楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入样例#1：
4
输出样例#1：
5
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
思路:
题目中说明中提及递归太慢,所以用递推做的.但是又因为范围是到5000,范围太大,所以需要用高精来做.
坑点:
斐波那契第0项的值为0,是根据题目的意思来判断的.
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int M = 100010; int n; string f[M]; string J(string aa,string bb) { if(aa.length()<bb.length()) { string tmp=aa; aa=bb; bb=tmp; } int i,j; for(i=aa.length()-1,j=bb.length()-1;i>=0;i--,j--) { aa[i]=char(aa[i] + ( j >= 0 ? bb[j]-‘0‘ : 0)); if(aa[i]-‘0‘>=10) { aa[i]=char((aa[i]-‘0‘)%10+‘0‘); if(i) aa[i-1]++; else aa=‘1‘+aa; } } return aa; } int main() { int j=3; scanf("%d",&n); f[0]=‘0‘; f[1]=‘1‘; f[2]=‘2‘; while(j<=n) { f[j]=J(f[j-1],f[j-2]); j++; } cout<<f[n]; return 0; }
End.
原文：http://www.cnblogs.com/zxqxwnngztxx/p/7083808.html
