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;
}
查看30道真题和解析