青蛙跳台阶问题的三种解法
题目：一只青蛙一次可以跳 1 级台阶，也可以跳 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
这道题还被 ITEye 放在了博文视点杯有奖答题活动里面。
我提供三种解法。
1、递归求解：
青蛙每跳一次前，有这样三种情况：
- （1）只剩 1 级或 0 级台阶了，只能跳一步或者无法再跳了，那么这条路也走到了终点，走法的种类数可以加 1；
- （2）可以走 2 级台阶；
- （3）可以走 1 级台阶。
于是递归方法求解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | /** * 递归方法 */ public static int calc(int n) { return recursiveCalc(n, 0); } private static int recursiveCalc(int n, int total) { if (1 == n || 0 == n) return ++total; total = recursiveCalc(n - 1, total); return recursiveCalc(n - 2, total); } |
|---|
2、概率论思路求解：
首先把问题抽象成简单的数学模型，设 2 步台阶跳了 x 次，1 步台阶跳了 y 次，那么：
2x + y = n
于是，当 x = i ，可知 x >= 0 ，且 x < n/2（向下取整），设某时刻的 x = i ，那么有 y = n – 2 * x ，于是，总共需要走 z = i + n – 2 * x 步。
这时，问题即转化为：
z 步骤中，有 x 个两步，y 个一步，相当于 z 个空当，由 x、y 去填充，那么不同填充方法的数目符合概率公式：
C(x,z) = z! / ((z-x)!x!)
即从排列 z 中取其中 x 个数的种类，x 内部无序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /** * 概率论 */ public static int calc2(int n) { int total = 0; for (int i = 0; i <= n / 2; i++) total += factorial((i) + (n - 2 * i)) / factorial(i) / factorial(n - 2 * i); return total; } private static int factorial(int n) { if (0 == n) return 1; int total = 1; for (int i = 1; i <= n; i++) total *= i; return total; } |
|---|
3、数学归纳法求解：
如果 n=1，总步数 f(n)=1；如果 n=2，总步数 f(n)=2。
另一方面，当 n>=3，当前还剩的步数 f(n)，如果接下去跳一步，那么还剩下的步数是 f(n-1)；如果接下去跳两步，那么还剩下的步数是 f(n-2)，故：f(n)=f(n-1)+f(n-2)。
现设 s3=f(n)，s2=f(n-2)，s1=f(n-1)，从时间、空间复杂度来说，这也是最简单的一种方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | /** * 数学归纳法 */ public static int calc3(int n) { if (1 == n || 2 == n) return n; int s1 = 1, s2 = 2, s3 = 1; for (int i = 3; i <= n; i++) { s3 = s1 + s2; s1 = s2; s2 = s3; } return s3; } |
|---|
聪明的你，还有什么办法？
欢迎和我讨论。 :)
—————————————————————————————————————-
补充：
跳到第 N 级话，
可以先跳 N-1 级，再跳 1 级；
也可以先跳 N-2 级，再跳 2 级。
所以 f(n)=f(n-1)+f(n-2)，就是斐波那契数列。
既然都知道是斐波拉契数列了，那就给个通式吧：
F(N) =
((5+5^(1/2))/10)*(((1+5^(1/2))/2)^n) +
((5-5^(1/2))/10)*(((1-5^(1/2))/2)^n)
N >= 1
时间复杂度 O(log n)，因为求一个数的 n 次方，可以以时间复杂度为 log n 的方式来计算求解。
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
×Scan to share with WeChat