952 (due 96/04/10) C++ 程式作業一：大整數 類別設計

這是個暖身的作業, 所以我的說明比較多, 另外這個作業和實習裡的複數類別的設計也有很多相似點, 按部就班地作應該不會太困難, 雖然這比較像一個習題, 挑戰性稍微少了一點, 不過還是可以練習許多必備的 C++ 語法與程式設計, 事實上要寫的東西很多, 會遇見的錯誤也絕對無法預期, 請提早寫, 否則一定寫不完。

這三個學分的課程中作業佔的比例很高, 在我的理念裡如果你不幸考試考得不好, 但是你能夠說服我作業和實習的題目自己可以完成, 那我就沒有理由當你, 但是如果你考試成績不佳, 作業缺交或是抄襲, 那就很難讓你過, 主要的目的是希望你不是只會紙上談兵, 看得懂部份的程式, 會修改程式, 但是卻不會設計程式, 很多時候軟體系統的運作原理是和程式設計習習相關的, 不會設計程式, 你就很難體會軟體系統的運作方法、長處與限制。

請千萬不要放棄這些作業, 萬一最後你只完成了部份, 還是建議你連同設計還有偵錯時的心得一起交過來, 唯一不需要交過來的是別人的作業, 如果你撰寫時遇見問題, 歡迎你隨時找我詢問, 上課後, 實習課, 電話, email, msn... 都可以運用, 當然這也是說服我 - 你的確付出努力去完成這個作業 - 最直接的辦法。

大整數 類別設計

1. 請使用多個 .h, .cpp 檔案來分割你的程式模組
2. 練習各種流程控制： for, while, if, switch, 函式等等,
3. 練習基礎的類別語法
4. 練習類別界面函式的設計
5. 練習 function overloading
6. 練習使用參考變數來傳遞資料到函式內
7. 練習使用 new 與 delete 配置記憶體
8. 練習使用 const 型態的函式參數
9. 使用自定類別產生物件
10. 練習 bottom-up 的程式設計方法
11. 練習使用 string 類別物件

請下載範例執行程式 BigInteger1.exe, BigInteger1d.exe (列印 n1! 與 (n1!)^n2) 並請參考執行結果

程式基本要求

由於在 C/C++ 中整數最大可以用 4 個位元組來表示, 範圍在 2³¹-1 到 -2³¹ 之間, 超過這個範圍就沒有辦法表示了, 這個意思是說如果你的存款不幸超過這個範圍, 銀行就會不斷出錯; 在資料加密的應用裡也會有很多需要使用到大的整數的地方, 難道電腦就不能處理了嗎?

在這個作業中我們希望製作一個 "大整數" 的類別, 希望能夠處理正負數, 任意位數的整數 (測試至少十進位 500 位數) (如果可以的話也希望儲存一個數字不要太浪費記憶體)

對於一個這樣子的物件來說, 必須提供一些基本的功能, 例如: 加法, 減法, 乘法, 除法, 餘數, 相等, 大於, 小於, 設定, 列印, 拷貝 等等, 請製作一個 "BigInteger" 的類別來處理這樣的資料

1. 希望能夠處理正負數, 任意位數的整數 (測試至少十進位 500 位數) (如果可以的話也希望儲存一個數字不要太浪費記憶體)

   實際上在存放一個很大的整數時, 你可以用字元陣列來存放十進位數字, 每一個位數一個字元; 或是也可以用整數陣列來存放十進位數字, 每一個位數用一個整數來存放; 或是你想要用比較節省記憶體的方式存放, 用整數陣列, 但是每一個整數基本上存放 32 個位元, 當然這樣子存放 的話在運算上會比較麻煩; 或是你想用 字元串列 來存放十進位數字, 每一個位數一個字元, 這樣子在這個物件的數字變大的時候會比較節省時間; 你也可以考慮用標準 C++ 函式庫裡的 vector 或是 list 來存放資料...

2. 請撰寫設定大整數物件內容的成員函式, 包括以十進位或是十六進位方式來設定:
   • bool BigInteger::setValue(int value);
   • bool BigInteger::setValue(string str, bool hex=false);

   這兩個成員函式需要把傳進來的資料轉變為內部資料的存放格式, 如果是第二個版本的話, 第二個參數代表前面的字串是以十六進位或是十進位表示的, 並且需要檢查傳進來的資料是否合法 (十進位的話只能出現 0 到 9, 十六進位的話還可以出現 ABCDEF), 請注意如果原先自己這個物件內有任何舊的資料的話都要清除掉, 如果設定失敗的話, 應該要傳回 false, 反之成功的話就傳回 true, 另外這兩個成員函式應該是一個 public 的界面函式。

