首页 > 代码库 > 数楼梯——恶心的高精斐波那契数列
数楼梯——恶心的高精斐波那契数列
题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
输入样例#1：
4
输出样例#1：
5
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
啊啊，数据太大了！
肿么办？！
当数据等于5000时的斐波那契数为
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626
long long 也开不开啊！
那真么办？！
用高精啊！！！
代码
#include<cmath>#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;int f[5001][5001]={0},len[5001]={0};int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f;}void fei(int a,int b,int c){ for(int i=1;i<=max(len[b],len[c]);i++) { f[a][i]+=f[b][i]+f[c][i]; if(f[a][i]>9) { f[a][i+1]+=f[a][i]/10; f[a][i]%=10; len[a]=max(len[a],i+1); } else len[a]=max(len[a],i); }}int main(){ int n=read(); f[1][1]=1; f[2][1]=2; len[0]=1; len[1]=1; for(int i=3;i<=n;i++) { fei(i,i-1,i-2); } for(int i=len[n];i>=1;i--) cout<<f[n][i]; return 0;}
数楼梯——恶心的高精斐波那契数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。