1062 C++ 程式作業一

繳交時間
2A: 107/03/15 星期四 21:00
2B: 107/03/16 星期五 21:00

產生 n 個數字的所有排列 (Enumerate Permutations)

這個作業希望你用 C 語法, 用程序化的程式設計方法寫一個簡單的程式, 列印 {1,2,...,n} n個整數所有的排列, 產生排列的基本方法可以是 迭代式 (iterative) 或是 遞迴式 (recursive) 的, 在這次作業裡你必須把這兩種演算法都完成, 相互比較, 方式請參考 投影片 (4up) 裡的說明, 其中遞迴式的已經給你程式碼, 迭代式的程式需要和遞迴式的程式產生一模一樣順序的答案。

這個課程不是演算法的課程, 所以要求你寫的這個演算法並不需要最有效率的, 不過這個演算法有兩個特性, 第一是他需要運用相當的程式控制敘述, 第二是 Google 不太到 (你找到的應該都不是我要求的)

這個作業主要希望你能夠回憶一下 C 的語法, 回憶一下 C 程式的製作環境, 重新整理一下怎樣把一個演算法轉換為 C 程式的步驟, 怎樣逐步地設計, 測試, 和修改自己的程式, 並且熟悉一下這學期作業繳交的流程。

這個作業並不會特別困難, 但是要求每位同學自己獨立動手完成 (不是分組完成, demo 時是每一位同學自己 demo 自己的程式), 同時你需要達成下面的要求, 請注意除了程式的 "正確性" 之外, 另外還要求許多項目, 請趕快開始做, 不要最後因為時間不夠而胡亂繳交一份, 不好的開始通常不是成功的一半。

這個作業主要也是印證和練習 "撰寫程式時無形的規範 (b&w)", 請你拿簡單的 "產生 n 個數字排列" 的程式當作練習, 按照投影片中對於 Selection Sort 演算法的實作所作的逐步修改, 依樣畫葫蘆一番, 相信你更能夠了解設計程式時除了正確性以外一些比較形而上的要求, 嘗試去想像這些要求可能帶來的好處, 後續課程中還會逐步闡述這些要求代表的意義。

其次, 這個作業裡也希望你練習第一次以及第二次實習的 iostream/fstream 函式庫 的用法, 以及 assert 的使用

這次作業提示比較多, 大部分是過去學過的, 使得它比較像一個習題, 挑戰性會比較少, 除了上面談到希望你練習的, 其實也希望能夠透過這個作業建立一個與我、與助教溝通討論的管道, 程式課程的成績不太能夠客觀地代表程式設計和撰寫的能力, 但是程式設計的課程的確要求你透過實習/作業/以及課堂討論來建立自己的程式能力, 過了這個學期, 你有沒有建立起這種能力其實你自己是最清楚的, 希望你在這個時候能夠跳脫以前修課時讓考試被動催促的習慣, 主動參與這個課程, 如果你撰寫程式時遇見問題, 歡迎你隨時找我或是助教詢問, 上課後, 實習課, 補強教學, 電話, email, FB 訊息, ... 都可以運用, 我們這學期的課程中共同的目標是 - 讓你學到一些東西, 讓你對於程式設計有更多的想法。

 

本次作業目標:

  1. 複習 C 語言中各種流程控制: for, while, if, switch, 函式等等
  2. 請撰寫一個 迭代式 (iterative) 的程式來產生所有 n 個數字的排列, 並且將結果以文字模式存放在檔案中
  3. 練習 iostream/fstream 輸出入函式庫 (鍵盤,螢幕,檔案輸出及輸入)
  4. 練習以 "容易了解, 容易修改, 容易偵錯" 為基本目標來撰寫程式
  5. 練習運用 assert 加入確認假設與結果的程式碼

範例執行程式

程式要求

  1. 與程式執行者互動以及輸出資料檔案請使用 iostream (上課講義), fstream 函式庫 (上課講義) 來完成

  2. 請參考範例執行程式, 要求程式執行者輸入一整數以及一個輸出檔案名稱, 依照講義中指定的順序將所有的排列輸出至指定檔案中

  3. 根據 "撰寫程式時無形的規範 (b&w)", 希望你的程式滿足下列要求:

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

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

    3. 不要使用沒有名稱的常數 (例如 int data[100];, 應該要用 int data[DATASIZE];)

    4. 程式內大括號以及同一層的敘述請務必對齊 (程式檔案裡請使用 空格 字元而不要用 Tab 字元)

    5. 使用比較有限制的結構化語法 (重複次數已知時 for 迴圈比 while 迴圈好, 多選項時 switch 比 if 好, ...)

    6. 使用函式來組織你的程式, 讓程式中每一個區塊裡變數盡量減少, 邏輯上沒有關連的程式盡量分到不同的區塊或是不同的函式中, 函式不要太大 (以 30 列為平均值, 不要超過 50 列)

    7. 運用 assert 敘述建立自動驗證正確性的程式碼 (請練習把這些 assert 敘述的效果用前處理器常數 NDEBUG 一次去除)

      請確定所產生 排列的個數是否正確,
      請運用投影片中讓你練習的 遞迴 (recursive) 版本的結果來比對儲存在檔案中的結果的正確性

    8. 另外, 不要使用全域變數 (global variable) 在函式之間傳遞資料, 這是程序化程式設計時的大敵

作業繳交注意事項

  1. 請於時限內上傳程式以及文件檔案的壓縮包 (逾時無法上傳, 請預先測試你的帳號與密碼), 上傳網頁

  2. 請注意由於你對於 iostream, fstream 函式庫不是很熟悉, 所以你還是應該早點開始做, 請避免看到同學的程式碼, 由於程式功能已經做了很多的限制了, 如果你先看過別人的程式, 很難寫出和別人不一樣的東西...

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

  4. report.txt (或是 report.docx) 中請描述你的心得 (可以包括你覺得有幫助的觀念, 你 debug 時發現的問題, 你 debug 的心得, 你自己覺得比較好或是比較特別的設計...)

C++ 物件導向程式設計課程 首頁

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