題目:一個臺階總共有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;
}
~~~
運行結果如圖:




統計為如下表:

當n = 50的時候,遞歸版本非常慢,等了好久都沒出結果,于是干脆不等了。 當n比較大時,非遞歸版本運行速度比較高。
參考:
[http://zhedahht.blog.163.com/blog/static/25411174200731844235261/](http://zhedahht.blog.163.com/blog/static/25411174200731844235261/)