首页 > 代码库 > 9、剑指offer--变态跳台阶

9、剑指offer--变态跳台阶

题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 
解题思路:可知本题f(n)=f(1)+f(2)+...+f(n-1)+1;通过数学归纳法得到f(n)=2^(n-1)
 1 #include <iostream>
 2 using namespace std;
 3 class Solution {
 4 public:
 5     //fn=2^(n-1)
 6     int jumpFloorII(int number) {
 7         if(number <= 0)
 8             return 0;
 9         //fibN = 2^(n-1);
10         else if(number == 1)
11             return 1;
12         else
13             return 2*jumpFloorII(number-1);
14  
15     }
16 };
17 int main()
18 {
19     int n;
20     while(cin>>n)
21     {
22         Solution s;
23         cout<<""<<n<<"级台阶需要步数:"<<s.jumpFloorII(n)<<endl;
24     }
25     return 0;
26 }

程序运行结果截图:

技术分享

 

9、剑指offer--变态跳台阶