Ch11 大數運算

# Ch11 大數運算 > 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/) > Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<\(\_ \_\)\> ## > 上一章：[字串處理](https://hackmd.io/s/BkcTlsvHM) > 下一章：[副函式與遞迴](https://hackmd.io/s/r1ewEfGqM) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## 應用：大數 ### 什麼是大數還記得我們曾經學過long long 它可以用來存到 9,223,372,036,854,775,807這麼大的數字那萬一需要比這個數字更大的數字怎麼辦例如20位、100位、1000位這種數字就算是用了long long也沒有用的這種連long long都無法存的數字，我們就稱作「大數」 ## 出現大數時，要怎麼辦 有些題目就是特別邪惡給你的數字會大到用long long都存不下但是我們自有辦法！雖然long long 無法存大數但是string總可以吧！把那個大數當成一串數字串就好了 1000個字對string來說一點都不長所以當題目給的數字超過long long可存範圍時我們就要把熟悉的 ```cpp int n; cin >> n; 或 long long n; cin >> n; ``` 改成 ```cpp string n; cin >> n; ``` 但是，存進來以後卻不能直接用string做運算要記得現在已經把那串數字當成一句字串存進來了他現在根本不是數字了你可以執行看看下列這段程式你會發現結果根本不會是你想要的 ```cpp= string a = "100" ; string b = "200" ; cout << a+b ; ``` 編譯成功的話會出現100200，絕不會出現你期望中的300 ## 大數運算：一步一步直式加法 如果想要對大數做加減乘除，我們還是有辦法做到的！ int和long long的運算就像按計算機一樣直接輸入之後就能跑出結果大數的運算就像人類用手算一樣要從最低位數一步一步相加進位，把每一位都算出來 【例題】 > 輸入兩個數，a與b > 其中a和b都至多有20位 > 輸出a和b相加後的結果為了方便，先將讀進來的大數存進陣列裡吧陣列要開多大呢？先看看題目，題目表示a和b都至多有20位可以知道a+b至多是21位 (為什麼？) 那就開個25格的陣列吧~ (多開幾格沒關係，少開就no no no囉) 並且用兩個字串將a與b讀進來 ```cpp= int na[25]; int nb[25]; int sum[25]; string a; string b; cin >> a; cin >> b; ``` 首先要把陣列裡的數值都先手動歸零千萬要記得：宣告陣列之後，裡面格子的數值不會自動是零而是會有任何可能的數字哦！ ```cpp=10 for(i=0;i<25;i++){ na[i]=0; nb[i]=0; sum[i]=0; } ``` 接下來要做的是把a和b都分別把每一位拆開，存入陣列中的每一格裡例如： a的數字是168的話，就要在na[0]中存入8 在na[1]中存入6 在na[2]中存入1 b的數字是5566的話就要在nb[0]中存入6 在nb[1]中存入6 在nb[2]中存入5 在nb[3]中存入5 之所以要把數字反過來是因為希望讓個位數在陣列的第0格十位數在陣列的第1格以此類推所以168和5566存進陣列裡會變這樣 8610000000000000000000000 和 6655000000000000000000000 相加完輸出時再反過來輸出先將a與b反轉 ```cpp= string a_reverse = a; for(int i=0;i<len_a/2;i++){ swap(a_reverse[i], a_reverse[len_a-1-i]); } string b_reverse = b; for(int i=0;i<len_b/2;i++){ swap(b_reverse[i], b_reverse[len_b-1-i]); } ``` 再來就可以把反轉後的字串裡面的數字存進陣列裡了 ```cpp= for(i=0;i<len_a;i++){ na[i]=reverse_a[i]-'0'; } for(i=0;i<len_b;i++){ nb[i]=reverse_b[i]-'0'; } ``` 記得喔字元都要減掉`'0'`之後才是他字元所代表的數字讀進來之後就可以一步一步相加拉剛才是把個位數存在陣列的第0格，十位數在第1格.... 我們手算直式加法時也是從個位數開始加所以我們讓迴圈也從第0格開始 ```cpp=22 for(i=0;i<25;i++){ sum[i]=na[i]+nb[i]; } ``` 不過這樣還沒有完成喔萬一na[i]+nb[i]大於等於10 要記得處理進位的問題喔我們用carry這個變數來表示他的前一位有沒有進位(帶1上來) 最一開始個位數相加的時候一定沒有前一位帶來的進位所以可以先讓 carry = 0 ```cpp=25 int carry = 0; for(i=0;i<25;i++){ sum[i]=na[i]+nb[i]+carry; if(sum[i]>=10){ sum[i]-=10; carry=1; } else carry=0; } ``` 這麼一來sum這個陣列裡就會有算完的結果了以168+5566的例子 (結果會是5734) sum這個陣列中的結果會是 4375000000000000000000000 那麼再把他倒過來輸出吧先找到他的第一位在哪裡 ```cpp=34 for(i=24;i>=0;i--){ if(sum[i]!=0){ start=i; break; } } ``` 從他的第一位開始印出數字 ```cpp=40 for(i=start;i>=0;i--){ cout<<sum[i]; } ``` > 【學生練習題】 > - [ ] [Green Judge b016: 螞蟻雄兵 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b016) 看清楚題目喔！他不只20位而已！ ## 大數運算：一步一步直式乘法 這個題型的做法跟加法很像一樣是用 string 讀進來之後一個字一個字倒過來存進陣列裡差別在於運算的細節不同還有答案的陣列大小不一樣如果 a 和 b 都至多20位的話，那 a+b 至多21位而 a\*b 則是至多40位喔！ (為什麼？) 接下來回想一下直式乘法是怎麼做的吧在a\*b的乘法裡首先我們會拿b的個位數去乘以a 從a的個位數開始往a的高位乘過去並且隨時記錄進位的值接下來會拿b的十位數去乘以a 且結果會寫在往左邊移一格的位置 . . 一直到b的每一位數都乘完a為止程式也用一樣的方法吧由於乘法結果的每一位數都會是好幾個數字相加所以一開始要讓每一格都先歸零之後加上數字時就可以直接加上去 ```cpp= for(i=0;i<40;i++) product[i]=0; //如果a和b都是20位數的話，那乘積至多是40位數喔 ``` ```cpp=3 for(ib=0;ib<25;ib++){ for(ia=0;ia<25;ia++){ product[ib+ia] += nb[ib]*na[ia]; } } ``` 數字b的第ib位和數字a的第ia位相乘後的結果會被存在第(ib+ia)位請仔細想想為什麼但這也是還沒完成的形式喔要記得進位的問題如果相乘之後超過10了，就必須只留下個位的部分，讓十位去進位喔 ```cpp=8 for(ib=0;ib<25;ib++){ for(ia=0;ia<25;ia++){ product[ib+ia] += nb[ib]*na[ia]; if(product[ib+ia]>=10){ product[ib+ia+1] += product[ib+ia]/10; product[ib+ia] = product[ib+ia]%10; } } } ``` 最後一樣從最高位依序輸出就好 ```cpp=17 for(i=40;i>=0;i--){ if(product[i]!=0){ start=i; break; } } for(i=start;i>=0;i--){ cout<<product[i]; } ``` > 【學生練習題】 > - [ ] [Green Judge b017: 奈米科技 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b017) ## > 上一章：[字串處理](https://hackmd.io/s/BkcTlsvHM) > 下一章：[副函式與遞迴](https://hackmd.io/s/r1ewEfGqM) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)