iT邦幫忙

0

Day 16, 沒有Day 15,但費波納契數溢位問題有解了

  • 分享至 

  • xImage
  •  

如題,昨天我並沒有發佈文章,而是放了一天的空,看了一整天的影集,處理其他Arduino問題,但沒有費波納契數,所以乾脆不發文,今天我參考了成大資工Wiki的大數加法運算程式,解決了overflow問題:
http://wiki.csie.ncku.edu.tw/acm/course/Math#%E5%8A%A0%E6%B3%95%E9%81%8B%E7%AE%97
https://ithelp.ithome.com.tw/upload/images/20220619/20149573T0ssfr4Eqe.png
首先,由於每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:
https://ithelp.ithome.com.tw/upload/images/20220619/20149573k415vkSmZZ.png
After:
https://ithelp.ithome.com.tw/upload/images/20220619/201495736C5dg6i7La.png
我相信這一次,大部分是對的了。


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言