作業鏈接

http://www.cnblogs.com/easteast/p/7469291.html

評分細則

本次個人項目分數由三部分組成，分別是

（1）博客 — 20分，分數組成如下:

• 在文章開頭給出Github項目地址。（1‘）
• 在開始實現程序之前，在下述PSP表格記錄下你估計將在程序的各個模塊的開發上耗費的時間。（0.5'）
• 解題思路描述。即剛開始拿到題目后，如何思考，如何找資料的心路歷程。（3'）
• 設計實現過程。設計包括代碼如何組織，比如會有幾個類，幾個函數，他們之間關系如何，關鍵函數是否需要畫出流程圖？（4'）
• 代碼說明。展示出項目關鍵代碼，并解釋思路與注釋說明。（5'）
• 測試運行。程序必須是可運行的，展示出程序運行的截圖。PS：如果有擴展需求或者更高級的需求，請秀出來，有額外加分。（3'）
• 記錄在改進程序性能上所花費的時間，描述你改進的思路，并展示一張性能分析圖，并展示你程序中消耗最大的函數。PS：如果采用Visual Studio Community 2015開發，使用C++或者C#語言實現，VS 2015的性能分析工具可自動生成。（3'）
• 在你實現完程序之后，在下述PSP表格記錄下你在程序的各個模塊上實際花費的時間。（0.5'）

（2）程序 — 40分，分數組成如下：

