学步园

遇到高精度的题目，曾经是多么的不快，可是一次又一次硬着头皮写了过后，觉得，高精度的题目也想像中的那么烦……

这道大斐波数，更是乌龙，原来打算从右边找到不为0的位置来确定长度，不慎将 “!=” 写成了 “==” ，奇迹的是竟然AC了！

后来发现，把数为0的位也相加，不影响结果，还省去了求长度的麻烦，当然，占的内存多了点，哈哈！

#include <iostream>
#include <string.h>

using namespace std;

int f[5010][1010];       //第1个5010用来存5010个斐波那契数（测试可知第5000项已超过了1000位），第2个1010表示给每个斐波那契数开1010位

int main()
{
    int i, j;

    memset(f, 0, sizeof(f));

    f[1][0] = 1;        //给第1个斐波那契数置数
    f[2][0] = 1;        //给第2个斐波那契数置数

    for(i = 3; i < 5010; i++)      //从第3项开始，用前2项相加
    {
        int C = 0;      //C表示进位，开始设为0
        for(j = 0; j < 1001; j++)
        {
            f[i][j] = (f[i-2][j] + f[i-1][j] + C) % 10;     //%10后就是这一位该有的数字
            C = (f[i-2][j] + f[i-1][j] + C) / 10;       //相加产生的进位
        }

    }

    int a;
    while(cin>>a)
    {
        for(j = 1001; j >= 0; j--)      //寻找最高位
            if(f[a][j] != 0)
                break;
        for(; j >= 0; j--)
            cout<<f[a][j];
        cout<<endl;
    }
    return 0;
}