首先申明,一下是我个人分析得出,但是根据正确答案是2^n,所以以下个人分析过程仅供参考,并非正确.
2. 青蛙跳阶问题。
(1)一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
(2)一只青蛙一次可以跳上1级台阶,也可以跳上2 级……它也可以跳上n 级,此时该青蛙跳上一个n级的台阶总共有多少种跳法?
对于这个问题进行解答:
1. 假定青蛙跳阶的跳法以f(n)来表示,n表示阶数,即f(1)表示1阶的跳法,f(2)表示2阶的跳法...
2. 由于对于第二个问题有一次n级跳法,所以这里设定一个值f(0)=f(n-n)=1 表示n阶由一次跳上n级的跳法数为1。
--------------------------------------------问题(1)解答------------------------------------------------------------
问题(1),前提只有 一次 1阶或者2阶的跳法。
a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);
b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列:
| 1, (n=1)
f(n) = | 2, (n=2)
| f(n-1)+f(n-2) ,(n>2,n为整数)
----------------------------------------------问题(2)解答------------------------------------------------------------
问题(2),前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
说明:
1)这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
2)n = 1时,只有1种跳法,f(1) = 1
3) n = 2时,会有两个跳得方式,一次1阶或者2阶,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2)
4) n = 3时,会有三种跳得方式,1阶、2阶、3阶,
那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)
因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
5) n = n时,会有n中跳的方式,1阶、2阶...n阶,得出结论:
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
6) 由以上已经是一种结论,但是为了简单,我们可以继续简化:
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出:
f(n) = 2*f(n-1)
7) 得出最终结论,在n阶台阶,一次有1、2、...n阶的跳的方式时,总得跳法为:
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1),(n>=2)
------------------------------------------------------------------------------------------------------------------------
分享到:
相关推荐
青蛙跳测试智商青蛙跳测试智商青蛙跳测试智商青蛙跳测试智商
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法? 若把条件修改成一次可以跳一级,也可以跳2级...也可以跳上n级呢?
Unity模仿Flash小游戏《青蛙跳》而实现的算法,其实很简单,看代码就知道
青蛙跳HTML5游戏源码,运行需要服务器环境,已经反复测试,放心使用。
同学让我帮忙写了一个模拟青蛙跳实现过程的小程序,在网上找了找没找到,于是自己写了一个,可以让左侧的青蛙先跳,也可以让右侧的青蛙先跳,通过动态的青蛙来展现整个实现过程。
青蛙跳,想必很多人小时候都玩过。现在这个是我做的android 小游戏,喜欢玩得朋友可以下载。学习android的一定要下载哦,里面带有源码的
一种新型仿青蛙弹跳腿设计,张伟,樊继壮,设计了一种新型仿青蛙弹跳腿,腿机构采用气动肌肉作为跳跃驱动单元,并采取双关节驱动形式,在增加气动肌肉驱动关节转角的大小同
青蛙跳台阶问题(斐波那契数列变形)一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。示例 1:输入:n = 2 输出:2示例 2:输入:n = 7 输出
小游戏源码-青蛙跳.rar
【基础算法】-python青蛙跳台阶 way = 0 def traceback(n, step_num): global way if n > step_num: return if n == step_num: way += 1 return traceback(n+1, step_num) traceback(n+2, step_num) ...
Flash游戏制作教程:青蛙跳荷叶.pdf
小学数学一年级青蛙跳—数轴练习题一步计算两步计算.doc
面试题10- II. 青蛙跳台阶问题题目链接面试题10- II. 青蛙跳台阶问题题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。示例 1:输入:n =
用C#开发的一款小游戏,可以实现青蛙在石头上的跳动,是一款智力小游戏。
可以复制到FLASH中,简单方便效果还不错,希望你们可以用到
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。 示例 1: 输入:n = 2 输出:2 ...
表格模板-青蛙跳河.ett
讓左右兩邊青蛙交換位置,通常年薪50万水準的人,三分鐘內可以完成 ^_^ 。...1:用鼠标点青蛙头部,它会向前跳; 2:它最多只能跳过一个青蛙; 3:按红色箭头,游戏复原。 4:此题肯定有解,不要怀疑。
二、青蛙跳台阶算法 类似于Fibonacci数列的算法问题 台阶数为number或n,跳法数为ret,f(n)代表跳到第n阶台阶的跳法数 算法流程分析 由于青蛙每次只能跳一个台阶或者两个台阶,故 f(n) = f(n-1) + f(n-2) 注:青蛙...
小学数学一年级青蛙跳数轴练习题集一步计算两步计算.doc