跳台阶问题

最后更新于:2022-04-01 09:32:53

题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。 在[这里](http://zhedahht.blog.163.com/blog/static/25411174200731844235261/)看到这道面试题,思路是: 1)每次可以跳1级,也可以跳2级,如果当前只有1级台阶,那么就只有一次跳法;如果当前只有2级台阶,就有2种跳法(一种是每次跳1级,跳2次;另一种是一次跳2级,就跳完),也即 f(1) = 1; f(2) = 2。 2)假设有n级台阶要跳,如果最后一步是跳1级,那么剩下的就只有前面的n-1级台阶的步数了;如果最后一步是跳2级,那么剩下的就是前面n-2级台阶的步数了。总结两种情况,得出状态转移方程: f(n) = f(n-1) + f(n-2)。 经过上面的过程,可以写出这样的代码:    ~~~ int jumpstep(int n){ if(n == 1 || n == 2) return n; else return jumpstep(n-1) + jumpstep(n-2); } ~~~ 代码行数很少了,但是效率很低,因为有很多重复计算,于是,想出了另一个: ~~~ int jumpstep2(int n){ if(n == 1 || n ==2) return n; int *a = new int[n+1]; a[1] = 1; a[2] = 2; for(int i = 3; i <= n ; ++i){ a[i] = a[i-1] + a[i-2]; } int ret = a[n]; delete []a; return ret; } ~~~ 用一个表了记录计算结果。接着,来粗劣测试一下这两种方法的运行时间。上测试代码: ~~~ #include<iostream> #include<time.h> using namespace std; int jumpstep2(int n){ if(n == 1 || n ==2) return n; int *a = new int[n+1]; a[1] = 1; a[2] = 2; for(int i = 3; i <= n ; ++i){ a[i] = a[i-1] + a[i-2]; } int ret = a[n]; delete []a; return ret; } int jumpstep(int n){ if(n == 1 || n == 2) return n; else return jumpstep(n-1) + jumpstep(n-2); } void test_time(int (*func)(int), int n){ long bTime = clock(); cout<<"-----------------------------------"<<endl; cout<<"result is: "<<func(n)<<endl; long eTime = clock(); cout<<"cost time: "<<(eTime - bTime)<<"ms"<<endl; } void test(){ int n; cout<<"input n to test: "; cin>>n; test_time(jumpstep, n); test_time(jumpstep2, n); } int main(){ test(); return 0; } ~~~ 运行结果如图: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-19_56c6ad2554f97.jpg) ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-19_56c6ad2570512.jpg) ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-19_56c6ad257fae9.jpg) ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-19_56c6ad258fd2e.jpg) 统计为如下表: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-02-19_56c6ad25af87e.jpg) 当n = 50的时候,递归版本非常慢,等了好久都没出结果,于是干脆不等了。 当n比较大时,非递归版本运行速度比较高。 参考: [http://zhedahht.blog.163.com/blog/static/25411174200731844235261/](http://zhedahht.blog.163.com/blog/static/25411174200731844235261/)
';