首页 > 代码库 > HDU1021 Fibonacci Again 规律

HDU1021 Fibonacci Again 规律

2024-07-22 08:57:53   222人阅读

Fibonacci Again

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 37002 Accepted Submission(s): 17876


Problem Description
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.

Sample Input
0
1
2
3
4
5

Sample Output
no
no
yes
no
no
no
这是一道变换了的斐波那契数列，但是你如果写成递归函数的话内存是不够的，因为n的范围很大，如果你把前20项打出来的话，你会发现规律：就是从2开始是yes，每隔4个就是yes，其余是no。按这个规律编程绝对没问题，但是我还是愿意在这里证明一下其正确性。
我们看前七项，并设为ai：

7    11   18   29   47  76   123

a1   a2   a3   a4   a5   a6   a7

易知a3和a7是能被3整除的，其实如果只知道a3能被3整除，就能推出a7也能被3整除：
a7 =     a5    +     a6
    = a3 + a4 +  a4 +   a5
    = a3 + a4 +  a4 + a3 + a4
    = 2*a3   +   3*a4
因为a3能被3整除，所以2*a3能被3整除，  且3*a4肯定也能被3整除，所以a7能被3整除。

现在来证明 a4，a5，a6不能被3整除：
① a4=a2+a3      a2不能，a3能，所以a4不能；
② a5=a3+a4      a3能，a4不能，所以a5不能；
③a6=a4  +  a5
      =a4  + a3 + a4
      =a3 +  2*a4
a3能，2*a4不能，所以a6不能；
#！：一个整数不能被3整除，那么这个数的2倍也不能被3整除。

运用数学归纳法将其推广到n即可，一样能保证其正确性，在此不再多做证明。

代码就很简单了：
#include <stdio.h>
#include <string.h>
#include <math.h>

int main()
{
	int i,n,k;
	while(scanf("%d",&n)!=EOF)
	{
		if(n%4==2)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}






HDU1021 Fibonacci Again 规律


联系
我们