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
這道題應(yīng)該說(shuō)是很簡(jiǎn)單的題，如果說(shuō)考察了什么知識(shí)點(diǎn)的話時(shí)能說(shuō)是（a+b）%n = (a%n +
b%n)%n，但是這個(gè)題卻有多種思路，可以從很多方面優(yōu)化，比較有意思。
【解題思路1】：
最簡(jiǎn)單的思路,開(kāi)一個(gè)大小為n的數(shù)組，初始化為0，遍歷一遍，如果某一項(xiàng)滿足條件則設(shè)置為1，就不多說(shuō)了，代碼如下：
#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;
}
這個(gè)提交上去，由于執(zhí)行時(shí)只查表，時(shí)間不算多10ms，但是內(nèi)存消耗不小。下面看幾種優(yōu)化的方法。
【思路2】
這種題一般情況下會(huì)有規(guī)律。把前幾個(gè)能被3整除的數(shù)的下標(biāo)列出來(lái)一看，規(guī)律就出現(xiàn)了：2 6 10 14…，這就是一個(gè)等差數(shù)列嘛，這就好辦了，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;
}
該解法如果說(shuō)還可以優(yōu)化的話，那只能把取余運(yùn)算變?yōu)槲贿\(yùn)算了。
if ((n-2)&3)
printf("no\n");
else
printf("yes\n");
【思路3】
如果把數(shù)列前幾項(xiàng)的值列出來(lái)，會(huì)發(fā)現(xiàn)數(shù)組中每8項(xiàng)構(gòu)成一個(gè)循環(huán)。這也很好辦。
代碼如下：
#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;
}
其實(shí)這個(gè)還可以優(yōu)化，我們仔細(xì)觀察可以看到這些滿足條件的下標(biāo)有一個(gè)特點(diǎn)：
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;
}