柚子快報激活碼778899分享：大數(shù)加法-藍橋杯

http://yzkb.51969.com/

lanqiaoOJ題號1516

【題?描述】輸?兩個整數(shù)a和b，輸出這兩個整數(shù)的和。a和b 都不超過100位。

本題和下?題介紹計算?數(shù)的乘法和加法。在C/C++中，?數(shù)的 計算?法稱為?精度算法，是常?的考題。?使?Python和 Java代碼能直接計算?數(shù)，不需要??精度算法。

C++的數(shù)據(jù)類型中，最?的long long類型，可以聲明64位的? 進制數(shù)變量。此題的關鍵是處理?數(shù)的輸?，因為整數(shù)a和b太 ?，?法將其直接賦值給C++的變量，所以不能按數(shù)字讀?，只 能按字符讀?。 ?數(shù)a?字符串來存儲，?個字符存儲?位數(shù)字，a[0]存最?位 數(shù)字，a[1]存次?位數(shù)字……a[n?1]存最低位數(shù)字，等等。計算a 加上b，先模擬每?位相加，再處理進位。

//1計算大整數(shù)加法

string bigint_add(string a,string b){//a,b數(shù)字字符串中的低位在前

string s,st;

int temp=0;//用來存儲可能產(chǎn)生的進位

for(int i=a.size()-1,j=b.size()-1;i>=0||j>=0||temp>0;i--,j--){//倒序遍歷,注意這里temp不為0也要循環(huán)一次

if(i>=0) temp+=a[i]-'0';

if(j>=0) temp+=b[j]-'0';

st=temp%10+'0';

s=st+s;//新加入的高位放在 s 前面，保證輸出不會反

temp=temp/10;

}

// reverse(s.begin(),s.end());

return s;

}

1利用循環(huán)條件巧妙的解決了相加的大整數(shù)長度不一樣的情況，另外注意temp>0也需要進入循環(huán)。

2temp賦值之前要判斷一下避免越界，結果字符串記得要倒序，s=st+s可以把新獲得的數(shù)直接加在前面或者出循環(huán)后倒置一下s可以起到一樣的效果

lanqiaoOJ題號1515

【題?描述】輸??個正整數(shù)n，輸出n!的值，n≤1000。

C++代碼。 階乘的值極?，在C++中，unsigned long long類型變量的最? 值是264，?21!就已經(jīng)?于264了，所以需要?數(shù)組來存這個 ?數(shù)。

這是?道?精度算法題?，?精度算法可?數(shù)組實現(xiàn)。編 程時注意以下細節(jié)。

①定義?個數(shù)組a[]來存放?數(shù)，數(shù)組的?個元素存放?數(shù)的? 位數(shù)字。例如a[0]存放個位數(shù)，a[1]存放?位數(shù)，a[2]存放百位 數(shù)，等等。

②數(shù)組a[]需要定義成多?？也就是說，1000!有多少位？可以? Windows?帶的計算器直接算出來，1000! ≈4×102567。代碼中 簡單地定義成?個更?的數(shù)組a[10000]。

③模擬乘法運算，處理進位。 例如356×8，先計算個位的6×8，得48，其中個位的8等于 48%10=8，進位的4等于48/10=4。?下?代碼中的第10～第 13?，這??代碼實際上是處理了兩個數(shù)的乘法，請仔細分析這 ??代碼。

④按③的計算?法計算n!。i遍歷了1～n，計算 n!。

⑤從最?位開始輸出。先找到最?位，即第?個不等于0的數(shù)， 然后從?位往最低位輸出。 ? 提示：const int a[]表示定義?個?靜態(tài)數(shù)組，?靜態(tài) 數(shù)組應該定義在全局。如果將其定義在函數(shù)內(nèi)部，有些編譯器會 報錯。 有的讀者可能知道需要考慮代碼的計算復雜度問題,共循環(huán)計算了 10000×n = 10000×1000 = 1千萬次，不會超時。

const int N=10000;

int a[N]={0};//在全局定義了一個大靜態(tài)數(shù)組

void pow_n(int n){

a[0]=1;

int temp=0;//用來存儲可能產(chǎn)生的進位

for(int i=1;i<=n;i++){//模擬階乘計算

for(int j=0;j<=N;j++){

temp+=i*a[j];//以下三行實際處理了兩個數(shù)的乘法

a[j]=temp%10;

temp=temp/10;

}

}

int flag=0;

for(int i=N-1;i>=0;i--){

if(a[i]!=0){//找到第一個不為0的數(shù)，開始打印

flag=i;

break;

}

}

for(int i=flag;i>=0;i--) cout<

}

這里階乘計算的核心在于可以直接把i和a[j]相乘，由于a是從低位到高位存儲的，符合乘法的基本步驟，只要這里的結果沒有超出范圍，那總的結果就可以保證是對的。如果還是不清楚可以自己按照代碼手算一下比較。

如144*96。那么a={441}，i=96

1. 4*96=384, 4留下，temp=38

2. 4*96=384，(temp+4)%10=2,temp=(temp+4)/10=42

3.1*96=96，(temp+96)%10=8,temp=(temp+96)/10=13

由于循環(huán)從0-N-1且N足夠大，保證temp可以在循環(huán)里兩次賦值，留下3，1

最后倒序輸出13824

驗證：

1

??? a="123456789123456789"; ??? b="12345678912345678912345"; ??? //結果是12345802369134802369134

2求100的階乘

??? //結果是93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

柚子快報激活碼778899分享：大數(shù)加法-藍橋杯

http://yzkb.51969.com/

好文閱讀