數獨終局生成及殘局求解

文章目錄

• • • 一、項目位址
    • 二、各子產品開發時間預估
    • 三、學習過程、解題思路
    • • 3.1 開發語言及運作環境
      • 3.2 項目要求分析
      • • • 3.2.1 需求模組化
          • 3.2.2 資料流設計方法
      • 3.3 解題思路
      • • • 3.3.1 指令校驗子產品
          • 3.3.2 生成數獨終局（組）子產品
          • 3.3.3 殘局校驗子產品
          • 3.3.4 求解數獨殘局（組）子產品
    • 四、設計實作過程
    • • 4.1 程式流程圖
      • 4.2 主要函數接口設計
      • 4.3 各函數之間的關系
    • 五、程式性能分析及改進（測試均為1e6資料規模）
    • • 5.1數獨終局生成子產品
      • 5.2 數獨殘局求解子產品
    • 六、代碼說明
    • • 6.1 數獨終局生成子產品
      • • • 6.1.1 首行全排列子產品
          • 6.1.2 數獨終局生成子產品函數
      • 6.2 數獨殘局求解子產品
    • 七、單元測試
    • • 7.1 指令校驗子產品
      • 7.2 求解數獨殘局中的DFS子產品
    • 八、各子產品實際開發時間及與預期對照
    • 九、個人總結
    • • 9.1 個人能力的提升
      • • • 9.1.1 培養結構化設計程式的思維
          • 9.1.2 掌握更高效的程式設計技巧
          • 9.1.3 模仿與自學能力
      • 9.2 不足之處

一、項目位址

github位址：https://github.com/ZJT1024/Sudoku

二、各子產品開發時間預估

注：實際耗時在結尾處給出。

PSP2.1	Personal Software Process Stages	預估耗時（分鐘）
Planning	計劃	15
Estimatie	估計這個任務需要多少時間	20
Development	開發	240
Analysis	需求分析（包括學習新技術）	30
Design Spec	生成設計文檔	60
Design Review	實際複審（和同僚稽核設計文檔）	120
Coding Standard	代碼規範（為目前的開發制定合适的規範）	60
Design	具體設計	90
Coding	具體編碼	360
Code Review	代碼複審	90
Test	測試（自我測試，修改代碼，送出修改）	300
Reporting	報告	90
Test Report	測試報告	20
Size Measurement	計算工作量	60
Postmortem & Process Improvement Plan	事後總結，并提出過程修改計劃	30
合計	1585

三、學習過程、解題思路

3.1 開發語言及運作環境

考慮到不同語言的程式運作速度問題，根據題目要求及個人對所要求語言的熟悉程度，本次項目采用C++進行開發，運作環境為64bit Windows10。

3.2 項目要求分析

該項目的主要目的是實作一個能夠生成數獨終局并能求解數獨的控制台程式，此外項目還需包括代碼分析、性能測試。由于本次項目需要按照軟體工程開發的一般流程進行，是以，除了核心代碼之外，代碼分析和性能測試就尤為重要。由于該項目具有一定特殊性，即項目需求明确且固定，為友善之後進行單元測試，項目選用增量模型進行開發，每個需求之間采用瀑布模型，設計方法采用結構化的設計方法，盡量做到函數子產品之間高内聚低耦合。

3.2.1 需求模組化

由題意可知，程式需要能夠判斷使用者輸入指令，對于不同指令執行不同子程式，并給出回報，其中，子程式包括生成數獨終局子產品和求解數獨殘局子產品。

• 資料模組化——ER圖描述

  通過對題目進行分析，進篩選得到如下實體和實體屬性：

  指令：輸入檔案名*、操作指令*、參數*

  檔案：檔案名*、輸入輸出類型*

  數獨局：行資料、列資料、宮資料

  

• 功能模組化——資料流圖（DFD）
• • 頂層圖（第0層圖）：

    

    項目主要功能是根據使用者提供的合法指令完成數獨終局的生成或數獨殘局的求解，将結果寫入指定檔案并能在程式出現異常時給使用者相應的回報資訊。
