欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-26 21:48:34
...

题目:一只青蛙一次可以跳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;
	}

 

 

聪明的你,还有什么办法?

欢迎和我讨论。 :)

 

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