1052 C++ 程式作業一:
大整數加減乘除

繳交時間: 106/03/09 星期四 21:00

前面三個學期學了程式設計資料結構演算法,在進入物件的世界之前、在擴大自己撰寫的程式規模之前,先用這個作業回憶一下變數、迴圈、陣列、結構、動態記憶體配置、以及函式的語法,練習一下程式設計、測試、與修正的步驟。大整數的加減乘除的動作在 C/C++ 中基本上沒有現成可以用的工具,如果不要求效率的話,也不需要特別的演算法,就是實作你平常手動計算加減乘除的步驟而已,如果你希望有比較簡單的大整數拷貝的話,可以用結構的語法來設計存放資料的基礎單元;實際上如何運用陣列儲存一個大整數資料和寫出來的程式容不容易看得懂有很大的關係, 此外也可以作一些調整來減少存放每一個大整數所需要的記憶體。

大整數

這個作業希望大家寫的程式就是處理整數以及它們的基礎運算而已, 但是程式需要能夠處理到十進位 100 位數的整數, 這樣子的機制在金融系統中處理鉅額的款項時需要用到, 在密碼學裡也用得非常頻繁,在競賽程式裡也會看到很多需要使用大整數來計算的問題。

這裡要求的大整數不能夠用 C/C++ 裡的 short, long, int, long long, double, 甚至 long double 型態來表示, 因為 short, long, int, long long 型態能夠存放的資料都有大小的上限,分別是 65536, ~4.1*109, ~1.8*1019,不能夠表示更大的數字了, 而 double 類型雖然可以表示到 10308 的數字, 但是在表示這樣的數字時卻有大約 10290 的誤差, 這樣的誤差在上面很多應用程式中沒有辦法容忍的。

因此你必須設計資料結構來表示一個大的整數, 例如用字元陣列或是整數陣列來表示,每一個元素儲存十進位的一個位數 (當然也可以是其它進位制,也可以存放不只一位數),也需要表達數字的正負號,也需要實作你所熟悉的整數加減乘除的動作。

這個程式希望大家能夠練習下列:

  1. 請將 VC 2010 安裝好, 練習一下運用它的介面撰寫程式

  2. 陣列、條件判斷、迴圈、動態記憶體配置、結構、函式、與函式參數的傳遞

  3. 整數加減乘除的演算法主要就是實作你手動計算時的直式運算方法

  4. 練習使用 assert() 撰寫單元測試

程式基本要求

  1. 需要處理 1-10100 ~ 10100-1 範圍內的正整數 , 能夠以十進位的方式讀/寫數字

  2. 需要處理下列的運算
    1. 兩個大整數 a, b 的加法 a+b
    2. 兩個大整數 a, b 的減法 a-b
    3. 兩個大整數 a, b 的乘法 a*b
    4. 兩個大整數 a, b 的除法 a/b
    5. 兩個大整數 a, b 的比較大小 a==b 或是 a<b

  3. 輸入與輸出:
    1. 下面是程式的執行範例:
        > 12345678901234567890-23084753209485940893245893245
        -23084753197140261992011325355
        > 0010834589324583253 + 12121212123
        10834601445795376
        > 23455428* 12456789
        292179317500692
        > 9879834343  / 212146
        46570 195123
        > 2468246824==2468246824
        1
        > 2468246824 == 2468346824
        0 > 2468246824<2468246124 0 > quit 藍字部份是使用者輸入的,除法的答案中前面是商後面是餘數,+ - * / == 的前後可以有空格或是沒有空格,測試相等或是大小時輸出 1 代表關係正確,0 代表錯誤
    2. 為了簡化起見, 輸入的數字一律都是正數 (不需要考慮 1- -1, -1 * -5 等等)
      如果計算結果超過可以表示的範圍, 請輸出 NAN 的結果

基礎要求,不符合以下要求的話請不要繳交過來

  1. 請不要使用全域 (global) 的變數

  2. 請運用函式適當地切割程式,不可以只有一個 main 函式

  3. 請使用 free/malloc動態配置儲存資料的陣列 (不要使用 gcc/g++ 的 variable length array), 例如一個十進位 30 位數的數字,請使用剛剛好大小的陣列來存放,不要使用過大的陣列存放

  4. 請儘量以 const 約束函式對於參數的行為

  5. 請把程式分成兩個檔案

  6. 使用 assert() 函式針對你自己寫的函式建構單元測試, 並且在書面報告上說明你設計了哪些測試

  7. 請參考 Disciplined Coding Style 講義, 對你的程式進行下列的要求:

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

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

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

    4. 程式排版請務必對齊 (同一層的敘述一定要對齊,不要使用 TAB 字元在你的程式裡)

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

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

  8. 繳交的程式需要跟助教 demo,需要解釋助教指定的程式功能,所以請你一定不要繳交不是自己做出來的程式,當然只解釋程式的來源是不夠的,要解釋程式裡相關設計的原因

進一步增加程式功能:

以下僅為建議功能, 你自己增加的功能請在書面報告中註明以便評分參考

  1. 撰寫函式以一個 int 整數或是 long long 整數設定你的大整數

  2. 計算最大公因數以及最小公倍數

  3. 計算指數 xy, 其中 x 為大整數, y 則可以為大整數或是 int / long long 的整數

  4. 輸出輸入時資料進位制的改變 (例如: 8 進位或是 16 進位列印)

  5. 運用 memory_leak檢查是否有記憶體遺失 (memory leakage)

  6. 其它你自己想到的功能

 

作業繳交要求

 

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

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

html>