首页 > 代码库 > 新的斐波那契数列

新的斐波那契数列

转载请标明出处:牟尼的专栏 http://blog.csdn.net/u012027907

Problem1: 

题目描写叙述: 

定义一个新的斐波那契数列:

 F(0)=7。 

F(1)=11; 

F(n)=F(n-1)+F(n-2);(n>=2) 

输入: 

输入有多组;首先输入一个N(N<=100)。代表要输入的測试用例的个数;接下来输入N个数字ni(ni<=100),数字间用空格隔开。

输出: 

求F(n)是否能被3整除,若能整除输出‘yes’,否则输出‘no’。

 

例子输入:

 3 0 1 2 

例子输出:

no 

no

yes

提示:不能用递归,否则超时!

在计算时。我们不是必需算出递推的真正值,后面会越来越大,可能Int 都存不下了!

题目仅仅要求算是否是3的倍数。也就是说。无论值多大。最后都仅仅是 3n+0,3n+1,3n+2 这三种情况,我们仅仅需对3取余就可以。

/*
 * 描写叙述: 新的斐波那契数列
 * 作者: 张亚超 
 * 博客: 牟尼的专栏 http://blog.csdn.net/u012027907
 * 日期: 2014/8/24
 */
#include<stdio.h>
#define N 105

int F[N]; // 记录递推数对3取余的余数
int I[N]; // 记录输入的n个值
bool mark[N]; //标记相应数是否是3的余数

int main(){

	F[0] = 7;
	F[1] = 11;
	for(int i = 0; i < N; i++) //标记初始化为false
		mark[i] = false;

	for(i = 2; i < N; i++){    //计算递推数对3取余的余数
		F[i] = F[i-1] + F[i-2];
		if(F[i] % 3 == 0)     //若为3的倍数,标记
			mark[i] = true;		
		F[i] %= 3;            //重要一步。简化运算,仅仅存对3的余数
	}


	int n;
	while(scanf("%d",&n) != EOF){
		for(int i = 0; i < n; i++){  //输入
			scanf("%d",&I[i]);
		}
		for( i = 0; i < n; i++){     //输出
			if(mark[I[i]])
				printf("yes\n");
			else
				printf("no\n");
		}
	}
	return 0;
}
转载请标明出处:牟尼的专栏 http://blog.csdn.net/u012027907

新的斐波那契数列