数学归纳法 – 四火的唠叨

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

这道题还被 ITEye 放在了博文视点杯有奖答题活动里面。

我提供三种解法。

1、递归求解：

青蛙每跳一次前，有这样三种情况：

于是递归方法求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/** 
 * 递归方法 
 */
public static int calc(int n) {  

有道经典的算法题，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。假如运气最差的话，问要测试多少次才能找出这层楼来。

如果只有一个鸡蛋，我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置，第二个鸡蛋还是只能一层一层试验。

这道问题其实可以扩展到任意个鸡蛋，但现在还是只看 2 个鸡蛋的情况。

2 个鸡蛋只有 n 层的最优解求出来假使为 k，那么，n+1 层的时候，把第一个鸡蛋在第 k 层释放，只有两种情况（n+1 只是分解成两个<=n 的子问题，这两个都是已经有解了的）：

（1）破碎，于是只有之后就只能遍历从地面到第 k-1 层，一层层遍历，不能偷懒，最坏的情况在此要尝试 k 次；

（2）没碎，那问题

Tag: 数学归纳法