抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

青蛙跳台阶问题

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

解法:数学归纳法 wiki

首先我们考虑最简单的情况。

如果只有1级台阶,那显然只有一种跳
法。如果有2级台阶,那就有两种跳法: 一种是分两次跳,每次跳1级;
另一种就是一次跳2级。

接着我们再来讨论一般情况。

我们把n级台阶时的跳法看成n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:
一是第一次只跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);
二是第一次跳2级,此时跳法数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2)。
因此,n级台阶的不同跳法的总数如f(n)=f(n-1)+f(n-2)。

所有其实这题答案为:斐波那契数列

扩展题:

在青蛙跳台阶的问题中,如果把条件改成:
一只青蛙一次可以跳上1级台阶,也可以跳上2级… …它也可以跳上n级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?

解法:数学归纳法

简单情况:

当只有一级台阶时,只有一种情况,跳一级。f(1)=1;

当有两级台阶时,可以跳一级跳两次,也可以直接跳两级。f(2)=2;

当有三级台阶时,第一步可以分三种方法跳:

  • 1、第一步跳一级,后面按2级台阶算,记f(2)。
  • 2、第一步跳两级,后面按一级台阶算,记f(1)。
  • 3、第一步跳三级,直接跳完。

所以总共为:f(2)+f(1)+1=4;

当有四级台阶时,第一步分四种跳法:

  • 1、第一步跳一级,后面按3级台阶算,记f(3)。
  • 2、第一步跳两级,后面按两级台阶算,记f(2)。
  • 3、第一步跳三级, 后面按一级台阶算,记f(1)。
  • 4、第一步跳四级,直接跳完。

所以总共为:f(3)+f(2)+f(1)+1=8;

以上,我们用数学归纳法可以证明f(n)=2的n-1次方。

代码:乘法求阶层:

private static double pow(double num, int m) {
if (m < 0) {
return -1;
}
if (m == 0) {
return 1;
}
for (int i = 1; i < m; i++) {
num *= num;
}
return num;
}

以上为剑指offer青蛙跳台阶部分题目。


0条评论

发表评论