青蛙跳台阶问题。
一只青蛙一次可以跳上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条评论