NowCoder数列(PAT)

1.题目描述

NowCoder最近在研究一个数列：

• F(0) = 7
• F(1) = 11
• F(n) = F(n-1) + F(n-2) (n≥2)

他称之为NowCoder数列。请你帮忙确认一下数列中第n个数是否是3的倍数。

2.输入描述:

输入包含多组数据。
每组数据包含一个整数n，(0≤n≤1000000)。

3.输出描述:

对应每一组输入有一行输出。
如果F(n)是3的倍数，则输出“Yes”；否则输出“No”。

4.输入例子:

0
1
2
3
4
5

5.输出例子:

No
No
Yes
No
No
No

6.解题思路：

找规律，列出前几项

f（0）=7， f（0）%3=1
f（1）=11，f（1）%3=2
f（2）=18，f（2）%3=0
f（3）=29，f（3）%3=2
f（4）=47，f（4）%3=2
f（5）=76，f（5）%3=1
f（6）=123，f（6）%3=0
f（7）=199，f（7）%3=1
f（8）=322，f（8）%3=1
f（9）=521，f（9）%3=2
。。。。。

由上述例子我们可以得出一个规律公式，f（n）%3=[ f（n-1）+f（n-2）]%3
于是我们便只用算出八项的余数即可，从而我们只需要求出n在八位中的第几位即可

7.源代码：

#include<stdio.h>
int main()
{
	int n,num[8];
	num[0]=1;
	num[1]=2;
	for(int i=2;i<8;i++)
	{
		num[i]=(num[i-1]+num[i-2])%3;
	}
	while(scanf("%d",&n)!=-1)
	{
		n=n%8;
		if(num[n]==0)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}