• 源代碼管理評分，該評分主要通過源代碼管理中的commit注釋信息，增量修改的內容，是否有運行說明等給分。(5')
• 項目評分，分為兩個部分的評分：
  • 正確性測試，輸入范圍限制在 1-1000，要求程序在 60 s 內給出結果，超時則認定運行結果無效。(20')
  • 錯誤處理測試。(5')
• 性能評分，性能測試中輸入范圍限制在 10000-1000000，沒有時間的最小要求限制。(10')

（3）附加題 — 20分，分數組成已在原作業的附加題中寫到。
（4）注意事項：

• 按時間完成并提交——正常評分
• 晚交一周以內——0分
• 晚交一周以上或不交——倒扣本次作業分數
• 抄襲——倒扣2倍本次作業分數【嚴禁代碼與博客等一切形式的抄襲！博客園支持了對博客的查重功能，我們也有專用的代碼查重系統進行代碼查重。請各位同學千萬不要觸碰底線，勿謂言之不預也！】

（5）補考的同學，在截止時間，必須先提交部分博客和部分代碼，允許在最后一門補考結束后的48小時內，補充完整。

項目總結

項目得分明細

t1 對應測試點 -c 1
t2 對應測試點 -c 5
t3 對應測試點 -c 100
t4 對應測試點 -c 500
t5 對應測試點 -c 1000
t6 對應測試點 -c 50000
t7 對應測試點 -c 1000000

數據

• 至發布博客時，有效選課人數76人
• 提交了有效的作業鏈接:74人
• Github上的項目有效:73人
• 正確地使用源代碼管理:32人
• 完成-c 50000測試的同學：42人
• 完成-c 1000000測試的同學：34人

評分

本次項目評分主要從四個部分:

• 正確得分(5個測試點,滿分20分)
• 效率得分(2個測試點,滿分10分)
• 錯誤處理得分(5個測試點,滿分5分)
• 源代碼管理得分(5個要點,滿分5分)

傳統OJ的測試一般都是按點給分：在規定時間內過測試點給分，不過測試點就不給分。而本次個人項目測試之所以加了額外的三個方面測試，也是想讓同學們從測試中體會一下完成一個軟件工程題目與完成一個算法題目的區別。在Z班學生眾多的情況下，這三個額外的測試帶來了比較大的負擔：每一項評分都需要仔細查看與復核，相比傳統過測試點法付出的時間與精力要很多。值得慶幸的是自己準備得比較早，開發了一套自動測試的工具鏈接，減輕了不少正確性測試部分的負擔。

不同方面的評價出于不同的目的，但總的目的還是想讓大家感受軟件工程的魅力，體會從需求分析，代碼實現到單元測試的整個流程。

• 正確得分是想讓用心完成項目的同學都能拿到一個至少可以及格的分數，所以雖然數據量只有1000，但也設置了一個比較寬裕的時間上限60s。
• 效率得分的設置則是為了讓同學們都有動力對自己的算法迭代改進。這種按照運行時間落在檔級給分的規則，也融合了一些北航團隊項目“檔級給分制”的思想。
• 錯誤處理得分是為了讓同學們有意識地練習寫健壯的程序。軟件工程不是ACM題，不是說“打一段代碼提交過了測試點”就可以的，培養學生主動考慮并處理錯誤情況的意識是很重要的一環。
• 源代碼管理得分是為了讓同學們注意到使用 Git 時需要遵循一定的規范。源代碼管理不是簡單地把工程打包上傳到 Github 上，這只能叫存放，不能叫管理。我們期望通過這一點告訴同學們什么樣的操作是好的操作，引導學生向好的做法看齊，并讓他們知道該怎樣改進。

誠然，每個部分都暴露了大大小小的問題，有學生的，也有我自己的。下面講一講遇到的這些問題，并與各位老師分享自己最后解決的經驗與教訓。

問題

正確性測試

正確性測試部分暴露出來的問題是最嚴重的，也是最超乎我想象的。主要的問題集中在三個方面：

• 沒看需求，盲目下手：將近一半的同學沒有仔細閱讀或者沒有閱讀 測試須知 一節，導致個人項目第一次自動測試時許多同學的項目都無法正常測試。
• 不做完備測試，依賴助教反饋：一部分同學是使用其他平臺(Linux, Mac OS)開發的，在完成自己的項目后并未通過其他途徑(尋找同學,搭建虛擬機等)測試過自己的exe文件是否可運行。當然還有一部分 Windows平臺下開發的同學，沒有在測試前通過多方面的驗證與測試確保自己的可執行文件沒問題，而是寄希望于助教的測試反饋來修正。
• 需求主次不明，存在僥幸心理：少部分同學沒有分清需求的主次，過分追求生成的速度而忽略了需求中的 數獨棋盤必須不重復 的條件，導致測試失分。

Part1.盲目下手

第一個問題暴露出同學們拿到題目后不做需求分析，直接上手編碼的壞習慣。我猜一部分同學在做這個數獨題目的時候大概是這樣的場景：

• 老師：恭喜大家收獲作業 * 1
• 學生：開心（抑制不住悲傷）地點開了作業鏈接
• ...
• 10秒后，學生關掉了作業，開始百度：常見的數獨求解算法

實際上，像這樣匆匆掃一眼就開始碼代碼是軟件工程里最忌諱的事情。可能會有同學說：助教，我確實是在設計了數獨算法以后才開始實現的算法。但是我想說的是，在開發中設計并非第一步，需求分析才是，這一點從給大家的 PSP 表格中也能看出來。分析一個題目就跟高中做閱讀理解一樣：

• 粗讀一遍，知曉題目背景，大概了解題目要求你做什么；
• 精讀一遍，理清題目的要求，需要提交內容的規范，題目的截止時間等等；
• 最后再細過一遍，確保沒有漏掉題目中任何一個有用的細節。

而本次測試中發現，約一半的同學在Github上的倉庫非常“自由”，并沒有按照指定的規范來。有的同學的畫風是這樣的：

還有同學的畫風是這樣的：

如今面對這樣的問題我也有了一些粗淺的認識：一定要把最希望學生認真讀完的部分放在博客的最開始，讓學生一點開博客就最先看到它。附加題，補充說明，參考鏈接等補充材料都放在后面，勤于思考的同學自然會去看。比如我在這個博客中所做的事情——把成績排行榜放在了最后 :)

Part2.被動測試

第二個問題則暴露出部分同學在工程測試上比較被動、依賴于助教的心理。每位同學個人項目得多少分與助教是沒有任何關系的，項目的得分只會影響自己的成績。換句話說，這次測試如果我直接以第一次自動測試的成績給大家評分，不給任何悔過的機會，這對我而言是沒有任何損失，還大大減輕了我的工作量。

但考慮到這是同學們在軟件工程課程里的第一次大展身手的機會，希望給大家悔過的機會是為了讓大家能從錯誤里吸取教訓，快速成長。但請記得，如果將來你做了一款需要靠用戶來找BUG的產品，那恐怕它上線沒多久就再也活不下去了。要主動，自己能夠把握的事情就不要讓它聽天由命，自由發揮。

Part3.需求權衡

第三個問題則是一個典型的權衡問題，問題同樣是出現在需求分析方面。從題目中的要求我們其實不難看到：

• 隨機生成N個不重復的已解答完畢的數獨棋盤，并輸出到sudoku.txt中。
• [2017.9.4 新增要求] 在生成數獨矩陣時，左上角的第一個數為：（學號后兩位相加）% 9 + 1。

題目明確提出了“不重復”“已解答完畢”“左上角數由學號確定”三點要求，它們也是題目的核心條件。而至于“10分鐘內生成100萬個數獨棋盤”，它是只作用于效率測試的，棋盤滿足前面三個條件下的額外約束。只有在滿足前面三個正確性條件下，效率測試才有意義。所以同學們在完成項目時，切忌“丟了西瓜撿芝麻”，要對需求功能的優先級排個序，按照重要程度逐一實現。

Part4.生成文件路徑問題

在測試同學們項目的過程中還出現了一個小插曲：有一部分同學認為題目中的“要確保 txt 文件和 exe 文件要在同個目錄下”是助教特意強調的，需要對exe的運行時路徑進行獲取從而生成 txt文件的生成路徑，其他直接使用 "./sudoku.txt" 路徑的做法是存在問題的。在這里必須表揚一下這些看起來較真的同學，同時我來解釋一下這個問題。

使用命令行測試exe文件有幾種方式：

理想化的測試環境：使用 cd 進入了 exe 所在的目錄，然后調用 exe 文件，生成了 txt 文件。操作如下圖

意想不到的測試環境：當前目錄并不是 exe 所在的目錄，使用相對路徑或絕對路徑調用 exe 文件，生成了 txt 文件。操作如下圖

在這里表揚這幾位同學并非是因為他們因此多得了分，因為這本來并非是測試的要點。實際上，更多要表揚的是他們這種敢于質疑的態度和考慮周全的細致。沒有哪個用戶能確保一定在合法環境下運行軟件，開發者可能要考慮更多的是在非法環境下如何做出同樣的效果，或者是給出合理的提示。

在正確性測試中有不少同學是通過迭代改進才修復好BUG的，這里推薦陳涵同學的作業：他的博客詳細地記載了修復BUG的過程，博客組織條理清晰，改進方法令人信服。博客最后所述通過構建之法得到的啟示讓我覺得非常欣慰，這才是真正學到了構建之法與軟件工程的內涵。鏈接：http://www.cnblogs.com/kobe961231/p/7492920.html。

效率測試

在項目的效率測試方面我對同學們的表現是比較滿意的，大部分同學在初個迭代版本后都有所改進。從我看過的項目與博客來看，改進多集中于三點：

• 從DEBUG到RELEASE模式
• 文件輸出
• 算法核心

第一個改進是最容易的，也就是讓BIN文件夾中用于測試的二進制文件使用RELEASE模式而非DEBUG模式生成。在這里大概說一下兩者的區別，學過編譯的同學應該知道編譯優化（包括循環優化，控制優化，活躍變量分析等），在DEBUG模式下編譯器是不會對程序做任何優化的，而RELEASE模式下則會對程序進行優化。與此同時，RELEASE模式下編譯速度會下降，部分變量被優化而不好調試。更感興趣的同學可以參看鏈接
DEBUG和RELEASE模式的區別。

第二個改進相信是大部分同學的選擇，畢竟改進文件輸出的效率要比改進算法要容易得多。常見的有兩種改進的手段：

• 改進前：生成一個數獨棋盤，就寫入一次文件。改進后：把生成的數獨棋盤保存在內存中，一次性寫入文件。
• 改進前：使用 ofstream 與 << 的格式寫入文件。改進后：使用 C 的函數 fwrite,fprint 或者是 puts 函數寫入文件。

第一種改進手段減少了文件打開與關閉的次數，同時讓緩沖區一直處于填滿狀態，從而加快效率。第二種手段則是因為 fwrite 等函數是 C 底層使用的基礎函數，而ofstream 是 C++ 引入的輸出流類。C++ 通過引入虛函數簡化了編程邏輯，提高了安全性，但也因為引入過多抽象層帶來了相應的性能開銷，所以會慢。

第三個改進需要動到算法的核心，在閱讀了同學們的代碼與博客后發現生成數獨的算法大多分為三種或它們的組合：

• 深度優先搜索與回溯
• 隨機產生與回溯
• 矩陣置換法

從同學們作業完成的情況來看：在小數據上，隨機產生與回溯的方法生成的多樣性要好，但要引入額外的重復性檢查方法。在大數據上，隨機產生方法基本不可行，剩下兩種方法中深度優先搜索的速度要比矩陣置換法快，能生成的數據也比較多。但矩陣置換法的優點在于充分利用了數獨游戲的規律，避免了試錯的檢驗過程。

在這里強烈推薦劉晨瑤同學的作業：效能分析能對程序改進起到多大的作用？從文件操作到算法改進，再到最后做實驗選擇合適的參數。不斷迭代帶來的巨大改進竟讓程序加速了100多倍！ 鏈接：http://www.cnblogs.com/thousfeet/p/7502211.html

錯誤處理

在題目要求中我特意提示了大家測試數據可能存在錯誤，但從結果來看大家的錯誤處理做得并不夠好。本次錯誤處理測試了5個參數：

• "-c"
• "-c -100"
• "-abc 1"
• ""(空參數)
• "-c -c 1"

大部分同學在錯誤處理部分都或多或少有程序崩潰的情況出現，也有很多同學在錯誤出現后沒有任何提示。這兩者都是需要開發者極力避免的，錯誤處理得越好，用戶體驗就越好。試想一下如果你開發了一款軟件，隨便輸入幾個非法指令就能把它搞崩潰的話，還會有用戶繼續用么？

在錯誤處理部分做得非常棒的是鄭浩輝同學，大家可以看看他的錯誤提示：
-【開始校驗參數】【校驗參數中】請輸入生成數量
-【開始校驗參數】【校驗參數中】生成數量只能是數字
-【未知指令】試試 -help ?
-【請輸入指令及相關參數】試試 -help ?
-【開始校驗參數】【校驗參數中】請勿輸入多余參數

鄭同學的博客排版非常棒，算法思路也很清晰，他也是本次成績排行榜的第一名，歡迎大家圍觀他的博客。鏈接：http://www.cnblogs.com/andwho/p/7500515.html

源代碼管理

可能因為不少同學都是初次接觸 Git 和 Github，在源代碼管理方面同學們普遍做得不好。源代碼管理評分方面的具體細則如下：

• commit的頻率與 message 中的信息。
• 項目倉庫是否提供了運行說明。
• 項目倉庫是否忽略了無用文件, 是否使用 gitignore 來忽略編譯生成的文件。
• 項目倉庫是否用了 dev/master 等分支功能實現不同版本的迭代更新。
• 項目倉庫是否使用 Pull Request 的方式發起，并有規范的 code review 環節。

部分同學在源代碼管理上得分為0或者1，主要是因為你們commit的次數少于2，或者大部分commit都是通過上傳文件的形式完成的。

范本Github使用記錄可以參考陳翔同學的博客：他的項目不僅有完整的運行說明，可讀的commit信息注釋，恰當的commit頻率，還配置了集成測試。這個簡直是一份完美的Github項目范例，推薦給各位同學。鏈接：http://www.cnblogs.com/qq952693358/p/7487056.html

博客成績明細

成績排行榜