如題,昨天我並沒有發佈文章,而是放了一天的空,看了一整天的影集,處理其他Arduino問題,但沒有費波納契數,所以乾脆不發文,今天我參考了成大資工Wiki的大數加法運算程式,解決了overflow問題:
http://wiki.csie.ncku.edu.tw/acm/course/Math#%E5%8A%A0%E6%B3%95%E9%81%8B%E7%AE%97
首先,由於每10進位一次不會有overflow問題,所以不再使用long long int 指令,而是int指令(省一點運算空間)。
並且我們將最大位數設置為1000位數。
設置變數sum,計算進位次數,不但可以客製化迴圈次數,避免浪費,在最後顯示數值時,也能使迴圈顯示到最高進位數值,而不會將之外的0顯示出來,相當方便。
要注意一點,vector[10]是位於0~9,而不是1~10。所以,反向顯示時sum變數迴圈要扣一。
以下是我的程式:
//費波納契數
#include<iostream>
using namespace std;
int main(){
while(true){
int a[1000]={0},b[1000]={0},c[1000]={0};
b[0]=1;
int n, j=0, carry=0, sum=1;
//cout<<"?"<<endl;
cin>>n;
if(n==0){
//cout<<"F"<<n<<" is "<<a<<endl;
cout<<'0'<<endl;
}
else if(n==1){
//cout<<"F"<<n<<" is "<<b<<endl;
cout<<'1'<<endl;
}
else{
// cout<<"!"<<endl;
for(int i=0;i<n-1;i++){
for(j = 0; j < sum; ++j){
c[j] = a[j] + b[j] + carry;
carry = c[j] / 10;
c[j] %= 10;
if(carry!=0&&j+1==sum){//這裡參考了一位前輩的文章:http://it-easy.tw/c-super-large-power/
sum++;
//cout<<"sum is "<<sum<<endl;
}
}
for(j = 0; j < sum; ++j){
a[j]=b[j];
b[j]=c[j];
}
}
for(int h=sum-1; h>=0;--h){//要注意一點,vector[10]是位於0~9,而不是1~10。所以,反向顯示時sum變數迴圈要扣一。
cout<<c[h];
}
cout<<endl;//顯示完所有數值後才換行
//cout<<"F"<<n<<" is "<<c<<endl;
// cout<<c<<endl;
}
}
return 0;
}
最後,成大資工的維基真不錯!
顯示一下對照結果:
Before:
After:
我相信這一次,大部分是對的了。