Fibonacci數列 斐波那契數列

Fibonacci數列

Fibonacci數列的遞推公式為：Fn=Fn-1+Fn-2，其中F1=F2=1。

當n比較大時，Fn也非常大，現在我們想知道，Fn除以10007的餘數是多少。

輸入格式

輸入包含一個整數n。

輸出格式

輸出一行，包含一個整數，表示Fn除以10007的餘數。

樣例輸入

10

樣例輸出

55

樣例輸入

22

樣例輸出

7704

資料規模與約定

1 <= n <= 1,000,000。

首先我們可以定義一個數組F，

int F[1000000]；
           

由題可知

F[1]=1;
F[2]=1;
           

輸入一個N

int n;
scanf("%d",&n);
           

當N<2時輸出的就是1，是以

if(n>2){（資料處理*）}
           

設定一個循環，因為是從F[3]開始算起，是以for的判定條件為：

int i=3;i<=n;i++

Fn的計算就按題目給的Fn=Fn-1+Fn-2來計算。

對于這部分，我們要想到對于結果的處理不能放到最後，因為int的最大值一定比F1，000，000要小數組100%會炸

Boom！

是以我們要在運算時就對每一次的結果進行處理。

7%4=3

3%4=3

可知在運算時我們對斐波那契數列提前取餘不會對結果産生影響。

是以表達式變成了

F[i]=(F[i-1]+F[i-2])%10007;
           

以下是完整代碼：

#include<stdio.h>
#define falg 10007
main(){
	int n;
	scanf("%d",&n);
	int F[n];
	F[1]=1;
	F[2]=1;
	if(n>2){
	for(int i=3;i<=n;i++){
		F[i]=(F[i-1]+F[i-2])%falg;
		}
	}
	printf("%d",F[n]);
	return 0
} 
           

另附兩個不同解法：

這個是我的另一種解法占用空間較小但是算法更複雜

#include<stdio.h>
#define falg 10007
#define M (a1+a2)
main(){
	int a1=1,a2=1,ans,n,i;
	scanf("%d",&n);
	if(n>2){
		int bol =n%2;
		n=(n-2)/2;
		for(i=0;i<n;i++){
			a1=M%falg;
			a2=M%falg;	
		}
		if(bol==1){
			a2=M%falg;
		}
	}

	printf("%d\n",a2);
	return 0; 
} 
           

引用自百度知道 殛丿殪 的回答

#include<stdio.h>
int main(void)
{
int x,y,z,i,n;
x = 0;
y = 0;
z = 1;
i = 0;
scanf("%d",&n);
while(i<n)
{
x=y;
y=z;
z=x+y;
z=z%10007;
i +=1;
}
y=y%10007;
printf("%d",y);
return 0;
}