S - 大菲波數

Fibonacci數列，定義如下：

f(1)=f(2)=1

f(n)=f(n-1)+f(n-2) n>=3。

計算第n項Fibonacci數值。

Input

輸入第一行為一個整數N，接下來N行為整數Pi（1<=Pi<=1000）。

Output

輸出為N行，每行為對應的f(Pi)。

Sample Input

5
1
2
3
4
5      

Sample Output

1
1
2
3
5      

解題思路：

這道題在我看來，其實就是大數加法。關鍵是大數加法。

（這裡隻讨論大數-正整數）

其實要模拟大數加法，我們隻需要想一下國小的時候我們要怎麼做加法。

無非就是

1、從兩個要想加的數字的末尾開始相加

2、考慮進位（在小橫杠上寫個小數字）

3、回到 1、，直到其中有個數字的所有位數都處理完了

其實，我們已經把整個大數加法的程式都差不多寫出來了，關鍵其實就是有幾個小細節

1、兩個數字不同位數怎麼辦呀？

2、如何真的像我們想的那樣子進行呢，需要有什麼變量

3、除了這些實際操作中還有沒有什麼需要注意呢？

代碼展示：

#include<iostream>
#include<string>
using namespace std;
string add(string s1,string s2)
{
	string s;
	int len1=s1.size()-1;
	int len2=s2.size()-1;
	int sum=0;
	int flag=0;
	while(len1>=0&&len2>=0)
	{
		sum=flag+s1[len1]-'0'+s2[len2]-'0';
		s=s+char(sum%10+'0');
		flag=sum/10;
		len1--;
		len2--;
	}
	while(len1>=0)
	{
		sum=flag+s1[len1]-'0';
		s=s+char(sum%10+'0');
		flag=sum/10;
		len1--;
	}
	while(len2>=0)
	{
		sum=flag+s2[len2]-'0';
		s=s+char(sum%10+'0');
		flag=sum/10;
		len2--;
	}
	if(flag>0)
	{
		s=s+char(flag+'0');
	}
	//s轉置
	char tmp=' ';
	int end=s.size(); 
	for(int i=0;i<end/2;i++)
	{
		tmp=s[i];
		s[i]=s[s.size()-i-1];
		s[s.size()-i-1]=tmp;
	}
	return s;
}
int main()
{
	string f[1001];
	f[1]="1";
	f[2]="1";
	for(int i=3;i<=1000;i++)
	{
		f[i]=add(f[i-1],f[i-2]);
	}
	int n=0;
	while(cin>>n)
	{
		int tmp=0;
		for(int m=0;m<n;m++)
		{
			cin>>tmp;
			cout<<f[tmp]<<endl;
		}
	}
}