[数据结构与算法]E. 一个新的斐波那契数列

题目描述

现在，有一个新的斐波那契数列, 定义如下:
F(0) = 7
F(1) = 11
F(n) = F(n-1) + F(n-2) (n=>2)

输入

输入包含多组测试样例, 每组测试样例包含一个非负整数n.

输出

如果F(n)能够被3整除, 请输出"yes", 否则请输出"no".

数据范围

0<=n <1,000,000

输入样例

0
1
2
3
4
5

输出样例

no
no
yes
no
no
no

思路分析

?一种非常容易想到的做法就是利用递推公式把F(n)计算出来, 之后再判断 F(n)%3 是否等于零. 显然, 这是一种非常不可取的方法, 因为计算F(1,000,000-1)时早已超出了 long long int 的范围.(其实这一点,通过最原始的斐波那契数列就可以看出来, 它增长得非常快), 所以再来思考其他思路.
?如此分析: 因为对于任意一个正整数n, n除以3的余数必为0,1,2这三种情况 (这可能需要一些数论知识, 不过在高中学过数列之后这一点应该也不难理解) 如此多的正整数除以3的余数竟然只有这三种情况, 不难想到 (写到这时不禁会心一笑, 懂的都懂) n除以3的余数可能以一定的规律重复出现. 先来写几个看看.

? 通过这个表格我们可以轻而易举地看出一个循环为{1, 2, 0, 2, 2, 1, 0, 1}, 有了以上规律, 代码就很容易打了(开个玩笑: 有手就行!)

样例代码

#include<iostream>
using namespace std;
int main() {
	int n;
	while (cin >> n) 
	{
		n = n % 8;
		if (n==2||n==6)
			cout << "yes";
		else
			cout << "no";
		cout << endl;
	}
}

补充

? 这道题最关键的就是看看你能不能找出这个规律, 然而这种事就像高中时期的一些套路题或者说求不定积分的一些变形技巧一样, 如果你见过并记住了则万事大吉, 否则… 所以说, 要多做题积累经验.
? 在网上搜索这道题的时候, 发现其他题解要加上:

可能会让解题思路更有说服力.