大菲波数

问题描述 :

Fibonacci数列，定义如下： f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) n>=3。计算第n项Fibonacci数值。

输入:

输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。

输出:

输出为N行，每行为对应的f(Pi)。

样例输入:

样例输出:

思路同博客中上一道题1042 N！均是大数加法原则，考虑到位数较多，所以采用数组。一维数组可以么？可以，但考虑到较为繁琐。所以采用二维数组，a[i][j] 其中i 表示整数pi ， j表示求得结果的位数。本题同样采用10进制，逢十进一。（有的程序可能去除以自己定义的数100,1000,10000等等）。

#include<iostream>

#include<cstring>

using namespace std;

int f[][];

int main()

{

    int m;

    int n;

    cin>>n;

    memset(f,,sizeof(f));

    f[][]=;

    f[][]=;

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            f[i][j]+=f[i-][j]+f[i-][j];//+=号别错了  因为考虑到f[i][j]可能是之前计算的进位

            if(f[i][j]>=)

            {

                f[i][j+]=f[i][j]/;//注意此处不要颠倒

                f[i][j]=f[i][j]%;

            }

        }

    }

    while(n--)

    {

        cin>>m;

        int flag=;//控制输出的

        for(int i=;i>=;i--)//考虑到进位可能比较多所以稍大点

        {

            if(flag==&&f[m][i]!=)

               flag=;

           if(flag)

            cout<<f[m][i];

        }

        cout<<endl;

    }

    return ;

}

巴特西

HDU 1715 大菲波数

大菲波数

最新文章

热门文章