3. 請替這個類別寫一個成員函式 print(ostream &, bool hex), 將整數的內容以十進位或是十六進位格式在螢幕上列印出來, 例如:

       -12345678901234556789 或是 12ACD0A54D

   這個函式請傳入一個螢幕輸出資料串流 ostream 的參考參數, 傳入一個有預設值的旗標來表示使用者希望輸出十進位或是十六進位數值, 不需要回傳任何數值, 也不會更改物件的內容。

4. 請替這個類別寫一個比對兩個物件是否相等的成員函式: 這個函式傳入一個 BigInteger 物件的參考, 請檢查這個傳入的物件的數值是否等於自己這個物件的數值, 並且傳回一個 bool 型態的結果。

   請注意在這個運算裡不論是傳入的物件或是自己這個物件的內容維持不變, 請用 const 敘述保證這 兩件 事情。

   請特別注意如果傳入的物件根本就是自己這個物件的話, 要傳回 true 的結果, 有了這樣的設計也一定要在 unitTest() 函式中加入適當的測試。 你可以運用下列的敘述檢查傳入的物件是否等於自己:

         if (this == &secondObject)
         ...

   其中 this 為一個保留字, 在成員函式內使用的時候代表那個物件自己的記憶體位址。

5. 請撰寫一個 static 的成員函式 BigInteger::unitTest(), 在這個函式中運用 assert() 替下面所有逐步增加的功能都撰寫單元測試的程式碼, 每寫完一個功能就進行部份的測試, 實際上很可能你在設計一個成員函式的功能之前就先要設計如何測試, 如此在持續不斷地修改程式與不斷地新增程式功能的過程中, 你可以逐步的測試所有增加的功能, 並且確保增加新的功能時, 已經測試過的功能都維持正確, 請參考實習 1-2 以及 3-1, 在製作這個 BigInteger 類別的過程中, 主程式裡可以如下呼叫單元測試的函式:

   	BigInteger::unitTest();

6. 請撰寫一個拷貝大整數物件內容的成員函式:
   void BigInteger::clone(BigInteger &original);

   這個函式會讀取 original 物件內的資料, 並且拷貝在自己這個物件內, 如果自己這個物件內原先有資料的話, 會先清除然後再拷貝。

7. 接下來要替這個大整數類別 BigInteger 寫下面的成員函式, 這是這種類別的物件所需要提供給其它類別物件的服務:

   • 加法 (add): 這個函式傳入一個 BigInteger 物件的參考, 請計算自己這個 BigInteger 物件加上傳入的 BigInteger 物件後的數值, 並且將物件內容更改為算出來的結果 (如果你自己配置記憶體的話, 此時常常需要重新配置更多的記憶體)。

   • 減法 (sub): 這個函式傳入一個 BigInteger 物件的參考, 請計算自己這個 BigInteger 物件減掉傳入的 BigInteger 物件後的數值, 並且將物件內容更改為算出來的結果 (如果你自己配置記憶體的話, 此時常常需要重新配置記憶體)。

   • 乘法 (mul): 這個函式傳入一個 BigInteger 物件的參考, 請計算自己這個 BigInteger 物件乘上傳入的 BigInteger 物件後的數值, 並且將物件內容更改為算出來的結果 (如果你自己配置記憶體的話, 此時常常需要重新配置較大的記憶體)。

   • 除法 (div): 這個函式傳入一個 BigInteger 物件的參考, 請計算自己這個 BigInteger 物件除以傳入的 BigInteger 物件的數值, 並且將物件內容更改為算出來的商, 請注意這是整數的除法, 例如 14 除以 3 得到商是 4 餘數是2, 如果除數是 0 的話應該回傳一個失敗的訊息, 所以這個成員函式的回傳值設計為 bool, 另外你也可以多增加一個餘數的參數, 將計算出來的餘數傳回來。

   • 餘數 (mod): 這個函式傳入一個 BigInteger 物件的參考, 請計算自己這個 BigInteger 物件除以傳入的 BigInteger 物件的數值的餘數, 並將物件內容更改為算出來的餘數。

   • 大於: 這個函式傳入一個 BigInteger 物件的參考, 請檢查這個傳入的物件的數值是否大於自己這個物件的數值, 並且傳回一個 bool 型態的結果。

     請注意在這個運算裡不論是傳入的物件或是自己這個物件的內容維持不變, 請用 const 敘述保證這 兩件 事情。

     請特別注意如果傳入的物件根本就是自己這個物件的話, 要傳回 false 的結果。

   • 小於: 這個函式傳入一個 BigInteger 物件的參考, 請檢查這個傳入的物件的數值是否小於自己這個物件的數值, 並且傳回一個 bool 型態的結果。

     請注意在這個運算裡不論是傳入的物件或是自己這個物件的內容維持不變, 請用 const 敘述保證這 兩件 事情。

     請特別注意如果傳入的物件根本就是自己這個物件的話, 要傳回 false 的結果。 當然這個函式應該運用上面的大於函式來實作。

   • 其它你自己想到和大整數類別相關的函式, 例如上述加減乘除函式的參數如果是 int 的話, ... 如果你有製作的話, 記得在心得裡面提到, 可以酌量加分。

