高精度斐波拉契数列求解

题目描述

斐波拉契的数列如下形式，输出Fibonacci的第N（1<=N<=200）项。 1 1 2 3 5 8 13 21 34 55 ….

输入

一个数 N。

输出

斐波那契数列的第 N 项的值

样例输入

10

样例输出

55

提示

数据范围：1<=n<=200

题解

#include<bits/stdc++.h> 
using namespace std;
// 高精度
const int N=1200;
char sum[N];
int s=0,m=0,n;
int main()
{
    cin>>n;
    string s1,s2;
    int a[N],b[N];
    int cnt,i;
    //注意这里
    s1="1";
    s2="1";
    for(m=2;m<n;m++)
    {
		/*
		将常规斐波那契数列的求解方法，替换成高精度的方式
		k=a+b;//第i位k的值是前两位之和
    	a=b;//a向右移动一位
    	b=k;//b向右移动一位
		*/
        //数组初始化，填充0 
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0]=s1.length();
        for(i=1;i<=a[0];i++)
        {
            a[i]=s1[a[0]-i]-'0';
        }
        b[0]=s2.length();
        for(i=1;i<=b[0];i++)
        {
            b[i]=s2[b[0]-i]-'0';
        }
        cnt=(a[0]>b[0]?a[0]:b[0]);
        for(i=1;i<=he;i++)
        {
            a[i]+=b[i];
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
        cnt++;
        //计算出来的值，去除前导0 
        while((a[cnt]==0)&&(cnt>1)){
			cnt--;
		}
			for(i=cnt,s=0;i>=1;i--,s++)
			{
				sum[s]=a[i]+'0';
			}
            s1=s2;
            s2=sum;
    }
    cout<<s2<<endl;
    return 0; 
}