今天无意中看到这个连接。
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);
}
}
分享到:
相关推荐
算法-爬楼梯(信息学奥赛一本通-T1204)(包含源程序).rar
html css js网页设计
js代码-算法-动态规划-爬楼梯
leetcode算法题爬楼梯,第一次提交,如有不足还请多多包涵!
本文实例讲述了Python3爬楼梯算法。分享给大家供大家参考,具体如下: 假设你正在爬楼梯。需要 n 步你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数...
php 算法 爬楼梯有多少种方法
//如果n的取值从32~36,m的取值从2~3,请写程序输出每种情况下小明有多少种爬楼梯的方法。 //输入格式:共2行数据,内容如下: //10 32 32 33 33 34 34 35 35 36 36 //10 2 3 2 3 2 3 2 3 2 3 //每行第一个元素...
js代码-(算法)(动态规划)爬楼梯
这是我用c语言写的程序,我的其他资源都是免费的,是对于c语言初学者的帮助比较大的,其中有数据结构,window编程。我也在学c语言,每当我写完一个程序,我都会免费发上来。
使用动态规划解决经典问题,例如爬楼梯、打家劫舍问题、单词拆分问题、买卖股票问题等 动态规划是一种算法设计技术,它通过将问题分解为重叠的子问题并利用已经解决的子问题的结果来解决更大的问题。 通常用于解决...
爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。...这题爬楼梯算是算法题里面比较经典的。 解题思路 这题的解题思路主要有两种: 1.动态规划 2.斐波那契数
leetcode爬楼梯排列组合解法 Data Structure and Algorithmic Practice 【任务1 - 数组与链表】 1、数组 实现一个支持动态扩容的数组 实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个...
爬楼梯.md
动态规划(Dynamic Programming,简称DP)算法是一种通过将问题划分为相互重叠的子问题,并解决子问题来解决原问题的方法。它通常用于优化问题,其中需要找到最优解或最大/最小值。动态规划算法的核心思想在于将复杂...
用回溯法解决01背包问题,用c语言编写的源代码
对于动态规划算法的经典问题中,找到爬到楼梯顶层的方法有多少种事一个比较基础也是比较经典的一个一维动态规划问题。问题的主要描述为,假如要爬一个n层的楼梯,每次只能走一个或者两个楼梯,总共有多少种方法可以...