第二次作業——個人項目實戰
本次作業deadline:2017-9-10 23:00PM
0. 前言
閱讀了大家對于本課程的目标和規劃之後,想必很多同學都躍躍欲試,迫不及待想要提高自身實踐能力,那麼就從第一個個人項目開始吧,題目要求見下。
1. 閱讀
閱讀《建構之法》第一章至第三章的内容,并在下方作業裡展現出閱讀後的成果。特别是第2章中的效能分析及個人軟體開發流程(PSP)。
2. 題目描述
背景
數獨介紹:(摘自百度百科)
數獨是源自18世紀瑞士的一種數學遊戲。是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9盤面上的已知數字,推理出所有剩餘空格的數字,并滿足每一行、每一列、每一個粗線宮(3*3)内的數字均含1-9,不重複。
數獨盤面是個九宮,每一宮又分為九個小格。在這八十一格中給出一定的已知數字和解題條件,利用邏輯和推理,在其他的空格上填入1-9的數字。使1-9每個數字在每一行、每一列和每一宮中都隻出現一次,是以又稱“九宮格”。
工具清單
- 程式設計語言:C/C++/C#
- 程式設計IDE:推薦使用Visual Studio 2015/2017,下載下傳也推薦使用國内一些鏡像站點(不是盜版)MSDN,I tell you。
- 效能分析工具:推薦使用 Visual Studio Profiling Tools
- 源代碼管理平台:Github
項目需求
利用程式随機構造出N個已解答的數獨棋盤 。
輸入
數獨棋盤題目個數N(0<N<=1000000)
輸出
随機生成N個不重複的已解答完畢的數獨棋盤,并輸出到sudoku.txt中,輸出格式見下輸出示例。
[2017.9.4 新增要求] 在生成數獨矩陣時,左上角的第一個數為:(學号後兩位相加)% 9 + 1。例如學生A學号後2位是80,則該數字為(8+0)% 9 + 1 = 9,那麼生成的數獨棋盤應如下(x表示滿足數獨規則的任意數字):
9 x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
輸入示例
3
輸出示例(輸出檔案示例戳我)
2 6 8 4 7 3 9 5 1
3 4 1 9 6 5 2 7 8
7 9 5 8 1 2 3 6 4
5 7 4 6 2 1 8 3 9
1 3 9 5 4 8 6 2 7
8 2 6 3 9 7 4 1 5
9 1 7 2 8 6 5 4 3
6 8 3 1 5 4 7 9 2
4 5 2 7 3 9 1 8 6
4 5 1 7 8 2 3 6 9
7 8 6 4 9 3 5 2 1
3 9 2 1 5 6 4 8 7
5 2 7 6 4 9 8 1 3
9 6 8 5 3 1 2 7 4
1 3 4 2 7 8 6 9 5
8 1 5 3 6 7 9 4 2
6 7 3 9 2 4 1 5 8
2 4 9 8 1 5 7 3 6
9 5 8 3 6 7 1 2 4
2 3 7 4 5 1 9 6 8
1 4 6 9 2 8 3 5 7
6 1 2 8 7 4 5 9 3
5 7 3 6 1 9 4 8 2
4 8 9 2 3 5 6 7 1
7 2 4 5 9 3 8 1 6
8 9 1 7 4 6 2 3 5
3 6 5 1 8 2 7 4 9
測試須知
測試機為Windows環境,是以送出到Github上的項目均需要建立一個名字為
BIN
的檔案夾,裡面必須含有可執行檔案(以exe為字尾)與相關的依賴庫,請注意以下兩點:
- 確定可執行檔案的名字命名為 sudoku.exe。
- 確定生成的棋盤檔案 sudoku.txt 與可執行檔案在同一目錄下,生成檔案時請使用相對路徑!
一個示例組織目錄如下所示:
/ SudokuProject(工程名字自行指定即可)
/ main.cpp
/ generator.cpp
/ BIN
/ Lib.dll (exe運作需要的動态連結庫檔案,可以沒有)
/ sudoku.exe
/ sudoku.txt (運作exe後生成的檔案)
助教在測試時,将以指令行運作可執行檔案的方式進行批量測試,參數及其約定如下:
參數名字 | 參數意義 | 用法示例 |
---|---|---|
-c | 生成的數獨棋盤的數量 | sudoku.exe -c 20 |
值得一提的是,測試資料中有可能出現錯誤,比如出現 sudoku.exe -c abc 這樣的指令,你的程式需要自行處理錯誤情況,并給出合适的錯誤提示資訊。
附加題(選做)
1)現在已經有了一個數獨遊戲的生成器,如果想讓大家都能實際使用它,還需要一個簡單的遊戲界面。為數獨遊戲的生成器做一個GUI界面,并附上一個簡單的使用說明。界面需實作下述功能,會按點給分:
- 生成任意數量的數獨題目并将初始數獨棋局依次顯示。初始數獨棋盤需要挖空,要求為:99棋盤上挖空不少于30個,不多于60個。每個33的小棋盤中挖空不少于2個。比如下面這就是一個規範的棋局(5')
- 使用者可以在界面上通過點選或輸入完成數獨題目(3')
- 使用者完成數獨題目後可以得到回報,知道自己的題目是否做對(2')
【注意】選擇完成本附加題目的同學,需要将GUI與數獨遊戲生成器作為兩個工程開發,後者可以作為依賴庫為前者提供調用接口,但不可以把兩個工程直接混在一起。 GUI相關的部分也需要提供新的可執行檔案,放在根目錄的 GUIBIN
檔案夾下。
2)程式的基礎要求是完成一個數獨題目生成程式,但數獨棋局中是要求有獨解性的。是以數獨比賽中為了保障解題的趣味性與難度,一般會手工構造有唯一解的數獨程式。這種數獨題目的要求如下:
- 在9*9的棋盤中,初始棋盤最少有30個空
- 該數獨題目有且僅有唯一解
現在請你在之前程式的基礎上改進一下,完成上述需求。(10')
【注意】選擇完成本附加題目的同學,需要将改進版與原版作為兩個工程開發,後者可以作為依賴庫為前者提供調用接口,但不可以把兩個工程直接混在一起。 改進版相關的部分需要提供新的可執行檔案,放在根目錄的 GAMEBIN
檔案夾下。這部分程式的正确性與性能測試獨立于基礎測試,按通過的測試點給分。
随機生成N個不重複的有唯一解的數獨棋盤。挖空處用數字0表示,每個數獨棋盤中至少要有30個以上的0。輸出格式見下輸出示例,輸出需要到檔案sudoku.txt中。
2 0 0 0 0 0 9 0 1
3 4 0 0 6 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 3 0
0 0 9 5 0 8 0 0 7
0 0 6 0 0 0 0 0 0
0 0 0 0 0 0 5 4 0
0 0 0 1 0 0 0 0 0
0 0 0 7 0 9 0 0 0
4 0 0 0 0 0 0 0 0
7 0 6 0 9 0 5 0 0
0 0 0 1 0 0 0 0 0
0 2 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0
0 0 0 0 7 8 0 0 0
8 1 0 3 0 0 0 0 0
0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 7 0 6
0 0 0 0 0 7 0 2 0
0 0 0 0 0 0 0 0 0
1 4 6 0 0 0 0 0 0
0 0 0 0 0 0 5 0 0
0 7 3 0 0 9 0 0 0
0 0 0 0 0 0 6 0 1
0 2 0 5 0 0 0 0 0
0 9 0 0 0 0 0 3 0
0 0 0 1 8 0 0 0 0
3. 要求與說明
- 【項目設計】分析并了解題目要求,獨立完成整個項目,并将遵循上述測試須知中規範的最新項目釋出在Github上。
- 【項目測試】使用單元測試對項目進行測試,并使用插件檢視測試分支覆寫率等名額。
- 【性能優化】完成項目的首個版本之後,使用性能分析工具找出代碼中的性能瓶頸并進行改進。
- 【源代碼管理】在項目實踐過程中需要使用Github管理源代碼,代碼有進展即簽入Github。簽入記錄不合理的項目會被助教抽查詢問項目細節。
- 【部落格釋出】按照要求釋出部落格,利用在建構之法中學習到的相關内容,結合個人項目的實踐經曆,撰寫解決項目的心路曆程與收獲。部落格與Github項目明顯不符的作業将取消作業成績。
4. 博文規範
将博文釋出到個人部落格上,且需包含以下8個内容。
1)在文章開頭給出Github項目位址。(1‘)
2)在開始實作程式之前,在下述PSP表格記錄下你估計将在程式的各個子產品的開發上耗費的時間。(0.5‘)
3)解題思路描述。即剛開始拿到題目後,如何思考,如何找資料的心路曆程。(3‘)
4)設計實作過程。設計包括代碼如何組織,比如會有幾個類,幾個函數,他們之間關系如何,關鍵函數是否需要畫出流程圖?(4‘)
5)代碼說明。展示出項目關鍵代碼,并解釋思路與注釋說明。(5‘)
6)測試運作。程式必須是可運作的,展示出程式運作的截圖。PS:如果有擴充需求或者更進階的需求,請秀出來,有額外加分。(3‘)
7)記錄在改程序式性能上所花費的時間,描述你改進的思路,并展示一張性能分析圖,并展示你程式中消耗最大的函數。PS:如果采用Visual Studio Community 2015開發,使用C++或者C#語言實作,VS 2015的性能分析工具可自動生成。(3‘)
8)在你實作完程式之後,在下述PSP表格記錄下你在程式的各個子產品上實際花費的時間。(0.5‘)
附:PSP 2.1表格
PSP2.1 | Personal Software Process Stages | 預估耗時(分鐘) | 實際耗時(分鐘) |
---|---|---|---|
Planning | 計劃 | ||
· Estimate | · 估計這個任務需要多少時間 | ||
Development | 開發 | ||
· Analysis | · 需求分析 (包括學習新技術) | ||
· Design Spec | · 生成設計文檔 | ||
· Design Review | · 設計複審 (和同僚稽核設計文檔) | ||
· Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
· Design | · 具體設計 | ||
· Coding | · 具體編碼 | ||
· Code Review | · 代碼複審 | ||
· Test | · 測試(自我測試,修改代碼,送出修改) | ||
Reporting | 報告 | ||
· Test Report | · 測試報告 | ||
· Size Measurement | · 計算工作量 | ||
· Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
合計 |
附:部落格參考模闆
http://www.cnblogs.com/vertextao/p/7469789.html
5. 評分規則
本次個人項目分數由三部分組成,分别是
(1)部落格 — 20分,分數組成在博文規範中。
(2)程式 — 40分
- 5分為源代碼管理評分,該評分主要通過源代碼管理中的commit注釋資訊,增量修改的内容,是否有運作說明等給分。
- 25分為項目評分,正确性測試為20分,輸入範圍限制在 1-1000,要求程式在 60 s 内給出結果,逾時則認定運作結果無效。錯誤測試為5分。
- 10分為性能評分,性能測試中輸入範圍限制在 10000-1000000,沒有時間的最小要求限制。
- 當程式的正确性評分大于16分時才可以參與性能評分環節,是以請各位同學務必保證自己程式的正确性。
- 性能評分将采取檔級評分制度,助教将根據同學們的程式跑同一資料耗費的時間長度将程式分為若幹檔,每一檔的同學得到的分數為 10/檔級數。
(3)附加題 — 20分,分數組成已在附加題中寫到,附加題不參與總分映射。
(4)注意事項:
- 按時間完成并送出——正常評分
- 晚交一周以内——0分
- 晚交一周以上或不交——倒扣本次作業分數
- 抄襲——倒扣2倍本次作業分數【嚴禁代碼與部落格等一切形式的抄襲!部落格園支援了對部落格的查重功能,我們也有專用的代碼查重系統進行代碼查重。請各位同學千萬不要觸碰底線,勿謂言之不預也!】
(5)補考的同學,在截止時間,必須先送出部分部落格和部分代碼,允許在最後一門補考結束後的48小時内,補充完整。
6. 疑惑解疑
若有對題意不清或者有不了解的地方,可在該部落格下方留言,或者在微信群中直接提問。
7. 參考資料連結
- VS2015安裝與C++單元測試
- 基于C#的單元測試(VS2015)
- VS2015性能分析