Ch11 大數運算

搭配green judge解題系統
Special thanks to 台中女中sagit老師 <(_ _)>

上一章：字串處理
下一章：副函式與遞迴
回目錄：國立科學園區實驗中學C++程式語言自學講義

應用：大數

什麼是大數

還記得我們曾經學過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可存範圍時
我們就要把熟悉的

int n;
cin >> n;

或

long long n;
cin >> n;

改成

string n;
cin >> n;

但是，存進來以後
卻不能直接用string做運算
要記得現在已經把那串數字當成一句字串存進來了
他現在根本不是數字了

你可以執行看看下列這段程式
你會發現結果根本不會是你想要的

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讀進來

int na[25];
int nb[25];
int sum[25];

string a;
string b;

cin >> a;
cin >> b;

首先要把陣列裡的數值都先手動歸零
千萬要記得：
宣告陣列之後，裡面格子的數值不會自動是零
而是會有任何可能的數字哦！

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反轉

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]);
}

再來就可以把反轉後的字串裡面的數字存進陣列裡了

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格開始

for(i=0;i<25;i++){
    sum[i]=na[i]+nb[i];
}

不過這樣還沒有完成喔
萬一na[i]+nb[i]大於等於10
要記得處理進位的問題喔

我們用carry這個變數來表示他的前一位有沒有進位(帶1上來)

最一開始個位數相加的時候一定沒有前一位帶來的進位
所以可以先讓 carry = 0

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
那麼再把他倒過來輸出吧

先找到他的第一位在哪裡

for(i=24;i>=0;i--){
    if(sum[i]!=0){
        start=i;
        break;
    }
}

從他的第一位開始印出數字

for(i=start;i>=0;i--){
    cout<<sum[i];
}

【學生練習題】

• Green Judge b016: 螞蟻雄兵

看清楚題目喔！他不只20位而已！

大數運算：一步一步直式乘法

這個題型的做法跟加法很像
一樣是用 string 讀進來之後
一個字一個字倒過來存進陣列裡
差別在於運算的細節不同
還有答案的陣列大小不一樣

如果 a 和 b 都至多20位的話，那 a+b 至多21位
而 a*b 則是至多40位喔！ (為什麼？)

接下來回想一下直式乘法是怎麼做的吧

在a*b的乘法裡
首先我們會拿b的個位數去乘以a
從a的個位數開始往a的高位乘過去
並且隨時記錄進位的值
接下來會拿b的十位數去乘以a
且結果會寫在往左邊移一格的位置
.
.
一直到b的每一位數都乘完a為止

程式也用一樣的方法吧
由於乘法結果的每一位數都會是好幾個數字相加
所以一開始要讓每一格都先歸零
之後加上數字時就可以直接加上去

for(i=0;i<40;i++) product[i]=0;
//如果a和b都是20位數的話，那乘積至多是40位數喔

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了，就必須只留下個位的部分，讓十位去進位喔

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;
        }
    }
}

最後一樣從最高位依序輸出就好

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: 奈米科技

上一章：字串處理
下一章：副函式與遞迴
回目錄：國立科學園區實驗中學C++程式語言自學講義