`

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

 
阅读更多

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

 

 

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

欢迎和我讨论。 :)

 

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

1
顶
0
踩
分享到：
| 同步和异步的好处
评论
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
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    青蛙为什么要跳台阶？C语言趣解青蛙跳台阶问题.pdf

    2. 青蛙跳台阶问题的递归解法： - 递归是一种自顶向下的解法，直观易懂但效率低下，因为存在大量的重复计算。 - 以递归方式解决此问题时，需要从f(n)递归地计算f(n-1)和f(n-2)，直到计算出基本情况f(1)和f(2)。 3...

    【算法题】青蛙跳台阶问题（附过程取模证明）

    综上所述，青蛙跳台阶问题是一个结合了动态规划和模运算的算法问题，其解法的关键在于理解递推关系并正确处理取模操作，以避免数值溢出。通过这样的方法，我们可以有效地计算出任何不超过100级台阶的跳法数量。

    Python中跳台阶、变态跳台阶与矩形覆盖问题的解决方法

    这篇文章主要介绍了在Python语言中解决三个经典的递归问题：跳台阶问题、变态跳台阶问题以及矩形覆盖问题。这三个问题虽然描述不同，但实际上都可以归结为斐波那契数列的变种。通过示例代码的形式，作者详细地介绍了...

    Fibonacci题目合集.zip

    这个压缩包“Fibonacci题目合集.zip”显然包含了一系列与斐波那契相关的编程挑战，包括基本的斐波那契数列计算、青蛙跳台阶问题、变态跳台阶问题以及矩形覆盖问题。让我们逐一探讨这些知识点。 1. **斐波那契数列**...

    青蛙爬楼梯(C++源码)

    cout 青蛙跳上" 级台阶共有" (n) 种跳法。\n"; return 0; } ``` 这段代码首先定义了一个函数`jumpSteps`，用于计算n级台阶的跳法。然后在`main`函数中获取用户输入的台阶数，并调用`jumpSteps`函数，最后输出结果...

    BAT常见的面试问题及其解答

    题目描述：青蛙一次可以跳1级或2级台阶，求解跳上n级台阶有多少种跳法。 解答：这是经典的斐波那契数列问题。斐波那契数列的定义是F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n&gt;=2)。可以使用递归、动态规划或迭代方法...

    lyj2014211626#Prepare_For_AI_Job#剑指 Offer 46. 把数字翻译成字符串1

    剑指 Offer 46. 把数字翻译成字符串参考链接解法一：动态规划类似于青蛙跳台阶，但是有些许的改变，就是判断n-2的值是&gt;=10 && &lt;= 25int t

    简单的算法集合（c语言）

    8. **台阶问题**：又称“青蛙跳台阶”问题，假设青蛙每次可以跳1步或2步，问到达n阶台阶有多少种跳法。可以使用斐波那契数列来解决，C语言实现需要理解和应用递推关系。 每个算法的实现都需要理解问题本质，选择...

    动态规划30道经典问题图解解析(bigsai本人原创)

    2. **爬楼梯、跳台阶问题**：这类问题类似于斐波那契数列，但需要自行推导初始状态和状态转移方程。假设青蛙每次可以跳1步或2步，目标是找到到达指定台阶的最小跳跃次数。动态规划的解法是定义一个数组dp，其中dp[i]...

    leetcode第685题-leetcode-js:力扣js解题记录

    leetcode第685题 leetcode-js 力扣js解题记录 树 -&gt; 图论 -&gt; 递归 -&gt; 回溯 -&gt; DFS -&gt; BFS -&gt; 贪心 -&gt; 动态规划 -&gt; 字符串 -&gt; 数组 -&gt; 滑动窗口 1. 树 递归解法,迭代解法 ...青蛙跳台阶问题 面试题 16

    algorithmAndDataStructure:算法和数据结构学习记录

    青蛙跳台阶问题 q72 编辑距离 q17 电话号码的字母组合(复习 3) 在有序不重复的数组中查找指定元素，返回元素下标 查找第一个值等于给定值的元素 查找最后一个值等于给定值的元素 查找第一个大于等于给定值的元素 ...

    剑指Offer(Python多种思路实现):斐波那契数列

    **题目拓展2：变态跳台阶** 这个问题类似于斐波那契数列，但每次可以跳跃1到n级台阶。解法同样使用斐波那契的概念，因为青蛙跳跃的步数组合方式符合斐波那契序列的特性。对于n级台阶，总共有2^(n-1)种跳法。 ```...

Magicbox
Global site tag (gtag.js) - Google Analytics