8. 請參考 實習內容 擴充 iostream 輸入輸出函式庫, 運用先前製作的 print() 函式來以十進位格式輸出這個類別的物件到任何資料串流 ostream, 使 得程式裡可以運用下列的敘述:

     BigInteger x;
     ofstream outfile("TestOutput.txt");
     ...
     cout << x;
     outfile << x;

9. 請擴充 iostream 輸入輸出函式庫,由資料串流 (例如 cin) 中讀取一個十進位的大整數, 利用 setValue 成員函式存放到 BigInteger 類別的物件中, 使得程式裡可以運用下列的敘述:

     BigInteger x;
     ...
     cin >> x;

10. 請注意單元測試函式 unitTest() 裡至少要運用 assert 敘述測試下列

        a. 記憶體錯誤檢查
        b. 任意位數 (1-500位以上)
        c. 加法 (驗證進位, 正+正, 正+負,負+負)
        d. 減法 (驗證借位, 正-正, 正-負,負-負)
        e. 乘法 (驗證 正*正, 正*負,負*負, 乘 0)
        f. 除法 (驗證 正/正, 正/負,負/負, 除數為 0)
        g. 餘數 (驗證 正mod正, 正mod負,負mod負, 除數為 0)
        h. 大於
        i. 小於
        j. 輸出到一個暫時的檔案
        k. 由檔案中讀資料回來 

    如果你在設計這個類別的過程裡有撰寫其它輔助用的成員函式的話, 也應該在這裡對每一個功能加上測試的程式碼。

11. 主程式: (請參考範例執行程式 BigInterger1.exe及 BigInteger1d.exe (列印 n1! 與 (n1!)^n2) 執行記錄)

        請由鍵盤讀入三個數字 n1, n2, n3
        將此數字存放在 BigInteger 類別的物件裡
        請利用 BigInteger 的功能來計算下列運算式
            ((n1 !)n2 - n1 / n2 ) mod n3
        並且將結果列印在螢幕上 

其他注意事項:

1. 撰寫程式的時候由於你還不是很熟悉 C++ 的語法, 最好是寫一點點就編譯一下, 才不會一直等到寫完了以後發現錯誤很多, 不知道怎樣開始修改。

2. 請注意變數的命名和函式的命名不可太短, 要有意義

3. 各個函式的功能盡量不要重複, 可以盡量用已經設計好的功能來組合成新的功能, 例如: 減法的功能應該可以用加法的功能來完成, 這 樣子可以減少程式維護的困難 (如果你的程式裡相同的一段敘述重複很多次的話, 萬一有一天你要修改這段程式, 或是發現這段程式裡有錯, 會發現到處都有這樣的錯, 在修改的時候很容易就遺漏了一些地方, 也就留下了很難尋找的 bug)

進一步增加程式的功能

原則上你想要增加什麼功能都是可以的, 記得在心得中寫出來, 這樣我才會注意到, 也才能夠幫你加一些分數, 現在程式還簡單, 你應該有辦法增加功能或是基於這個類別做一些好玩的應用。

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

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