終於終於,費波納契數的解題能告一段落了!
最後兩題,我的程式雖然有一些小瑕疵,但是最終還是能夠跑過測試,那我們先來統整一下,費波納契數的幾個關鍵字重點吧!
輸入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;
}
結果圖: