這次的題目是http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=3552
[C_RU10-中] 爬樓梯
1. 問題描述:
一至二樓有 8 級樓梯,某人上樓,每次可跨 1 級或 2 級,不同上樓的方法有幾種?
輸入說明:
輸入樓梯之級數 n(3 ≦ n ≦ 20) 。
輸出說明:
輸出不同上樓的方法總數。
範例 :
Sample Input |
Sample Output |
3 |
3 |
13 |
377 |
雖然題目是中級,但只要了解其中的規律,就非常簡單了
走法是一次1級或2級,所以
當樓梯是1階時,有1 , 1個方法
2時,有1、1 , 2, 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、、
發現這其實是個費式數列,既然是個費式數列
那麼這題只要用遞迴就可以輕鬆解決
- #include <iostream>
- using namespace std;
- int f(int a);
- int main()
- {
- int input;
- cin>>input;
- cout<<f(input)<<endl;
- return 0;
- }
- int f(int a)
- {
- if(a==1)
- return 1;
- else if(a==2)
- return 2;
- else
- return f(a-1)+f(a-2);
- }
若想閱讀相關文章請關注我的粉絲團
小資菜鳥向前衝
文章標籤
全站熱搜
留言列表