斐波那契鳳尾(PAT)

1.題目描述

NowCoder号稱自己已經記住了1-100000之間所有的斐波那契數。

為了考驗他，我們随便出一個數n，讓他說出第n個斐波那契數。

當然，斐波那契數會很大。是以，如果第n個斐波那契數不到6位，則說出該數；否則隻說出最後6位。

2.輸入描述:

輸入有多組資料。

每組資料一行，包含一個整數n (1≤n≤100000)。

3.輸出描述:

對應每一組輸入，輸出第n個斐波那契數的最後6位。

4.輸入例子:

1
2
3
4
100000
           

5.輸出例子:

1
2
3
5
537501
           

6.解題思路：

由題意需要我們求100000個斐波那契數，顯然求到後面的斐波那契數會很大，并且題目隻要求後六位數，是以我們要對每一項斐波那契取餘；同時我們模拟一遍斐波那契數列可知第29位斐波那契數後開始大于6位數，是以我們在n>29時隻要輸出後6位即可

7.源代碼：

#include<stdio.h>
int main()
{
	int i,n,num[100001];
	num[0]=1;
	num[1]=1;
	for(i=2;i<=100000;i++)
		{
			num[i]=num[i-1]+num[i-2];
			num[i]=num[i]%1000000;//6位
		}
	while(scanf("%d",&n)!=-1)
	{
		if(n<29)
			printf("%d\n",num[n]);
		else
			printf("%06d\n",num[n]);//輸出後六位，不足補0
	}
	return 0;
}