iT邦幫忙

0

Day 23, Fibonacci last digit sum again & square

  • 分享至 

  • xImage
  •  

終於終於,費波納契數的解題能告一段落了!
最後兩題,我的程式雖然有一些小瑕疵,但是最終還是能夠跑過測試,那我們先來統整一下,費波納契數的幾個關鍵字重點吧!

  1. Pisano period: 費波納契數與指定整數相除之餘數,會呈現規律循環數。
  2. Fibonacci number:
    F0=0, F1=1
    Fn = Fn-1+Fn-2 (n>=2)
  3. 若將費波納契數(0~n)平方後依序相加的結果,會等同於費波納契數 FnxFn+1:
    請參見ted talk|| The magic of Fibonacci numbers | Arthur Benjamin:
    Yes

題目七:

輸入from, to 二整數(小到大),輸出從from到to的費波納契數加總之尾數值。
例如一:
Input 7 7
Output 3
例如二:
Input 6 7
Output 1

我的程式:

#include<iostream>
using namespace std;
long long last_digit_sum_fibo_again(long long from, long long to){
	long long sum=0, a=0, b=1,c=0;
	from  = from%60;// pisano period
	to = to%60;//pisano period
	if(to<from){
		to = to+60;
	}
	for(int i=0;i<=to;i++){
		if(i==0){
			c =0;
		}
		else if(i==1){
			c =1;
		}
		else if(i>=2){
			c = a+b;
			a=b;
			b=c;	
		}
		if(i>=from){
			sum = (sum+c)%10;
		}


	}
	return sum;
}



int main(){


	long long  from, to;
	cin>>from>>to;
	cout<<last_digit_sum_fibo_again(from, to)<<endl; 	

	return 0;
}

題目八:

輸入整數N,輸出從F0~FN之平方相加整數的尾數。
例如一:
Input 1
Output 1
例如二:
Input 5
Ouput 0
我們可以利用平方相加數等同於 Fn X Fn+1,來設計題目,並利用Pisano period避免overflow。
以下是程式:

#include<iostream>
using namespace std;
long long fibo_square_sum(long long fibo){
	fibo = fibo%60;
	long long a[1000]={0}, b[1000]={0}, c[1000]={0};
	long long  sum=1, counter=1, count = 0;
	b[0]= 1;
	for(int i=0;i<=fibo+1;i++){
		if(i==0){
			c[0]=0;
		}
		else if(i==1){
			c[0]=1;
		}
		else if(i>=2){
			for (int j=0;j<counter;j++){
				c[j] = a[j]+b[j]+count;
				c[j] = c[j]%10;
				count = c[j]/10;
				a[j] = b[j];
				b[j]= c[j];
				if(count !=0 && j+1 ==counter){
					counter++;
				}
			}

		}
		if(i>=fibo){
			sum = (sum*c[0])%10;
		//	cout<<sum<<" sum"<<endl;
		}
	}
	return sum;
}

int main(){
	long long fibo;
	cin>>fibo;
	cout<<fibo_square_sum(fibo)<<endl;
	
}

結果圖:
https://ithelp.ithome.com.tw/upload/images/20220626/20149573UuCSx7I5U2.png


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

尚未有邦友留言

立即登入留言