• • 一層圖：

    

    整個項目采用結構化設計，将主要過程進行子產品化封裝，做到高内聚低耦合。通過對題目的分析，本次項目開發将大緻分為四部分，分别為：指令校驗子產品、生成數獨終局（組）子產品、殘局校驗子產品、求解數獨殘局（組）子產品。其中，生成數獨終局（組）對應數獨終局生成功能，殘局校驗子產品和求解數獨殘局子產品對應殘局求解功能。

• • 二層圖：

    （指令校驗子產品）

    

    在指令校驗子產品中，将指令拆分為三部分分别進行校驗，并在校驗結束後提取出合法操作符和參數，如果不合法則對使用者進行提示。

    （生成數獨終局（組））

    

    在生成數獨終局（組）子產品中，程式根據終局需求數生成終局，每生成一個新終局就輸出一個并計數，節約記憶體。

    （殘局校驗子產品）

    

    在殘局校驗子產品，程式根據從檔案中獨入的數獨殘局的數字進行校驗，檢查是否有重複數字，若沒有則對完整性進行校驗，檢查殘局是否滿足9行9列，若都滿足則輸出合法殘局，否則則想使用者輸出非法數獨殘局的回報資訊。

    （求解數獨殘局（組））

    

    在求解數獨殘局（組）子產品，程式先統計合法殘局中的空位及它周圍的資料，之後在對每個空位進行求解，因為合法的殘局一定有一個解，是以程式一定能找到一個完整的數獨解。

• 行為模組化——狀态轉換圖

  下圖展示了數獨終局生成和數獨殘局求解程式的運作過程。

  

3.2.2 資料流設計方法

• 複審并精華資料流圖

  進過對資料流圖的進一步分析，在“生成數獨終局（組）”子產品和“求解數獨殘局（組）”子產品之後各增加一個輸出子產品，将原來的按字元輸出轉化為按塊輸出，提高輸出效率。得到的資料流簡化圖如下（其中，子產品5與子產品6為增加的輸出部分）：

  

• 劃分自動化邊界，确定資料流的特征為變換流

  自動化邊界的劃分如上圖虛線所示，資料流圖中沒有明顯的事物進行中心，将其視為變換流。

• 劃分資料輸入、輸出邊界，分離出處理部分

  輸入輸出邊界的劃分如上圖大括号所示，其中輸入部分包括指令輸入與校驗和數獨殘局的輸入與校驗，變換部分包括數獨終局生成和數獨殘局的求解，輸出部分為将對應的數獨終局輸出到指定檔案中。

• 執行“一級分解”

  系統的一級分解圖表現了系統高層的組織結構和高層子產品之間的資料流向，其一級分解圖如下圖所示：

  

• 執行“二級分解”

  二級分解細化了一級分解的結構組織，下圖為系統的二級分解圖：

  

3.3 解題思路

整個項目大緻分為四個子產品，根據題意，程式在指令子產品需要能夠判斷輸入指令是否合法，若合法再進行相應操作；生成數獨終局（組）子產品程式需要在竟可能短的時間内生成最多不超過1000000個不重複的數獨終局；殘局校驗子產品要能夠對使用者輸入的殘局進行校驗，當殘局合法時才進行殘局求解計算；求解數獨殘局（組）子產品需要在竟可能短的時間内對最多1000000個合法殘局進行求解。

3.3.1 指令校驗子產品

由題意可知，合法指令有如下兩種格式：

sudoku.exe -c 20  // 執行sudoku.exe程式 輸入指令-c 20
sudoku.exe -s absolute_path_of_puzzlefile	  // 執行sudoku.exe程式 輸入指令-s absolute_path_of_puzzlefile
           

是以指令校驗子產品的任務應該是檢驗操作符是否為“-c”或“-s”，操作符後的參數是否符合要求，是以該子產品隻需對指令兩個部分分别檢驗即可。因為除了檢驗指令合法性，該子產品還需要對合法指令進行操作符合參數的提取，是以不放接口參數直接用引用類型，将參數直接指派，而操作符用整型（1/0）或bool型傳回。

