首页 > 代码库 > HDU 1715 大菲波数
HDU 1715 大菲波数
大菲波数
问题描述 :
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)。
样例输入:
512345
样例输出:
11235
思路同博客中上一道题1042 N！ 均是大数加法原则，考虑到位数较多，所以采用数组。一维数组可以么？可以，但考虑到较为繁琐。所以采用二维数组，a[i][j] 其中i 表示 整数pi ， j表示求得结果的位数。本题同样采用10进制，逢十进一。（有的程序可能去除以自己定义的数100,1000,10000等等）。
#include<iostream>#include<cstring>using namespace std;int f[1001][2001];int main(){ int m; int n; cin>>n; memset(f,0,sizeof(f)); f[1][0]=1; f[2][0]=1; for(int i=3;i<1001;i++) { for(int j=0;j<2001;j++) { f[i][j]+=f[i-1][j]+f[i-2][j];//+=号别错了 因为考虑到f[i][j]可能是之前计算的进位 if(f[i][j]>=10) { f[i][j+1]=f[i][j]/10;//注意此处不要颠倒 f[i][j]=f[i][j]%10; } } } while(n--) { cin>>m; int flag=0;//控制输出的 for(int i=1010;i>=0;i--)//考虑到进位可能比较多所以稍大点 { if(flag==0&&f[m][i]!=0) flag=1; if(flag) cout<<f[m][i]; } cout<<endl; } return 0;}
HDU 1715 大菲波数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。