軟工結對項目
## 一、 Github項目位址
## 二、 PSP表格
| Psp | personal software progress stages | 預估耗時 | 實際耗時 |
|---|---|---|---|
| planning | 計劃 | 15 | 20 |
| estimate | 估計這個任務需要多少時間 | 10 | |
| development | 開發 | 600 | 700 |
| analysis | 需求分析 | 25 | |
| design spec | 生成設計文檔 | ||
| design review | 設計複審 | ||
| coding standard | 代碼規範 | ||
| design | 具體設計 | 30 | |
| coding | 具體編碼 | 300 | 320 |
| code review | 代碼複審 | 60 | |
| test | 測試 | 200 | 260 |
| reporting | 報告 | ||
| test report | 測試報告 | ||
| size measuring | 計算工作量 | 5 | |
| postmortem & process improvement plan | 事後總結，提出過程改進計劃 | 40 | |
| 合計 | 1335 | 1575 |
## 三、 看教科書和其它資料中關于Information Hiding, Interface Design, Loose Coupling的章節，說明你們在結對程式設計中是如何利用這些方法對接口進行設計的
- Information Hiding
- 資訊隐蔽将可能變化的因素封裝起來，遇到變化時對該子產品進行操作即可，不會影響到其它子產品。對于這一點，我們将一些必要的部件封裝成類，将其變量成員設定為私有，通路隻通過方法來通路，之後再修改也隻要針對需要修改的子產品進行修改，不需要改動其它子產品。
- Interface Design
- 在考慮接口設計時，要厘清楚哪些子產品之間是有聯系的，設計時應該要遵循下面那個高内聚低耦合的原則。
- Loose Coupling
- 内聚是一個子產品内各個元素彼此結合的緊密程度，耦合是一個軟體結構内不同子產品之間互連程度的度量 。這個原則要求我們設計時明确每一個子產品的作用，子產品與子產品之間盡量無牽扯，就如生成數獨與解數獨，這兩個子產品盡可能的沒有什麼共用的東西，而生成數獨與挖空有聯系。
## 四、 計算子產品接口的設計與實作過程。設計包括代碼如何組織，比如會有幾個類，幾個函數，他們之間關系如何，關鍵函數是否需要畫出流程圖？說明你的算法的關鍵（不必列出源代碼），以及獨到之處
**求解數獨，對生成的數獨挖空得到題目，指令行部分（參數分析等）和異常處理**：
涉及到Core子產品中的以下函數：
_declspec(dllexport) bool __stdcall solve(int puzzle[81], int solution[81]);
_declspec(dllexport) bool __stdcall blank(int puzzle[81], int mode);
_declspec(dllexport) bool __stdcall blank(int puzzle[81], int lower, int upper, bool unique);
Node* toMatrix(int puzzle[81]);
void remove(Node* c);
void resume(Node* c);
int dance(Node* head, int solution[81]);
int dance(Node* head, int &tag);
bool DLX(int puzzle[81], int solution[81]);
bool isunique(int puzzle[81]);
void Delete(Node* n);
void init(Node* n);
blank用于對生成好的數獨挖空得到題目，挖空時根據傳入的參數在範圍内随機挖空，會調用isunique判斷挖完的題目是否有唯一解，傳入參數不合法的話會抛出異常并傳回false
由于在實際上玩數獨的時候比起解的個數，挖空數對難度的影響要大得多，是以本項目難度的劃分不考慮解的個數，具體為:
| 難度 | 挖空數 |
|---|---|
| 1 | 20~35 |
| 2 | 36~45 |
| 3 | 46~55 |
求解使用了DLX算法，使用連結清單實作：
- DLX用于求解數獨，會調用dance(Node* head, int solution[81])和toMatrix，傳回值表示是否有解
- isunique用于判斷一個數獨題目是否有唯一解，會對數獨進行回溯求解，直到回溯完成或找到兩個解。是對DLX進行少量重寫得到的，傳回值表示是否有唯一解
- isunique中調用dance(Node* head, int &tag)，用tag标記解的個數，tag=2表示有兩個以上的解，=1表示唯一解，=0表示無解
- init用于初始化連結清單的節點，Delete用于釋放連結清單的空間
- 設計函數時将DLX算法分為2個部分：生成連結清單和周遊。其中周遊會多次執行删除元素和恢複元素的操作。是以将DLX的整個過程分為4個函數
- toMatrix用于生成連結清單，傳回head節點
- dance(Node* head, int solution[81])用于得出一個解并儲存到solution數組裡
- resume和remove分别用于恢複和删除連結清單中元素
生成部分：
涉及到的函數有：
generate(int number, int result[][81])
void produce(int total, int nums[], int block_num, int & count_total, int count_nums, int sudo[9][9], int result[][81]);
bool isinraw(int num, int raw_num, int sudo[9][9]);
bool isincolumn(int num, int c_num, int sudo[9][9]);
int insert(int num, int blocknum, int marked[], int sudo[9][9]);
void out(int sudo[9][9], int result[][81], int count_total);
生成函數采用的是回溯的方法，該方法雖然不能確定生成的所有數獨都不是等價的，但是是盡可能少的産生等價的數獨。
## 五、 畫出UML圖顯示計算子產品部分各個實體之間的關系
## 六、 計算子產品接口部分的性能改進。記錄在改進計算子產品性能上所花費的時間，描述你改進的思路，并展示一張性能分析圖（由VS 2015/2017的性能分析工具自動生成），并展示你程式中消耗最大的函數
基本隻對求解進行了改進，但是花費了大量時間（7-8h），第一版完成時在x86下進行了簡單的測試，當時還沒有發現問題，在第一版完成以後我們組進行了第四階段的交換測試，發現在x64環境下DLX求解變得十分慢而且記憶體消耗極大，在長時間調試後找到了原因。
一開始通過中斷調試找到了死循環，發現多次挖空時沒有還原挖過的數獨，修正了挖空的邏輯，但是問題沒有得到解決，然後通過記憶體分析發現連結清單的Node節點占用了大量的記憶體，可能是釋放連結清單空間出了問題。
經過長時間的分析後發現在求解完成時連結清單是不完整的，一部分節點被删除，但是變成了孤立節點，沒有被釋放（仔細想想求解完了的時候連結清單已經幾乎被删空了……）。
主要問題出現在dance函數上：
```
int Core::dance(Node* head, int solution[81])
{
if (head->right == head)
{
return 1; //得到一個解，傳回
}
Node *i = head->right->right;
Node *temp = head->right;
while (i != head)
if (i->countcount)
temp = i;
i = i->right;
if (temp->down == temp)return 0;
remove(temp);
i = temp->down;
while (i != temp)
Node *j = i->right;
solution[i->num[0] * 9 + i->num[1]] = i->num[2];
while (j != i)
{
remove(j->col);
j = j->right;
}
if (dance(head, solution))
return 1; //依次傳回1直到退出遞歸
j = i->left;
resume(j->col);
j = j->left;
solution[i->num[0] * 9 + i->num[1]] = 0;
i = i->down;
resume(temp); //用于恢複連結清單，但是退出遞歸的時候不會執行
return 0;
}
dance函數遞歸執行，在一開始連結清單是完整的，在遞歸過程中會逐漸删除連結清單中的元素，當執行到:
if (head->right == head)
return 1;
這段語句的時候，遞歸的dance函數會逐層傳回1并退出。但是這時，連結清單裡面隻剩一個head了。以原本的連結清單索引為基礎釋放隻能釋放head，其他元素已經變成了孤立節點。
可以通過在退出遞歸前還原連結清單或者建立額外的索引解決， 最後經過測試選擇了效率較高的方法，在連結清單中加入了一個額外的指針，使整個連結清單形成一個一維連結清單，以此為索引進行釋放就不會漏掉節點，最終解決了問題。
**性能分析**：
兩張分别對應生成數獨題和求解，生成參數為 -n 100 -u，求解為多次求解一個較難的17個數的數獨,由于generate調用了blank，blank調用了isunique，isunique調用了toMatrix和dance，時間主要消耗在轉換成矩陣上，求解也花了一定量的時間。求解的時候選用了難度較大的數獨，這時dance函數消耗的時間明顯上升,在使用-u參數的時候，由于需要多次求解和重新挖空，效率很慢，生成100個就要5s，目前還沒有找到什麼比較好的解決辦法。
<br>
##<font color=gray > 七、 描述這些做法的優缺點, 說明你是如何把它們融入結對作業中的</font>
- 優點
- 有利于設計層面上保證程式的正确性
- 獲得更優秀的設計
- 編寫契約可以幫助開發者更好地了解代碼
- 契約有助于測試（契約可以随時關閉或者啟用）
- 簡化調試
- 支援複用
- 缺點
- 撰寫契約需要時間
- 開發者需要時間學習撰寫良好契約的思想和技術
- 需要大量的實踐
- 目前的主流語言中，隻有Eiffel支援契約，而且僅僅支援順序式程式（sequential program）的契約
- 事先約定好各接口的參數定義以及能夠輸入的合法值，約定好各種條件下的傳回值。
<br>
##<font color=gray > 八、 計算子產品部分單元測試展示。展示出項目部分單元測試代碼，并說明測試的函數，構造測試資料的思路。并将單元測試得到的測試覆寫率截圖，發表在部落格中。要求總體覆寫率到90%以上，否則單元測試部分視作無效</font>
測試生成：
TEST_METHOD(TestGenerate)
{
// TODO: 在此輸入測試代碼
int sudo[9][9];
Core test;
int result[3][81];
test.generate(3, result);
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 81; j++)
{
sudo[j / 9][j % 9] = result[i][j];
}
for (int j = 0; j < 9; j++)
for (int k = 0; k < 9; k++)
{
for (int n = 0; n < 9; n++)
{
if (n != j)
{
Assert::AreEqual(false, sudo[i][j] == sudo[i][n]);
}
if (n != i)
Assert::AreEqual(false, sudo[i][j] == sudo[n][j]);
}
}
}
int blankNum = 0;
int puzzle[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,2,8,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
int backup[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
test.generate(1, 1, result);
for (int i = 0; i < 81; i++)
if (result[0][i] == 0)
blankNum++;
result[0][i] = backup[i];
Assert::AreEqual((20 <= blankNum&&blankNum <= 35), true);
blankNum = 0;
test.generate(1, 2, result);
Assert::AreEqual((36 <= blankNum&&blankNum <= 45), true);
test.generate(1, 3, result);
Assert::AreEqual((46 <= blankNum&&blankNum <= 55), true);
test.generate(1, 20, 55, true, result);
Assert::AreEqual((20 <= blankNum&&blankNum <= 55), true);
test.generate(1, 40, 40, true, result);
Assert::AreEqual((40 == blankNum), true);
}
分别針對生成的三種接口進行測試，檢測生成的數獨終局是否合法/題目是否符合要求
測試求解：
TEST_METHOD(TestSolve)
// TODO: 在此輸入測試代碼
int puzzle[81] = {
8,0,0,0,0,0,0,0,0
,0,0,3,6,0,0,0,0,0
,0,7,0,0,9,0,2,0,0
,0,5,0,0,0,7,0,0,0
,0,0,0,0,4,5,7,0,0
,0,0,0,1,0,0,0,3,0
,0,0,1,0,0,0,0,6,8
,0,0,8,5,0,0,0,1,0
,0,9,0,0,0,0,4,0,0,};
int result[81] = { 0 };
int answer[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,2,8,3,1,5,4,2,3,7,8,9
,6,3,6,9,8,4,5,7,2,1,2,8,7,1,6,9,5,3,4,5,2
,1,9,7,4,3,6,8,4,3,8,5,2,6,9,1,7,7,9,6,3,1
,8,4,5,2 };
int wrong[81] = { 8,1,2,7,5,3,6,4,9,9,4,3,6,8
,2,1,7,5,6,7,5,4,9,1,8,2,3,1,5,4,2,3,7,8,9
Core test;
bool isvalid = true;
test.solve(puzzle, result);
for (int i = 0; i < 81; i++)
puzzle[i] = answer[i];
Assert::AreEqual(result[i], answer[i]);
test.blank(puzzle, 20, 55, true);
isvalid = test.solve(wrong, result);
Assert::AreEqual(isvalid, false);
isvalid = test.solve(answer, result);
Assert::AreEqual(isvalid, true);
依次求解一個較難的數獨，随機挖空的唯一解數獨，不合法的數獨和完整的合法數獨，檢測求解的結果和傳回值正不正确。
同時檢測了判斷唯一解算法的正确性，若傳回的數獨不是唯一解的話求解出的result和answer可能不相同，不能通過測試。
單元測試覆寫率：
<br>
##<font color=gray > 九、 計算子產品部分異常處理說明。在部落格中詳細介紹每種異常的設計目标。每種異常都要選擇一個單元測試樣例釋出在部落格中，并指明錯誤對應的場景</font>
項目的異常分為三種：
|異常|描述|
|:--|:--|
|numberException|輸入的數獨生成數量異常|
|boundException|輸入的挖空邊界異常|
|modeException|輸入的難度異常|
TEST_METHOD(TestException)
int result[3][81];
try {
test.generate(2000000, result);
catch (numberException &e)
Assert::AreEqual(0, 0);
test.generate(20000, 2, result);
test.generate(20000, 20, 40, false, result);
test.generate(3, 5, result);
catch (modeException &e)
test.generate(3, 41, 40, false, result);
catch (boundException &e)
test.generate(3, 12, 40, false, result);
test.generate(3, 32, 70, false, result);
單元測試分别針對使用-c和-n時的參數，難度不為1-3，邊界超出範圍和lower>upper等情況進行了測試:
|測試函數|具體描述|
|:--|:--|
|test.generate(2000000, result);|使用參數-c，超出了最大範圍1000000|
|test.generate(20000, 2, result)|使用參數-n，超出了最大範圍10000|
|test.generate(20000, 20, 40, false, result)|使用參數-n，超出了最大範圍10000|
|test.generate(3, 5, result)|使用參數-m，輸入的參數不在1~3範圍内|
|test.generate(3, 41, 40, false, result)|使用參數-r，lower>upper|
|test.generate(3, 12, 40, false, result)|使用參數-r，lower超出範圍|
|test.generate(3, 32, 70, false, result)|使用參數-r，upper超出範圍|
<br>
##<font color=gray > 十、界面子產品的詳細設計過程。在部落格中詳細介紹界面子產品是如何設計的，并寫一些必要的代碼說明解釋實作過程</font>
界面主要分為兩部分：菜單欄和主界面。菜單欄實作的功能有難度的選擇，help文檔，主界面實作的功能有重新開始、清空、提示、送出、計時以及最佳記錄。
**數獨盤**：通過81個單行文本框實作，繼承了QLineEdit類實作MyLineEdit類，重寫了contextMenuEvent方法，新增了hint信号以及槽函數為了實作提示功能，新增setRead方法，使得題目中的數字背景變色以及hint失效。
**模式選擇**：在菜單中實作，通過點選執行相對應的槽函數，實作難度的改變。
**提示**：通過點選相應空格的右鍵進行提示，該動作的槽函數在自己寫的MyLineEdit類裡，該函數是發送信号，在主界面接受到信号後調用相應的函數求解并提示。
**計時計最佳記錄**：通過實作定時器和QTimer實作，讓定時器每隔一秒觸發一次，更新時間并輸入到文本框當中。最佳紀錄是在送出成功解正确後比對目前時間與最佳紀錄，若目前時間短則更新，通過一個字元串儲存在類裡。
具體布局代碼如下：
//布局
QGridLayout layout = new QGridLayout;
layout->addWidget(restartButton, 0, 0, 2, 1, 0); // 重新開始按鈕
layout->addWidget(clearButton, 0, 1, 2, 1, 0); // 清空按鈕
layout->addWidget(bestRecord, 0, 8, 1, 1, Qt::AlignRight); //最佳紀錄時間
layout->addWidget(nowRecord, 1, 8, 1, 1, Qt::AlignRight); //已經用時
layout->addLayout(layoutSudo, 2, 0, 1, 9, Qt::AlignCenter); // 99的方正
layout->addWidget(submitButton, 3, 0, 1, 9, Qt::AlignCenter); // 送出按鈕
計時部分代碼如下：
設定1秒觸發一次，調用updateTime函數，加一秒并更新文本框。
QLineEdit *bestRecord; // 顯示最好記錄的時間
QLineEdit *nowRecord; // 顯示現在的時間
QString record;
connect(timer, SIGNAL(timeout()), this, SLOT(updateTime()));
timer->start(1000);
void QtGuiApplication2::updateTime()
*TimeRecord = TimeRecord->addSecs(1);
nowRecord->setText(TimeRecord->toString("hh:mm:ss"));
提示部分代碼如下：
點選hint後，發出信号，在主界面接收到信号調用hintClicked()函數。
class MyLineEdit :public QLineEdit
protected:
QMenu * hintMenu = new QMenu();
QAction * action = hintMenu->addAction("hint");
void contextMenuEvent(QContextMenuEvent *event);
signals:
void hint();
public slots :
void hintCliked();
connect(blocks[nowNum], SIGNAL(hint()), this, SLOT(hintCliked())); // 提示綁定事件
<br>
##<font color=gray > 十一、界面子產品與計算子產品的對接。詳細地描述UI子產品的設計與兩個子產品的對接，并在部落格中截圖實作的功能</font>
- 要使用計算子產品的功能首先要配置相應的dll，我參考了這篇[部落格](http://www.cnblogs.com/houkai/archive/2013/06/05/3119513.html)。
- 接下來是具體的調用部分
- 首先建立了一個core對象，供調用函數。
- 初始化的時候調用generate(1, mode, sudo)，生成一個簡單的數獨局。
- 重新開始按鈕點選後，需要生成新的數獨局，同樣調用generate函數。
- 在送出按鈕點選後，需要先判斷填寫是否正确，錯誤的話應該顯示正确答案，此時先調用solve函數判斷解的正确性，若錯誤，再次調用solve函數。
- 模式選擇中，每次選擇一個模式，都需要生成相應模式的數獨，調用generate函數并傳入相應的模式難度參數。
- 提示被點選之後，要在該空顯示出數字，調用solve并取出對應位置的數填寫即可。
- 實作的功能有：模式選擇，幫助菜單，重新開始，清空目前所有，計時功能，最佳紀錄，提示功能
<br>
##<font color=gray > 十二、 描述結對的過程，提供非擺拍的兩人在讨論的結對照片</font>
主要的讨論都在網上進行，在确定結對後線上讨論得出分工，之後制訂計劃并開始編碼
讨論的結果是我負責除GUI和生成完整數獨算法以外的任務
在下課的時候會當面讨論一些線上無法解決的問題
<br>
##<font color=gray > 十三、 結對程式設計的優點和缺點</font>
- 優點
- 在開發層次，結對程式設計能提供更好的設計品質和代碼品質，兩人合作能有更強的解決問題的能力
- 對開發人員自身來說，結對工作能帶來更多的信心，高品質的産出能帶來更高的滿足感
- 在心理上, 當有另一個人在你身邊和你緊密配合, 做同樣一件事情的時候, 你不好意思開小差, 也不好意思糊弄
- 在企業管理層次上，結對能更有效地交流，互相學習和傳遞經驗，能更好地處理人員流動。因為一個人的知識已經被其他人共享
- 降低學習成本。一邊程式設計，一邊共享知識和經驗，有效地在實踐中進行學習
- 可以讓程式設計環境有效地貫徹Design
- 缺點
- 有時候，程式員們會對一個問題各執己見（代碼風格可能會是引發技術人員口水戰的地方），争吵不休，反而産生重大内耗
- 面對新手，有經驗的老手可能會覺得非常的煩躁。不合适的溝通會導到團隊的不和諧
- 有經驗的人更喜歡單兵作戰，找個人來站在他背後看着他可能會讓他感到非常的不爽，最終導緻程式設計時受到情緒影響，反而出現反作用
- 兩個人在一起工作可能會出現工作精力不能集中的情況，程式員可能會交談一些與工作無關的事情
- 對于有不同習慣的程式設計人員，可以在起工作會産生麻煩，甚至沖突
<br>
##<font color=gray>十四、 結對的每一個人的優點和缺點在哪裡 (要列出至少三個優點和一個缺點)</font>
- 個人
- 優點
- 代碼子產品分的比較清楚
- 比較細緻
- 遇到問題願意去溝通
- 缺點
- 不太主動去彙報進度
- 同伴
- 優點
- 積極溝通
- 有規劃，知道應該做什麼
- 願意嘗試
- 缺點
- 代碼不怎麼寫注釋，了解起來較困難
<br>
##<font color=gray>附加題： 界面子產品，測試子產品和核心子產品的松耦合</font>
合作小組：15061122 15061144
問題主要出現在兩方的測試子產品和Core對接，由于我們在測試的時候都用了非标準接口的函數，在測試時出現了問題。
我們對測試進行了針對性修改後可以使用他們的Core。
他們在測試時發現generate(100,40,55,true,result)會導緻程式異常，這是導緻發現第六部分提到的問題的原因（在此感謝他們）
由于我們測試的時候是在x86上，他們是在x64上，是以出現了完全不一樣的結果，對問題的處理和優化在第六部分有詳細說明。
gui與核心子產品對接沒什麼問題，隻是在設計上有所不同，他們把無解的數獨認為是異常，而我們能夠判斷，而我們的gui需要能判斷該數獨是否有解，也就是說，接上他們的核心子產品有可能填錯數獨而發生異常。