当前位置：首页 > article >正文

每日一刷——9.26——ACM训练题——Fibonacci Again

article 2024/10/6 22:53:11

题目描述：

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.

输入样例：

0
1
2
3
4
5

输出样例：

no
no
yes
no
no
no

思路分析：

9.25碎碎念：

1.我感觉需要打点，如果不打点的话，时间计算上估计会超时吧

2.应该用什么东西接收输入的一系列数据，这些数据需要保存吗？是输入一个数据就输出一个yes或no吗？

9.29找到的解决方法：

为了方便求解，我们可以把原式 F(n) = F(n-1) + F(n-2) 等式左右两边都对3取模，即 F(n) %3 = (F(n-1) + F(n-2) ) %3

此式子由数论知识易知可以进一步等价于 F(n) %3 = (F(n-1) %3 + F(n-2) %3) %3。现在我们开始找规律：F(0)%3=1，F(1)%3=2，F(2)%3=(F(1)%3+F(0)%3)%3=0，同理 F(3)%3=2，F(4)%3=2，F(5)%3=1，F(6)%3=0，F(7)%3=1，F(8)%3=1，F(9)%3=2，

这时可以发现 F(0)%3=1，F(1)%3=2 ，又 F(8)%3=1，F(9)%3=2，表明此时已出现循环，即一个完整的循环为：{1，2，0，2，2，1，0，1}，既然已经出现了循环，那么此题就可以划为找规律题目了，此问题就迎刃而解了。

代码实现：

#include<iostream>
using namespace std;
 
int main()
{
	int a[8]={1,2,0,2,2,1,0,1},n;
	while(cin>>n)
	{
		if(a[n%8]==0)
		{
			cout<<"yes"<<endl;
		}
		else
		{
			cout<<"no"<<endl;
		}
	}
    return 0;
}