每日一刷——9.26——ACM训练题——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.

 输入样例：

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;
}

题目分析Again ：

7        1

11      2

18      0

29      2

47      2

76      1

123     0

199     1

322     1

确实是发现余数也是按照前两个余数之和等于下一个余数，然后九发现规律，确实是可以有循环，所以这个题目就简化为对8取余，如果得出来的结果充当a数组的下标时，发现确实为0，那么这个数就是可以被3除尽，真的很奇妙！！！

有时候除了打点，也可以考虑一下循环，尤其是本身数字就很有规律时！