這次的題目是http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=3552

 

[C_RU10-中] 爬樓梯

1. 問題描述: 
一至二樓有 8 級樓梯,某人上樓,每次可跨 1 級或 2 級,不同上樓的方法有幾種?

CRU10.JPG

輸入說明:

輸入樓梯之級數 n(3 ≦ n ≦ 20) 。

輸出說明:

輸出不同上樓的方法總數。

範例 :

Sample Input

Sample Output

3

3

13

377

 

雖然題目是中級,但只要了解其中的規律,就非常簡單了

走法是一次1級或2級,所以

當樓梯是1階時,有 ,   1個方法

2時,有1、1 , ,   2個方法

3時,有1、1、1 ,1、2 ,2、1  3個方法

4時,

1、1、1、1 ,1、1、2 ,1、2、1 ,2、1、1 ,2、2     5個方法

5時,有

1、1、1、1、1

1、1、1、2

1、1、2、1

1、2、1、1

2、1、1、1

1、2、2

2、1、2

2、2、1  8個方法

排列起來是

1、2、3、5、8、、

發現這其實是個費式數列,既然是個費式數列

那麼這題只要用遞迴就可以輕鬆解決

 

 

  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4. int f(int a);  
  5. int main()  
  6. {  
  7.     int input;  
  8.     cin>>input;  
  9.     cout<<f(input)<<endl;  
  10.     return 0;  
  11. }  
  12. int f(int a)  
  13. {  
  14.     if(a==1)  
  15.         return 1;  
  16.     else if(a==2)  
  17.         return 2;  
  18.     else  
  19.         return f(a-1)+f(a-2);  
  20. }  

若想閱讀相關文章請關注我的粉絲團

小資菜鳥向前衝

https://www.facebook.com/%E5%B0%8F%E8%B3%87%E8%8F%9C%E9%B3%A5%E5%90%91%E5%89%8D%E8%A1%9D-204484273323335/?fref=ts

文章標籤
創作者介紹

cychss6305的部落格

cychss6305 發表在 痞客邦 PIXNET 留言(0) 人氣()