《剑指offer》面试题10:题目3青蛙变态跳台阶（C++实现））

题目描述题目分析分析思路1：青蛙对每级台阶可选择过或者不过分析思路2：数学归纳法证明 解决思路思路一：循环实现2的正整数次幂思路二：用位操作执行更快小结参考文献

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目分析

分析思路1：青蛙对每级台阶可选择过或者不过

换个角度来看，题目的问题等价于，青蛙现在在起点n=0处。目标是n=n处。那么经过序号1，2，3…n-1层台阶。对于每一层台阶，都可以随意选择通过，或者不通过。即2的（n-1）次幂种跳法。 即： f(n)=2^(n-1)

分析思路2：数学归纳法证明

下面是严格的数学归纳法证明:

我们设青蛙需要跳上的台阶级数为n,f(n)代表一个青蛙跳上n级台阶的跳法数目。 类似于之前的普通青蛙跳台阶，我们根据青蛙的第一步跳多少台阶分情况进行分析。 青蛙的第一步可以跳1层，2层…n层 （1）青蛙第一步跳到1层，剩下的跳法为f(n-1) (2) 青蛙第一步跳到2层，剩下的跳法为f(n-2) … （n-1）青蛙第一步跳到n-1层，剩下的跳法为f(1) 那么综上得到 式1：f(n)=f(n-1)+f(n-2)+…f(1) 同理对于f(n-1)有 式2：f(n-1)=f(n-2)+f(n-3)+…f(1) 由上述两式得到：f(n)=2*f(n-1) 依次类推得到：f(n)=f(1)*2^(n-1)=2^(n-1)

综上所述，不管是哪种分析思路，我们都得到了 当n>=1时，f(n)和n之间的关系 f(n)=2^(n-1)

解决思路

经过刚才的分析，其实题目已经很简单了。 问题转化为了求解2的正整数次幂。

思路一：循环实现2的正整数次幂

所以我们很快能写出如下的代码：

//运行时间：3ms //占用内存：376K class Solution { public: int jumpFloorII(int number) { if(number<=0) return 0; int result = 1; for(int i=1;i<number;i++){ result =result *2; } return result; } };

思路二：用位操作执行更快

//运行时间：4ms //占用内存：484K class Solution { public: int jumpFloorII(int number) { int a=1; return a<<(number-1); } };

小结

所以这道题的难点在于建立模型本身，而不是在于代码实现。 如果能够观察到f(n)与n 之间的关系，那么问题也就迎刃而解了。

参考文献

《剑指offer》

牛课网刷题链接link.