青蛙跳台阶问题的三种解法

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

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

 

我提供三种解法。

 

1、递归求解：

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

（1）只剩1级或0级台阶了，只能跳一步或者无法再跳了，那么这条路也走到了终点，走法的种类数可以加1；

（2）可以走2级台阶；

（3）可以走1级台阶。

于是递归方法求解：

	/**
	 * 递归方法
	 */
	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内部无序：

	/**
	 * 概率论
	 */
	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)，从时间、空间复杂度来说，这也是最简单的一种方法：

	/**
	 * 数学归纳法
	 */
	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;
	}

 

 

聪明的你，还有什么办法？

欢迎和我讨论。 :)

 

文章系本人原创，转载请注明作者和出处

评论

6 楼 RayChase 2012-01-18  

lethorld 写道

既然都知道是斐波拉契数列了，那就给个通式吧：
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(1)

Good!

5 楼 lethorld 2012-01-17  

既然都知道是斐波拉契数列了，那就给个通式吧：
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(1)

4 楼 lethorld 2012-01-17  

lethorld 写道

RayChase 写道

lethorld 写道

这是个费布拉奇数列：

F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}
     = F(N - 1) + F(N - 2)

解释如下：

第N级台阶的走法可以分为：

1)当前青蛙在N-2级台阶上，那么它跳到N级台阶有两种方法：
  I N-2 + (1) + (1) -- 跳一级到N-1，再跳一级到N
  II N-2 + (2) -- 直接跳到N级台阶
  所以有两种：即 2 * F(N-2)
2)当前青蛙在N-1级台阶上，那它只能跳一次到N级上（但是这里面包含了上面提到的第I中情况，所以要减掉F(N - 2)
  即：1 * {F(N-1) - F(N - 2)}

所以最后是：
F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2

是的，不过你好像想复杂了
跳到第N级话，
可以先跳N-1级，再跳1级；
也可以先跳N-2级，再跳2级。
所以f(n)=f(n-1)+f(n-2)，就是斐波那契数列。

嗯，这样也行。但其实仔细想想，你提的和我提的是不完全一样的。可以仔细考虑如下问题：
一个青蛙，它可以跳1、2、3、...、m步，这时候，问它跳到N级台阶的时候有多少种方法？

你看看这个，就知道我开始列的那个式子的含义了。

其实和你的第三种数学归纳法是异曲同工的，只是过程不一样罢了~~

3 楼 lethorld 2012-01-17  

RayChase 写道

lethorld 写道

这是个费布拉奇数列：

F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}
     = F(N - 1) + F(N - 2)

解释如下：

第N级台阶的走法可以分为：

1)当前青蛙在N-2级台阶上，那么它跳到N级台阶有两种方法：
  I N-2 + (1) + (1) -- 跳一级到N-1，再跳一级到N
  II N-2 + (2) -- 直接跳到N级台阶
  所以有两种：即 2 * F(N-2)
2)当前青蛙在N-1级台阶上，那它只能跳一次到N级上（但是这里面包含了上面提到的第I中情况，所以要减掉F(N - 2)
  即：1 * {F(N-1) - F(N - 2)}

所以最后是：
F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2

是的，不过你好像想复杂了
跳到第N级话，
可以先跳N-1级，再跳1级；
也可以先跳N-2级，再跳2级。
所以f(n)=f(n-1)+f(n-2)，就是斐波那契数列。

嗯，这样也行。但其实仔细想想，你提的和我提的是不完全一样的。可以仔细考虑如下问题：
一个青蛙，它可以跳1、2、3、...、m步，这时候，问它跳到N级台阶的时候有多少种方法？

你看看这个，就知道我开始列的那个式子的含义了。

2 楼 RayChase 2012-01-17  

lethorld 写道

这是个费布拉奇数列：

F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}
     = F(N - 1) + F(N - 2)

解释如下：

第N级台阶的走法可以分为：

1)当前青蛙在N-2级台阶上，那么它跳到N级台阶有两种方法：
  I N-2 + (1) + (1) -- 跳一级到N-1，再跳一级到N
  II N-2 + (2) -- 直接跳到N级台阶
  所以有两种：即 2 * F(N-2)
2)当前青蛙在N-1级台阶上，那它只能跳一次到N级上（但是这里面包含了上面提到的第I中情况，所以要减掉F(N - 2)
  即：1 * {F(N-1) - F(N - 2)}

所以最后是：
F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2

是的，不过你好像想复杂了
跳到第N级话，
可以先跳N-1级，再跳1级；
也可以先跳N-2级，再跳2级。
所以f(n)=f(n-1)+f(n-2)，就是斐波那契数列。

1 楼 lethorld 2012-01-17  

这是个费布拉奇数列：

F(N) = 2 * F(N-2) + 1 * {F(N-1) - F(N - 2)}
     = F(N - 1) + F(N - 2)

解释如下：

第N级台阶的走法可以分为：

1)当前青蛙在N-2级台阶上，那么它跳到N级台阶有两种方法：
  I N-2 + (1) + (1) -- 跳一级到N-1，再跳一级到N
  II N-2 + (2) -- 直接跳到N级台阶
  所以有两种：即 2 * F(N-2)
2)当前青蛙在N-1级台阶上，那它只能跳一次到N级上（但是这里面包含了上面提到的第I中情况，所以要减掉F(N - 2)
  即：1 * {F(N-1) - F(N - 2)}

所以最后是：
F(N) = F(N - 1) + F(N - 2)
F(1) = 1
F(2) = 2