題目描述

樓梯有N階，上樓可以一步上一階，也可以一步上二階。

編一個(gè)程序，計(jì)算共有多少種不同的走法。

輸入輸出格式

輸入格式：

?

一個(gè)數(shù)字，樓梯數(shù)。

?

輸出格式：

?

走的方式幾種。

?

輸入輸出樣例

輸入樣例#1：
4 輸出樣例#1：
5

說明

用遞歸會太慢，需用遞推

（60% N<=50 ,100% N<=5000)

?

?

啊啊，數(shù)據(jù)太大了！

腫么辦？！

當(dāng)數(shù)據(jù)等于5000時(shí)的斐波那契數(shù)為

62763028004889570860352531083496840554785287027364574390258244489279372568116632 64475883711527806250329984690249846819800648580083040107584710332687596562185073 64042228679923993261579710597471085709548734282035130747714187501217687430715601 62299658325891377797249738543627776298782295055002604771361083637090900104215369 15488632339240756987974122598603591920306874926755600361865354330444681915154695 74185196007108994401531930012857410766275705479064815275136647552912187721278548 96651017337558985803179844029638737381870001207378241931620113992005474240344408 36239726275765901190914513013217132050988064832024783370583789324109052449717186 85732723978300002079177780450393043987506866268767067880291426978481702256708806 94962311114079089533139023985296550560822285987158823657794699024656757156991872 25655878240668599547496218159297881601061923195562143932693324644219266564617042 93422789337117983238964289528540126387534264046801737892592148358011127805504425 41983822655673959464318033043043268650777429258187573706917261682286488413192314 70626

?

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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/z360/p/6680844.html

總結(jié)

以上是生活随笔為你收集整理的数楼梯——恶心的高精斐波那契数列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。