今天无意中看到这个连接。
http://www.iteye.com/topic/1118928 看到了爬楼梯的算法比较有意思。就研究了下。呜呜。摆置半天没有写出来。悲催啊。看来好长时间不看。以前的知识都荒废了。
转载
http://283433775.iteye.com/blog/1313748 对这个问题的分析。
对于这个问题进行解答:
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)
java 核心代码:
public static int getMethodCount(int total, StringBuffer str) {
if (0 == total) {
System.out.println(str);
return 1;
} else if (1 == total) {
System.out.println(str.append("1"));
return 1;
} else {
StringBuffer strBuffA = new StringBuffer(str);
StringBuffer strBuffB = new StringBuffer(str);
return getMethodCount(total - 1, strBuffA.append("1\t"))
+ getMethodCount(total - 2, strBuffB.append("2\t"));
}
}
public static int getMethodCountN(int total,StringBuffer str){
if(0== total){
System.out.println(str);
return 1;
}
else if(1 == total){
System.out.println(str.append("1"));
return 1;
}
else{
StringBuffer buffer = new StringBuffer(str);
return 2*getMethodCountN(total-1,str);
}
}
分享到:
相关推荐
标题中的“爬楼梯”问题,通常在编程竞赛和信息学奥赛中被用作一个经典的算法题目。这个题目源于实际生活中的场景,旨在考察选手的逻辑思维和算法设计能力。爬楼梯问题的基本设定是:一个人要爬上一个有若干阶的楼梯...
html css js网页设计
python爬楼梯问题假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?示例 1:输入:n = 2输出:2解释:有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶...
在编程领域,动态规划是一种强大...总的来说,"js代码-算法-动态规划-爬楼梯"这一主题为我们提供了一个学习和理解动态规划概念的良好起点。通过分析和实践这段代码,开发者可以进一步提升在算法和问题解决方面的能力。
leetcode算法题爬楼梯,第一次提交,如有不足还请多多包涵!
在这个“c语言基础_c语言编程基础之动态规划示例_爬楼梯”的主题中,我们将深入探讨如何利用C语言实现动态规划方法,通过爬楼梯问题来讲解这一概念。 首先,让我们理解一下爬楼梯问题。假设有一座有n级台阶的楼梯,...
在编程领域,爬楼梯算法(也称为斐波那契数列)是一个常见的问题,它用于演示动态规划或递归的概念。在这个问题中,一个人要爬到一个有n级台阶的楼梯,每次可以爬1级或者2级。目标是找出到达顶部的不同方法数。 这...
总之,“js代码-爬楼梯台阶走法”是一个关于算法和编程的问题,通过不同的方法可以解决这个经典问题,展示了JavaScript在处理递归、动态规划和记忆化搜索等算法时的能力。在实际编程中,我们需要根据问题规模和性能...
php 算法 爬楼梯有多少种方法
在LeetCode上,"最低成本-爬楼梯"是一道经典的算法问题,主要考察动态规划的运用。本题目的目标是找到以最小代价爬完给定楼梯的方法。在这里,每层楼梯都有一个相应的成本,你可以选择每次爬1阶或2阶。我们需要找出...
下面我们将深入探讨回溯算法的概念、应用场景以及如何用C语言来实现爬楼梯问题。 回溯算法主要应用于解决组合优化问题,如八皇后问题、迷宫求解、图的着色问题等。其核心特点是通过递归或迭代的方式遍历所有可能的...
【标题】"js代码-16.1 动态规划-爬楼梯" 涉及的是使用JavaScript实现动态规划算法解决经典问题“爬楼梯”。在这个问题中,一个人要爬上一个有n级台阶的楼梯,每次可以跳1级或2级。任务是找出到达顶层有多少种不同的...
机器人技术与爬楼梯机器人的创新设计 机器人技术是计算机技术、光机电一体化技术、先进制造技术及人工智能等技术的交叉汇集,已经在社会不同领域得到了广泛应用,如医疗服务、家庭服务、教育娱乐、勘探勘测、生物...
70爬楼梯.zip(算法)
爬楼梯问题描述如下:假设你正在爬楼梯,需要 n 阶你才能到达顶部。每次你可以爬 1 阶或者 2 阶。编写一个函数来计算你达到顶部的不同方法数。这个问题可以看作是斐波那契序列的一个变种,因为它同样涉及到前两个...
### 动态规划算法入门指南:从斐波那契数列到爬楼梯问题 #### 一、动态规划算法概述 动态规划(Dynamic Programming,简称DP)是一种强大的算法思想和技术,常用于解决各种优化问题,例如寻找最优解或最大化/最小...