Fibonacci Again
【题目描述】
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
这道题应该说是很简单的题，如果说考察了什么知识点的话时能说是（a+b）%n = (a%n +
b%n)%n，但是这个题却有多种思路，可以从很多方面优化，比较有意思。
【解题思路1】：
最简单的思路,开一个大小为n的数组，初始化为0，遍历一遍，如果某一项满足条件则设置为1，就不多说了，代码如下：
#include <stdio.h>
#include <stdlib.h>
int r[1000000];
int main(void)
{
int a, b, tmp;
int i;
int n;
a = 7;
b = 11;
r[0] = r[1] = 0;
for (i = 2; i < 1000000; ++i)
{
tmp = ((a%3) + (b%3)) % 3;
if (tmp == 0)
r[i] = 1;
a = b;
b = tmp;
}
while (scanf("%d", &n) == 1)
{
if (r[n] == 0)
printf("no\n");
else
printf("yes\n");
}
return 0;
}
这个提交上去，由于执行时只查表，时间不算多10ms，但是内存消耗不小。下面看几种优化的方法。
【思路2】
这种题一般情况下会有规律。把前几个能被3整除的数的下标列出来一看，规律就出现了：2 6 10 14…，这就是一个等差数列嘛，这就好办了，an = a1 + (n-1)*4,那么an-a1肯定能被4整除。代码如下：
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n;
while (scanf("%d", &n) == 1)
{
if ((n-2)%4 == 0)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
该解法如果说还可以优化的话，那只能把取余运算变为位运算了。
if ((n-2)&3)
printf("no\n");
else
printf("yes\n");
【思路3】
如果把数列前几项的值列出来，会发现数组中每8项构成一个循环。这也很好办。
代码如下：
#include <stdio.h>
#include <stdlib.h>
int a[8];
int main(void)
{
int n;
a[2] = a[6] = 1;
while (scanf("%d", &n) == 1)
printf("%s\n", a[n%8] == 0 ? "no" : "yes" );
return 0;
}
其实这个还可以优化，我们仔细观察可以看到这些满足条件的下标有一个特点：
N%8 == 2或者n%8==6
代码如下：
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n;
while (scanf("%d", &n) == 1)
{
if (n%8 == 2 || n%8 == 6)
printf("yes\n");
else
printf("no\n");
}
return 0;
}