962 C++ 程式作業一 (due 97/03/10 24:00) ：Quick Sort 程式的工程化版本

這是個暖身的作業, 不能算是演算法的作業 (太容易了一點), 這個作業主要是呼應我們在課堂裡討論的 "撰寫程式時無形的規範 (b&w)", 就請你拿簡單的 Quick Sort 演算法當作範例, 按照我們課堂裡對於 Selection Sort 演算法的實作所作的逐步修改, 依樣畫葫蘆一番, 相信你更能夠了解寫程式時一些比較形而上的要求。

雖然實際上這次作業比較像一個習題, 挑戰性稍微少了一點, 不過還是可以複習一下必備的 C 語法與程式設計, 如果你撰寫時遇見問題, 歡迎你隨時找我詢問, 上課後, 實習課, 電話, email, msn... 都可以運用 (當然這也是說服我 - 你的確付出努力去完成這個作業 - 最直接的辦法)。

Quick Sort 的工程化版本

1. 複習 C 中各種流程控制： for, while, if, switch, 函式, 文字檔案讀取等等

2. 練習撰寫以 "容易了解" 為目標的工程化程式

這個作業不提供範例執行程式, 不過針對程式執行的正確性, 還是需要你測試一些資料, 下面是兩組基本的測試資料

1. data1.dat
2. data2.dat

程式要求

1. 資料檔案第一列為此檔案中浮點資料的個數, 第二列以後每一列為一個浮點數的資料, 請由檔案中讀取資料至陣列中, 以你自己撰寫的 QuickSort 程式將資料由小至大排序之後, 計算數字的間距的平方和, 例如檔案中資料為

       3    
       1.5
       3.1
       0.8
       

   由小至大排序以後應該是

       0.8
       1.5
       3.1
       

   請計算 (1.5-0.8)*(1.5-0.8) + (3.1-1.5)*(3.1-1.5) = 3.05 並列印出來

2. 根據上課講義, 請你對你的程式進行下列的要求:

   1. 去除不需要的指標運算 (能夠使用陣列語法的盡量使用)

   2. 使用有意義的變數名稱

   3. 使用比較有限制的結構化語法 (for 迴圈比 while 迴圈好, if 比 goto 好, ...)

   4. 使用函式來組織你的程式, 同時讓程式中每一個區塊裡變數盡量減少, 邏輯上沒有關連的程式盡量分到不同的區塊或是不同的函式中

   5. 請畫一張圖代表此演算法高階概念上的作法

   6. 請撰寫一個遞迴版本的 Quicksort 程式

   7. 請運用 assert 敘述加上自動測試正確性的程式碼

   8. 請比較一下各個程式版本執行檔案的大小

作業繳交注意事項

1. 請於時限內 (97/03/10 24:00) 上傳程式檔案 (逾時無法上傳, 請預先測試你的帳號與密碼), 上傳網頁

2. 如果你像講義裡做的一樣有多個版本的話, 請編輯一個 readme.txt (或是 readme.doc) 檔案, 說明每一個版本的差別

3. 請編輯一個 report.txt (或是 report.doc) 檔案, 說明你的演算法高階的模型, 概念上的作法, 資料結構, 你所完成的功能, ... 以及對於此次作業各個部份的問題? (提出問題時請盡量整理你所知道的, 與你所懷疑的, 你所不認同的..., 如此會比空洞的 "我不懂 xxx?", "yyy 是什麼?" 要容易回答, 相對的你也比較容易得到你想要的答案)

4. report.txt (或是 report.doc) 中請說明你的心得 (心得可以包括你覺得你獲得的觀念, 你 debug 時發現的問題, 你 debug 的心得, 作業的感想 ...)

回 C++ 程式設計課程 首頁

製作日期: 02/25/2008 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@cs.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 工學院 資訊工程系 Lagoon