7-45 求Fibonacci数列的第n项（30 分）

求Fibonacci数列的第n项f[n]. f[0]=1; f[1]=1 ; f[n]=f[n-1]+f[n-2];

输入格式:

输入一个不超过10000的正整数n。

输出格式:

输出Fibonacci数列的第n项的值。

输入样例:

在这里给出一组输入。例如：

99

输出样例:

在这里给出相应的输出。例如：

354224848179261915075

这里讲三种方法：

第一种：

#include <iostream>
#include <vector>
using namespace std;
vector <int> a,b,c;
void jisuan(int n){
	if(n<=1) cout << 1 << endl;
	else{
		a.push_back(1);
		b.push_back(1);
		for (int i = 2; i <= n;++i){
			c=b;//存一下b的值
			for (int j = b.size()-1,k = a.size()-1;k>=0;k--,j--){
				b[j]+=a[k];
				if(b[j]>=10){
					if(k==0&&j==0){
						b.insert(b.begin(),1);
					    j++;//插入之后需要%10的那个数往后移动一位
					}
					else{
						b[j-1]++;// 如果b前面还有数，前一个数+1
					}	
					b[j]%=10;//把数%10，变成小于10的数因为前面已经进位
				}		
			}
			a=c;
		}
		for (int i = 0; i < b.size();i++){
			cout << b[i];
		}
		cout << endl;
	}
}
int main(){
	int n;
	cin >> n;
	jisuan (n);
	return 0;
}

 第二种：（思路跟第一种一样，不解释了）

#include <iostream>
using namespace std;
string s1,s2,s3;
void jisuan(int n){
	if(n<=1) cout << 1 << endl;
	else{
		s1="1";
		s2="1";
		for (int i = 2; i <= n;i++){
			s3=s2;
			int cnt=0;
			for (int j = s2.size()-1,k = s1.size()-1;k>=0;k--,j--){
				s2[j]+=s1[k]-'0';
				int x=s2[j]-'0';
				if(x>=10){
					if(k==0&&j==0){
						s2.insert(s2.begin(),'1');
						j++;
					}
					else{
					    s2[j-1]++;
					}
					s2[j]-=10;
				}
			}
			s1=s3;
		}
		cout << s2 << endl;
	}
}
int main(){
	int n;
	cin >> n;
	jisuan(n);
	return 0;
}

 第三种：（如果题目给的内存过小，可能会超内存）

import java.util.*;
import java.math.BigInteger;
 public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        while(cin.hasNextInt()){
            int num = cin.nextInt();
            BigInteger bg2 = BigInteger.ONE;
            BigInteger bg1 = BigInteger.ZERO;
            BigInteger bg3 = BigInteger.ZERO;
            for(int i = 1; i <= num; i++){//常规的循环相加
                bg3 = bg1.add(bg2);
                bg1 = bg2;
                bg2 = bg3;
            }
            System.out.println(bg3);
        }
    }
}