一道簡單的Fibonacci

時間限制:?1 Sec??內(nèi)存限制:?32 MB

題目描述

有如下數(shù)列：F(0) = 7, F(1) = 11, F(n) = F(n - 1) + F(n - 2) ?(n >= 2)。

?

輸入

輸入由一系列的行構(gòu)成，每一行包含一個正數(shù) n (n < 1000000)。

?

輸出

如果 F(n) 能被 3 整除，則輸出 “Yes”，否則輸出 “No”。

?

樣例輸入

0 1 2 3 4 5

樣例輸出

No No Yes No No No

解法一：打表+找規(guī)律

#include<bits/stdc++.h> using namespace std; int f(int n) {if(n==0) return 7;if(n==1) return 11;return f(n-1)+f(n-2); } int main() {for(int i=0;i<50;i++)if(f(i)%3==0)printf("%d:Yes\n",i);else printf("%d:No\n",i);return 0; }

AC代碼

#include<bits/stdc++.h> using namespace std; int main() {int n;while(cin>>n){if((n-2)%4==0)printf("Yes\n");else printf("No\n");}return 0; }

解法2：同余公式：(a+b)%mod=a%mod+b%mod

#include<bits/stdc++.h> using namespace std; typedef long long ll; int f(int n) {if(n==0) return 7;if(n==1) return 11;int f0=7,f1=11,f2;//同余公式：(a+b)%mod=a%mod+b%modfor(int i=1;i<n;i++){f2=f0+f1;f0=f1%3;f1=f2%3;}return f2; } int main() {int n;while(cin>>n){if(f(n)%3==0)printf("Yes\n");else printf("No\n");}return 0; }

解法三：打表

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+10; int a[maxn]; int main() {a[0]=7;a[1]=11;for(int i=2;i<maxn;i++){a[i]=a[i-1]+a[i-2];a[i-1]%=3;a[i-2]%=3;}int n;while(cin>>n){if(a[n]%3==0)printf("Yes\n");else printf("No\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的一道简单的Fibonacci的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。