Fibonacci Again

某日，老师留了一道神奇的斐波那契数列题。

先把题搬上来

【问题描述】There are another kind of Fibonacci number:F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2) (n>=2).
【输入形式】Input an interger n.(n<1000000)
【输出形式】Print the word "yes" if 3 divide evenly into F(n).Print the word "no" if not.
【样例输入】5
【样例输出】no
【样例说明】if input 5,print the word"no".
【评分标准】This programe have 4 test points,each have0. 25 points.

简而言之，就是输入一个值n，n代表这个数列里面的第n个元素。解题者需要判断第n个元素是否可以被3整除。

做题的时候我还没学C语言的字符串和数组。

好吧，很简单的一道题。

对bug进行一个写

我很快也写出了第一版程序。

#include <stdio.h>
int main() {
	int in, a = 1;
	scanf("%d", &in);
	int f, f0 = 7, f1 = 11 ;
	while (a != in) {
		f = f0 + f1;
		f0 = f1;
		f1 = f;
		a++;
	}
	if (f % 3 == 0) {
		printf("yes");
	} else {
		printf("no");
	}
	return 0;
}

提交，显示有两个测试数据没有通过。这一定是测试数据的问题。在几经排查确定算法没有写错以后，我把目光挪向了这道题的题干。n的取值小于1000000。

一定是谁的问题

于是我强行读取了一下这道题的测试数据。报错的两个测试数据，一个n的值是999998另一个是999999。
好嘛，F(n)全部超出了int的范围。int不够，那就long long。long long还不够的情况下我还想出了用Double的小数点后的位数来存储的方法。但是这里涉及一个基本的进制转换问题。二进制没有办法表示十进制下的0.1。

对bug进行一个修

就在我埋头苦学数组和字符串的时候。老爹刚好看见了正在折腾这道题的我。对着这道题的数列一顿分析，得到如下规律：

F(0)=2*3  +1
F(1)=3*3  +2
F(2)=6*3  +0
F(3)=9*3  +2
F(4)=15*3 +2
F(5)25*3  +1
……

这里我把每个值的余数都单拿出来放在了后面。仔细观察不难发现，这些余数全部满足满三归0的特征。
既第n项的余数由前两项的余数相加所得，如果余数大于3，则要减去一个3。
在此基础上我对原来的代码稍作了一些修改。

int f, f0 = 1, f1 = 2 ;
while (a != in) {
f = f0 + f1;
	if (f >= 3) {
		f = f - 3;
	}
	f0 = f1;
	f1 = f;
	a++;
}
if (f  == 0) {
	printf("yes");
}
//此处仅为改动部分

再提交，运行，通过！

Return 0;

首先，不得不佩服老爹这扎实的数学功底。这道题就算能拿字符串解，其在代码的复杂程度和对资源的利用上也肯定是要逊于这道题的最终解。
再一个可能就是要学会换角度看问题了，这个明显属于是构建模型上的问题。
不过最近是真的没少碰，满X归零或者进位的模型。

if (a>=x){
    a=a-x;
}