首页 > 代码库 > Fibonacci Again

Fibonacci Again

2024-11-22 04:36:39   204人阅读

Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).
 

 

Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).
 

 

Output
Print the word "yes" if 3 divide evenly into F(n).

Print the word "no" if not.
 

 

Sample Input
0
1
2
3
4
5
 

 

Sample Output
no
no
yes
no
no
no

 做这道题的思路来自hau oj 的另一道题

1005 

Number Sequence

是一个周期的问题

/*思路如下，题目最终是要判断能否被3整除，那么在计算每一个 f（n）时，可以先对 3 求余，

那么，问题就转化为题号：1005   由于对 3 求余，那么结果就被控制在范围 0---2 ，当满足

f（n-1)=f（0）=7%3=1 并且 f（n）=f（1）=11%3=2时。break循环，而不必要算出全部 f（n）

此时以 i-2 作为一个周期 那么 f（n）=f（n%(i-2))  若f（n）==0  说明原f（n）能被3 整除*/

技术分享
#include<cstdio>int are[1000000];int main(){    int i;    are[0]=1;    are[1]=2;    for(i=2; i<100000; i++)    {        are[i]=(are[i-1]+are[i-2])%3;        if(are[i]==2&&are[i-1]==1)            break;    }    int n;    while(scanf("%d",&n)!=EOF)    {        n=n%(i-1);        if(are[n]==0) printf("yes\n");        else printf("no\n");    }    return 0;}
View Code

 

 

Fibonacci Again


联系
我们