3.3.2 生成數獨終局（組）子產品

• 暴力枚舉

  對于少量的數獨終局，我最先想到的是暴力枚舉，即每個位随機取[0,9]的整型數字，之後判斷是否合法，直到填滿81個空格，在生成一個數獨總局之後進行查重…顯然，這是一種非常費時的算法，就算進行适當優化，在不考慮輸出的情況下，假設每個位置的數字均能一次随機出合法數字，則每個數字的合法性的檢驗需要O(n）的複雜度，生成一個數獨終局需要O(n)的複雜度。之後是查重，對n個二維數組查重需要O(n^3)的複雜度。

  是以，在特别理想的情況下，該算法的時間複雜度為O(n^3)，顯然不能滿足1000000數量的求解問題…

• 全排列算法

  通過簡單觀察以及查閱資料得知，全排列是生成數獨終局的有效算法之一。以第一行為下列資料為例：

  當第二行向左（或右）平移（n % 9）位，且（n % 9 != 0）時，該兩行中的任意兩列元素一定不同。同理，之後的7行也做類似處理，這樣就能初步保證9行中任意兩列沒有重複的元素，因為每一行是由平移得到的，是以隻要保證了第一行沒有重複元素，之後的9行中任意一行都不會有重複元素。之後就是保證每個3X3的宮内元素不重複。

  通過嘗試發現，當從第二行開始，每行依次向一個方向平移3、6、1、4、7、2、5、8個機關時，每個宮内的元素不重複。至此一個有效的數獨終局便已形成。該算法的優勢在于，由于平移的原理，在首行無重複元素的情況下，生成的數獨終局一定合法，不需要再對每個元素進行合法性檢驗，時間複雜度為O(1)；其次，隻要首行不同，生成的終局一定不同（至少首行不同），是以隻要保證首行不同，就不用進行查重，時間複雜度為O(n)。

  現在問題就有求解一個數獨終局轉化成了求解8個數（第一位固定為8）的全排列問題。由于8個數規模不大，隻需使用簡單的遞歸便能實作8個數的全排列，複雜度為O(1)。

  參考文章：筆試面試算法經典–全排列算法-遞歸&字典序實作（Java）

  通過簡單計算發現，此時的可以生成的數獨終局的總數為：8! = 40320種，不足1000000，是以再進行優化。繼續觀察發現，位于同一小九宮格中的數字，兩行間整行交換或兩列間整列交換不影響結果，但是如果是兩個小九宮格中的各一行（或各一列）進行整體交換，則可能引起交換之後小九宮格中出現重複元素。由于第一行第一個元素固定，是以，前三行（第一行九宮格）中，第2行和第3行可以進行交換，中間三行（第二行九宮格）中，三行間可兩兩交換，最後三行（第三行九宮格）也可以三行間兩兩交換。這樣，若不考慮列交換，則現在能夠生成的數獨終局數量為：8! X ( 2! X 3! X 3! ) = 2903040，大于1000000。是以，隻需考慮首行全排列和行排列（或列排列）即可。

  綜上所述，使用全排列算法的時間複雜度為O(n)。

3.3.3 殘局校驗子產品

殘局校驗子產品需要對目标檔案中的數獨殘局題目的合法性進行檢測，主要檢測題目中的元素是否都是[0,9]的整型數字、題目行數（列數）是否為9、題目給出的已知數字之間有沒有沖突等。殘局檢驗子產品隻需對每個殘局進行掃描，并對已知數字進行行列檢測即可。該子產品相對簡單，且題目中沒有明确說明數獨殘局題目有出錯的情況，是以在此不多做分析。

3.3.4 求解數獨殘局（組）子產品

該子產品需要對一個合法的數獨殘局進行求解，對于每道題，給出一個可行解即可。根據以往做題經驗，看到題目後，我嘗試使用回溯進行求解，用适當的剪枝政策進行優化。

有上一個子產品的處理，該子產品的到的數獨殘局一定是合法的，由于數獨的特性，該殘局一定有至少一個可行解。于是，在讀取殘局的過程中，将空位（為0的位）放入記錄的數組中，當掃描結束後，直接按照記錄空位數組中的坐标（行号，列号）進行試探。試探過程采用深搜政策（DFS），從第一個空位開始，填入[1,9]中的一個整型數字，之後對該數字的有效性進行判斷，如果有效，則進行下一個空位的試探，如果該位置9個數字都不滿足要求，則傳回上一個空位，換另一個數字進行試探。當所有空位試探完畢後，便得到一個可行的數獨解。

該算法的複雜度為O(n^m)，m為空位個數，可見深搜其本質是枚舉，是以複雜度很高，通過查閱資料，程式将在深搜的基礎上進一步優化。

參考文章：暴力算法之美：如何在1毫秒内解決數獨問題？| 暴力枚舉法+深度優先搜尋

受文章啟發，反思原有算法發現，程式的時間開銷除了在試探每一個數以及回溯上，還主要在檢驗目前位置數字的有效性上，為了降低時間複雜度，在此用犧牲空間換區時間效益的方式，增加三個記錄表，分别用于記錄某個數字在某行是否出現，某個數字子在某列是否出現，以及某個數字在每個小九宮格中是否出現。這樣在判斷目前位置數字的有效性的時候，時間複雜度就從O(n)降為了O(1)。

除此之外，由于隻需要輸出一個可行解，根據啟發式規則，如果目前空位能填的有效數字數量為x，下一空位能填的有效數字的數量為y，當x>y時，先試探有效數字數量少的空位能夠在一定程度上降低時間消耗（如：目前空位可填的有效數字數量為4，下一空位可填的有效數字數量為1，則先填充下一空位能夠有效減少程式回溯的次數）。是以，在統計完所有空位之後對所有空位按照其能填的有效數字的數量先進行預處理（排序），将一定程度上減少回溯的次數，且空位最多為81位，排序的時間開銷可以忽略。

這樣一來，怎樣提高回溯效率的問題就轉化成了怎麼計算目前空位可填的有效數字數量的問題。根據啟發式規則，如果一個空位周圍（所在行、所在列、所在小九宮格）的已知數字越多，那麼該空位能填的有效數字應該相對就越少。是以隻要在掃描的過程中記錄下每行、每列、每個小九宮格中已知的數字的數量，便可作為之後對空位排序的依據。

四、設計實作過程

4.1 程式流程圖

4.2 主要函數接口設計

該程式中，比較重要的函數有：全排列函數，數獨終局生成函數，遞歸求解數獨殘局函數。

首行全排列函數：由上述全排列算法可知，每一種首行排列能夠産生2! X 3! X 3! = 72個不同的數獨終局，是以用一個max_num記錄目前需求數（-c 目前需求數） 所需的最多首行排列數，用一個每行有8個元素的二維數組target[Maxn][8]記錄不同排列，每行為一種排列，最多有max_num種。

數獨終局生成函數：用一個8元素的一維數組記錄從第二行到第九行的平移偏移量（例：move_step[0][8] = {3, 6, 1, 4, 7, 2, 5, 8}，一個下标表示第n + 1中平移偏移量），與首行全排列類似，也可通過遞歸的方式得到足夠的平移偏移量序列組。現在已經有了首行的全排列序列和足夠的平移偏移量序列，是以在數獨終局生成函數中，将兩個排列組傳入函數體，然後在函數内部件兩組序列按上述全排列算法中的方式進行組合，最後按要求輸出。

遞歸求解數獨殘局函數：按上述回溯剪枝的遞歸求解數獨殘局算法，在執行該子產品前，程式因通過對合法殘局的掃描已經得到各空位組成的數組，各行各列各小九宮格的資料資訊。是以，在該函數子產品中，按照空位數組（預處理後）順序進行深搜（DFS）

4.3 各函數之間的關系

由于在編寫項目時，VS不是企業版，無法自動生成各函數之間的調用關系，是以，下圖為手繪函數調用關系圖：

五、程式性能分析及改進（測試均為1e6資料規模）

5.1數獨終局生成子產品

由上述分析報告可知，數獨生成子產品的瓶頸主要在最後的輸出方式上，是以對函數子產品的輸出方式進行優化。考慮到原來的方式為單個數字輸出，系統的讀寫速度與CPU運算速度相比要慢得多，是以因減少讀寫次數，是以考慮将一個數獨終局中的所有元素轉換成一個字元串，用puts()函數一次性輸出。一下為優化之後的代碼分析報告：

可見，減少了讀寫的次數後，程式品質有了大幅度的提高，解決1e6規模的問題耗時不到10s。

5.2 數獨殘局求解子產品

吸取數獨終局生成子產品的教訓，數獨殘局求解中已經優化了讀寫子產品。

根據分析結果，考慮到在使用類時（特别是數組時），每個類對象需要執行構造函數和析構函數，再加上私有類成員不能直接通路，導緻程式運作速度下降。于是考慮用結構體代替類，得到下圖：

效果不是很明顯…這說明兩點：1.類的構造函數基本不會占用太多時間；2.深搜的本質是枚舉，枚舉真的很慢…（也許是剪枝剪得不夠）

六、代碼說明

該部分主要對程式的核心代碼：數獨終局生成子產品、數獨殘局求解子產品，進行必要說明。

6.1 數獨終局生成子產品

6.1.1 首行全排列子產品

void Permutate_for_permutation(int source[], int start, int end, int target[Maxn][Maxm], int& line, int max_num)
/*****************************************************************************
參數：source[]：初始的排列（後續生成的所有排列通過該排列變換，相當于種子
      start：需要排列的序列起點，用于遞歸
	  end：需要排列的序列終點，用于遞歸
	  target[Maxn][Maxm]：每一行記錄一種排列
	  line：記錄目前生成的排列是第幾種
	  max_num：需要最多的首行排列數

作用：該函數能更具max_num和source[]，遞歸調用自身，完成對初始序列的全排序，将排序結果
	  放在target數組中，每一行放一種排序，最多有max_num行
******************************************************************************/
{
	if (start == end)	//  終止條件
	{
		for (int i = 0; i <= end; i++)
		{
			target[line][i] = source[i];
		}
		line++;
	}
	else
	{
		for (int i = start; i <= end; i++)
		{
			if (line >= max_num)	// 目前全排序還沒有生成結束，但是應為目前的終局生成需求數不需要那麼多，是以強制傳回
			{
				return;
			}

			Swap(source[i], source[start]);		//  交換兩個元素位置
			Permutate_for_permutation(source, start + 1, end, target, line, max_num);
			Swap(source[i], source[start]);
		}
	}
}
           

需要注意的是，之前提過，每一種首行排列能夠産生 2! x 3! x 3! = 72個數獨終局，是以不需要每次求解都産生首行的說有排列，隻需（目前終局需求數 / 72）下取整即可。上述函數子產品的本質是一個 排列通過有限次兩兩元素交換能得到另一個排列。

6.1.2 數獨終局生成子產品函數

void FillTheBlock(int cnt, int move_step[80][Maxm], int permutation[Maxn][Maxm])
/*****************************************************************************
參數：cnt：指令中-c的參數，即需要的數獨生成終局的數量
	  move_step[80][Maxm]：第2至9行的行平移偏移量，每一行為中排序，每行的第i個元素對應第i + 1行的平移偏移量
	  permutation[Maxn][Maxm]：首行排序，每一行對應一種排序

作用：該函數将首行全排列和2隻9行每行平移偏移量結合起來，生成數獨終局，一個首行全排列和一個平移偏移量排列即
可組成一個數獨終局
******************************************************************************/
{
	...  // 第一行處理（因為第一行不用平移，是以單獨處理）
		 // temp為函數内的局部變量，是一個字元串，記錄一整個數獨終局，temp_site是對應的腳标
	
	for (int i = 1; i < 9; i++)		//  輸出 2 ~ 9 行
	{
		for (int j = 0; j < 9; j++)
		{
			int site = (j + move_step[ml][i - 1]) % 9;	//  對整行進行平移（向左）

			temp[temp_site] = permutation[pl][site] + '0';
			temp_site++;

			if (j == 8)
			{
				if (i == 8)
				{
					temp[temp_site] = '\0';
					temp_site++;
				}
				else
				{
					temp[temp_site] = '\n';
					temp_site++;
				}
			}
			else
			{
				temp[temp_site] = ' ';
				temp_site++;
			}
		}
	}
	...  //  輸出
}
           

該部分代碼的實質其實就是将從兩個集合裡分别選一個元素進行組合，其中需要注意的是，每次要對平移後的腳本模9，保證腳本不超過[0,8]的範圍。

6.2 數獨殘局求解子產品

bool DFS(Point p[], const int& num, int rm[Maxm][Maxm], int cm[Maxm][Maxm], int bm[Maxm][Maxm], int step, int block[Maxm][Maxm])
/*****************************************************************************
參數：p[]：空位數組，在掃描之後，記錄個空位的坐标（行，列）等有關資訊
      num：空位數量，記錄空位總數，作為遞歸重點的依據
	  rm[Maxm][Maxm]：行元素記錄表，rm[x][y] == 1 表示x行包含元素y
	  cm[Maxm][Maxm]：列元素記錄表，cm[x][y] == 1 表示x列包含元素y
	  bm[Maxm][Maxm]：塊元素記錄表，bm[x][y] == 1 表示小九宮盒x包含元素y，小九宮格順序為從0到8，一行一行編碼
	  step：表示目前在試探的空位在空位數組中的腳标，用于遞歸
	  block[Maxm][Maxm]：記錄一個數獨殘局

傳回值：bool型，傳回1表示遞歸找到了可行解，否則表示沒有找到

作用：通過遞歸調用自身，按照空位數組p[]中的順序對每個空位進行試探，當填滿所有空位時，遞歸結束，找到一個可行解
******************************************************************************/
{
	if (step == num)
	{
		return true;
	}

	for (int i = 1; i <= 9; i++)	//  對于每個空位，從1到9依次試探
	{
		int r = p[step].row, c = p[step].col;

		if (CheckNum(rm[r][i], cm[c][i], bm[GetBlockNum(r, c)][i]))	// 檢查在空位（r,c)上填數字i是否合适
		{
			/* 打表記錄 */
			SetMark(rm, r, i, 1);
			SetMark(cm, c, i, 1);
			SetMark(bm, GetBlockNum(r, c), i, 1);
			
			block[r][c] = i;
			/*  結束  */

			if (DFS(p, num, rm, cm, bm, step + 1, block))	//搜尋下一個空位
			{
				return true;	// 遞歸找到了一個可行解
			}

			/*  遞歸沒有找到可行解，目前位置不能填數字i，恢複之前打表的資料  */
			SetMark(rm, r, i, 0);
			SetMark(cm, c, i, 0);
			SetMark(bm, GetBlockNum(r, c), i, 0);

			block[r][c] = 0;
			/*  結束  */
		}
	}

	return false;
}
           

此處列出了該函數子產品的核心部分，回溯搜尋及剪枝，其中剪枝的思想展現在掃描過程（DFS（）之前的預處理）中記錄空位數組并根據相關資訊對數組進行排序，其次還展現在打表記錄每行每列每小九宮格中某個數字是否存在，友善快速驗證試探數字的有效性。至于是否需要再進行預處理篩選出每個空位可以填的候選數字，我認為沒有必要，應為篩選候選數字需要在整個數獨殘局掃描結束之後才能進行，上述代碼塊相當于是在找候選數字的同時直接對候選數字進行試探，理論上效率更高。

七、單元測試

由于本次開發以結構化設計開發方式進行，以增量模型開發，每個部分為小的瀑布模型，是以整個程式子產品話程度較高，基本做到高内聚，低耦合。是以，很容易做到對每個子產品進行單元測試。測試主要以白盒測試為主，每個單元測試偏向于對判斷部分的路徑測試，測試用例在代碼庫裡，在此僅展示測試結果圖。

7.1 指令校驗子產品

7.2 求解數獨殘局中的DFS子產品

因為有效的數獨問題一定至少有一個可行解，是以DFS函數子產品正常情況下一定能傳回true，是以該子產品的單元測試主要偏向于測試生成的數獨殘局的可行解是否正确（即，每行每列每小九宮格沒有重複元素）。另外，因為之前以及預設DFS的起點是空位數組的第一個位置，是以忽略了起點的邊界值等問題，經過單元測試，将起點的邊界值判斷也歸入其中。

八、各子產品實際開發時間及與預期對照

PSP2.1	Personal Software Process Stages	預估耗時（分鐘）	實際耗時（分鐘）
Planning	計劃	15	30
Estimatie	估計這個任務需要多少時間	20	20
Development	開發	240	300
Analysis	需求分析（包括學習新技術）	30	90
Design Spec	生成設計文檔	60	90
Design Review	實際複審（和同僚稽核設計文檔）	120	90
Coding Standard	代碼規範（為目前的開發制定合适的規範）	60	60
Design	具體設計	90	120
Coding	具體編碼	360	480
Code Review	代碼複審	90	120
Test	測試（自我測試，修改代碼，送出修改）	300	360
Reporting	報告	90	90
Test Report	測試報告	20	60
Size Measurement	計算工作量	60	30
Postmortem & Process Improvement Plan	事後總結，并提出過程修改計劃	30	30
合計	1585	1970

九、個人總結

9.1 個人能力的提升

9.1.1 培養結構化設計程式的思維

這是我第一次以工程化的角度編寫C++程式，與以往做題不同，以往做題，通常所有檔案都隻用放到一個main.cpp中，隻要最後OJ系統判斷正确，就萬事大吉，而以工程化方式編寫程式則更像是一步一個腳印的成長，讓自己的程式有規律的健壯。在結構化程式設計過程中，需要先确定需求，認真進行需求分析，弄清各資料流在程式子產品之間的轉化，真正做到條例清晰。另外，工程化程式設計和做題的顯著差別在于，bug的隐蔽性更高，當然對于培養個人改程序式能力而言，這是一件好事。

9.1.2 掌握更高效的程式設計技巧

由于工程程式設計需要對代碼進行分析，對子產品進行單元測試，在完成每個小任務的過程中，我見識到了新的程式設計技巧，打破了一貫的隻會盲目輸入用例進行調試，優化代碼得通篇細看的習慣。在VS的代碼分析工具的幫助下，我能很快定位程式中的瓶頸，根據二八定律，我便能有針對性的對程式進行優化，而且效果顯著。在VS單元測試功能的幫助下，我掌握了對單個子產品進行批量測試的方法，不用再像以往一樣通篇盲目調試，這樣一來，我定位bug的能力又上了一個台階。總的來說，學無止境，隻有不斷開闊自己的眼界，才能真正使自己便利。

9.1.3 模仿與自學能力

在編寫項目和優化過程中，有很多功能是我第一次接觸，這對我的自學能力是一個很大的挑戰，好在如今網絡便利，加上教程豐富，讓我能夠很快的上手使用有關功能。仔細想想，從事有關計算機方面的事情，要是沒有一定的學習熱情和自學能力，真的很快就會被淘汰。

9.2 不足之處

由于計算機發展迅速，是以很多新技術、新資料通常都是英文版的，在這次項目實踐過程中，我深切感受到，若不能讓英語成為自己的強項，那它終将成為自己的絆腳石。這次項目編寫讓我真切的認識到了自己的不足，也讓我有了強烈的危機感，相信在今後的學習生活中，我會銘記現在的這樣迫切想要變得更加優秀的心情，一直努力。