大整數(shù)乘法
上一期(高精度加法)
今天我們來研討一下高精度乘法卸伞。
題目描述:
將兩個(gè)大整數(shù)(最多100位)相乘,輸出結(jié)果锉屈。
輸入樣例:
123456789
987654321
輸出樣例:
121932631112635269
代碼(想粘走的就粘走):
#include<iostream>
#include<string>
using namespace std;
int main(){
string as,bs;
int an[101]={0},bn[101]={0},c[10200]={0},aLen,bLen,cLen;
cin>>as>>bs;
aLen=as.length();
bLen=bs.length();
//倒序存儲(chǔ)兩個(gè)數(shù)于整型數(shù)組中
for(int i=0;i<aLen;i++){
an[aLen-i-1]=as[i]-'0';
}
for(int i=0;i<bLen;i++){
bn[bLen-i-1]=bs[i]-'0';
}
//進(jìn)行乘法運(yùn)算荤傲,結(jié)果存于c[]
for(int i=0;i<bLen;i++){
for(int j=0;j<aLen;j++){
c[i+j]+=an[j]*bn[i];
c[i+j+1]+=c[i+j]/10;
c[i+j]%=10;
}
}
cLen=aLen+bLen;
//刪除結(jié)果高位的前綴0
while(c[cLen-1]==0 && cLen>1){
cLen--;
}
//將結(jié)果倒序輸出
for(int i=cLen-1;i>=0;i--){
cout<<c[i];
}
cout<<endl;
return 0;
}
乘法原理:
關(guān)鍵點(diǎn)分析
1.核心代碼(乘法運(yùn)算部分)是由模擬乘法豎式算出來的:
(1) 數(shù)1的倒數(shù)第i位與數(shù)2的倒數(shù)第j位相乘所得到的值應(yīng)存在結(jié)果的倒數(shù)第i+j位上。
(2) 如果結(jié)果的i+j位大于9部念,則進(jìn)位到i+j+1位弃酌。
c[i+j]+=an[j]*bn[i];
c[i+j+1]+=c[i+j]/10;
c[i+j]%=10;
i位數(shù) 與 j位數(shù) 相乘,其結(jié)果最多為 i+j 位儡炼。
要注意結(jié)果前綴中的0以及結(jié)果為0的情況妓湘。
while(c[cLen-1]==0 && cLen>1){
cLen--;
}
測(cè)試樣例
輸入樣例1
999
99
輸出樣例1
98901
輸入樣例2
00999
00000099
輸出樣例2
98901
輸入樣例3
98765432123456789
0
輸出樣例3
0
有人說:“編寫文章20%的內(nèi)容就可獲得80%的進(jìn)度”,那么乌询,下一期榜贴,你能不能找出那20%?妹田,我在高精度除法的世界中等你唬党!