爬楼梯问题-最大迈两步

欢迎大家来到IT世界,在知识的湖畔探索吧!

问题描述：

有n阶楼梯，每次只能迈一步或两步，输出有多少种迈法到达楼顶。

解题心得：

递归方法：先考虑最后一步，可能是迈了一步，可能是迈了两步。所以step(n)=step(n-1)+step(n-2)，然后step(0)=1，step(1)=1;

但是递归方法时间复杂度太高，n=40就已经需要一段时间了。

顺便学习了如何打表，把结果全部输出到一个txt文件里，然后需要哪个结果用哪个就行。

下面是代码：

#include <iostream> #include <cstdio> //时间复杂度太大，不采用。 using namespace std; int step(int n) { if(n==0||n==1){ return 1; }else{ return step(n-1)+step(n-2); } } int main { int n; FILE *fp; long long int a[55]; fp=fopen("fibonaqi.txt","w"); for(int i=0;i<40;i++){ a[i]=step(i); fprintf(fp,"%lld,\n",a[i]); } cin>>n; cout<<a[n]; return 0; }

欢迎大家来到IT世界,在知识的湖畔探索吧!

fibonacci数列： a[i]=a[i-1]+a[i-2];每一步都可以由前面两步得到，正好是斐波那契数列。

欢迎大家来到IT世界,在知识的湖畔探索吧!#include <iostream> using namespace std; int main { int a[55]; int n; a[1]=1; a[2]=2; for(int i=3;i<53;i++){ a[i]=a[i-1]+a[i-2]; } cin>>n; cout<<a[n]; return 0; }