文档章节

小孩上楼梯的方式的种类

一贱书生
 一贱书生
发布于 2016/11/22 09:34
字数 984
阅读 10
收藏 0
点赞 0
评论 0

梯有N阶,上楼可以一步上一阶,也可以一次上二阶(Java实现)
 

例3:一共有10级,每次可走一步也可以走两步.必须要8步走完10级楼梯. 问:一共有多少种走法?

分析:走一步的需要6次,走两步的需要2次。因此,本题是6个1、2个2的组合问题。在6个一步中,插入2个两步的,因可放在第一个1步之前,也可以放在最后一个1步之后,所以6个1步有7个空.因此,如果两个两步在一起有c(7,1)种;如果两个两步的分开来插有C(7,2)种,因此共有

    c(7,1)+c(7,2)=7+21=28(种)=C(8,2)=C(8,6) 
    总数=8步中选2中走两步的=8步中选6个走一步的

 

Java编程实现:(数组迭代,动态规划,递归)

package com.test;

public classzoutaijie {

// 梯有N阶,上楼可以一步上一阶,也可以一次上二阶。编一个程序,计算共有多少种不同的走法。如果上20阶会有几种走法

public staticlongresult[]=new long[100];

public staticvoidmain(String[] args) {

result[0]=result[1]=1;

for(inti=2;i<</span>result.length;i++)

result[i]=-1;

//s不能太大,否则int溢出

int s =60;

//动态规划

long startTime = System.currentTimeMillis();

System.out.println("动态规划解决:"+fun1(s));

long endTime = System.currentTimeMillis();

System.out.println("动态规划解决-程序运行时间:"+(endTime-startTime)+"ms");

 

//数组叠加

long startTime2 = System.currentTimeMillis();

System.out.println("数组叠加实现:"+fun2(s));

long endTime2 = System.currentTimeMillis();

System.out.println("数组叠加实现-程序运行时间:"+(endTime2-startTime2)+"ms");

 

//递归方法

long startTime1 = System.currentTimeMillis();

System.out.println("递归方法解决:"+fun(s));

long endTime1 = System.currentTimeMillis();

System.out.println("递归方法解决-程序运行时间:"+(endTime1-startTime1)+"ms");

}

 

 

 

public staticlongfun(ints){

if(s==0 || s==1)

return 1;

else{

return fun(s-1)+fun(s-2);

}

 

}

 

public staticlongfun1(ints){

if(result[s]>=0) {

return result[s];

}else{

result[s]=(fun1(s-1)+fun1(s-2));

return result[s];

}

}

 

 

public staticlongfun2(ints){

long result_1[]=newlong[s+1];//注意这个要大一个,多了个第0

result_1[0]=result_1[1]=1;

for(inti=2;i<=s;i++)

result_1[i]=result_1[i-1]+result_1[i-2];

return result_1[s];//s就是第s+1

}

 

}

 

 

 

分析:

  (1) int s=48时候的运行效果:

 

 梯有N阶,上楼可以一步上一阶,也可以一次上二阶(Java实现)


 

(2). int s=60时候的运行效果

 

 梯有N阶,上楼可以一步上一阶,也可以一次上二阶(Java实现)

 

  显然数组叠加和动态规划效率高很多很多,不是一个数量级的!

 

 

/**

 * 功能:有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。计算小孩上楼梯的方式有多少种。

 */

 

三种方法:

 

方法一:

//递归法
	/**
	 * 思路:自上而下的方式。
	 * 最后一步可能是从第n-1阶往上走1阶、从第n-2阶往上走2阶或从第n-3阶往上走3阶。
	 * 因此,抵达最后一阶的走法,抵达这最后三阶的方式的综合。
	 * @param n
	 * @return
	 */
	public static int countWays(int n){
		if(n<0)
			return 0;
		else if(n==0)//注意此处条件
			return 1;
		else{
			return countWays(n-1)+countWays(n-2)+countWays(n-3);
		}
	}

 

方法二:

//动态规划
	/**
	 * 思路:每次调用都会分支出三次调用。予以动态规划加以修正。
	 * @param n
	 * @param map
	 * @return
	 */
	public static int countWaysDP(int n,int[] map){
		if(n<0)
			return 0;
		else if(n==0)
			return 1;
		else if(map[n]>-1)
			return map[n];
		else{
			map[n]=countWaysDP(n-1,map)+countWaysDP(n-2,map)+countWaysDP(n-3, map);
			return map[n];
		}
	}

 

方法三:

  1. package com.tian;
  2.  
  3. import java.util.TreeMap;
  4.  
  5. /**
  6. * 爬楼梯的算法(有一个人要爬楼梯,楼梯有N个台阶,此人最多可以爬M个台阶
  7. * 问这个人上楼有多少中上法)
  8. * @author Administrator
  9. *
  10. */
  11. public class Test {
  12.  
  13.  
  14.  
  15. public static void main(String[] args) {
  16. System.out.println(new Test().suanfa(3,1));
  17. }
  18.  
  19. /**
  20. * 得到所有能相加等于这个数的2个非自然正数
  21. * @param n
  22. */
  23. public void fenjie(final int n){
  24.  
  25. for (int i = 1; i <=n; i++) {
  26.  
  27.  
  28. System.out.println(i+","+(n-i));
  29. }
  30. }
  31.  
  32. /**
  33. *
  34. * @param n 总台阶数
  35. * @param m 最多能走的步数
  36. * @return 返回能走方法数
  37. */
  38. public int suanfa(final int n,final int m){
  39.  
  40. switch (n) {
  41. case 1:
  42. return 1;
  43.  
  44. case 2:
  45. if(m>=2){
  46. return 2;
  47. }
  48. else{
  49. return 1;
  50. }
  51. }
  52. int result=0;
  53. for (int i = 1; i <n; i++) {
  54. int a=i;
  55. int b=n-i;
  56.  
  57. System.out.println(i+","+(n-i));
  58. result+=suanfa(a, m)*suanfa(b, m);
  59. }
  60. return result;
  61.  
  62.  
  63.  
  64. }
  65. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
你对爱人的态度,决定了你的婚姻质量

01 在好友大妮家做客时,她老公刚购物回来,气呼呼地拎着大包小包爬楼梯上来。 东西刚放下,大妮在房间里叫他,“老头,赶紧拿片纸尿裤来”。 大妮她老公一听立马拿了尿裤进房间去,那动作干...

洪生鹏
06/14
0
0
重磅!优必选CES推出双足机器人Walker,准备卖给全球高端消费人群

     CES 2018优必选展位   美国时间2018年1月9日,国际消费类电子产品展览会(简称CES)在拉斯维加斯开幕。优必选作为全球领先的人工智能和人形机器人研发、制造和销售为一体的高科技...

人工智能机器人联盟
01/10
0
0
Jzoj3528 图书馆

圣玛格丽特大图书馆是一座由石材砌成的角柱型高塔,是欧洲屈指可数的巨大书库。图书馆整面墙壁都是巨大的书架,书架与书架之间就像巨大的迷宫一般,以细窄的木制楼梯连结。大图书馆的最高处是...

JacaJava
01/22
0
0
codevs4438 YJQ Runs Upstairs

Description 学校科技楼一共有 层,而神犇YJQ每天都在科技楼 楼的机房写代码。这天,他准备从科技楼 楼爬到 楼。有个 连接不同楼层的楼梯,爬每个楼梯需要一定的体力值。楼梯一定是从低处通往高...

aziint
01/06
0
0
程序员,你有多久没关爱自己了?

随着互联网应用在近年间改变了各行各业,尤其是移动互联网,更是让互联网与人们生活紧密相联。促成互联网辉煌的背后的程序员们,也获得了人们的重视,成为一个令人羡慕的职业。尤其是总理倡导...

OneAPM蓝海讯通
2015/10/22
33
0
这台会尬舞的机器人,长了六只脚

width="649px" class=" imgloading" src="http://ss.csdn.net/p?http://mmbiz.qpic.cn/mmbizjpg/18iaLicz4PyRKjUYsBtmjvZktINlxAkeZjbJS3kjkU3AkWAQjFoGr8xibbfOCKsFibpGyLrFSTIVfQ15LAdJXP6......

R5A81qHe857X8
2017/12/21
0
0
Leetcode 746: Min Cost Climbing Stairs(详解)

题目描述 一个楼梯,第i阶都有一个非负的花费cost[i],从0开始索引。 一旦你支付了花销,你就可以跳上一阶或者两阶。你需要找到到达楼梯顶的最小花费,你可以选择从楼梯第0阶或者第1阶开始。 ...

117
06/29
0
0
月影MM对面向对象,原型,函数式的理解

“面向对象”其实好比是人类成年期学习和整理知识的方法 ——把知识分门别类 比如猫、老虎,都属于猫科动物 class 猫 extends 猫科动物 class 老虎 extends 猫科动物 描述的就是这种认知世界...

尐桀
2014/10/29
0
0
杨利甲的故事

以下内容转贴自"感恩中国",国内我唯一敬重的网站。 ==================== 1. "大兄弟,你看这时候的天,突然就变黑了,我估计晚上可能下大雨,所以我得赶快回小旅馆去,否则等会就要挨雨淋了...

阮一峰
2007/09/09
0
0
(百度算法题)有三种走楼梯方式,走完100阶总共有多少种走法

原题: 有一100阶层的楼梯,有三种走楼梯方式,一次走一阶,一次走两阶,一次走三阶。用算法实现,走完100阶总共有多少种走法 解答: f(n)=f(n-1)+f(n-2)+f(n-3) 有两个要点:1,结果大于i...

技术小阿哥
2017/11/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java集合元素的默认大小

当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存),要将容器原来的数据全部复制到新的内存上,这无疑使...

竹叶青出于蓝
6分钟前
1
0
Java快速开发平台,JEECG 3.7.7闪电版本发布,增加多套主流UI代码生成器模板

JEECG 3.7.7 闪电版本发布,提供5套主流UI代码生成器模板 导读 ⊙平台性能优化,速度闪电般提升 ⊙提供5套新的主流UI代码生成器模板(Bootstrap表单+BootstrapTable列表\ ElementUI列表表单)...

Jeecg
9分钟前
0
0
export 和 module.export 的区别

在浏览器端 js 里面,为了解决各模块变量冲突等问题,往往借助于 js 的闭包把左右模块相关的代码都包装在一个匿名函数里。而 Nodejs 编写模块相当的自由,开发者只需要关注 require,exports,...

孟飞阳
12分钟前
0
0
技术教育的兴起

技术教育的兴起 作者: 阮一峰 1、 有一年,我在台湾环岛旅行。 花莲的海边,我遇到一对台湾青年夫妻,带着女儿在海滩上玩。我们聊了起来。 当时,我还在高校当老师。他们问我,是否觉得台湾...

吕伯文
12分钟前
0
0
Linux服务器下的HTTP抓包分析

说到抓包分析,最简单的办法莫过于在客户端直接安装一个Wireshark或者Fiddler了,但是有时候由于客户端开发人员(可能是第三方)知识欠缺或者其它一些原因,无法顺利的在客户端进行抓包分析,...

mylxsw
16分钟前
0
0
mybatis3-javaapi

sqlSessionFactoryBuilder->sqlSessionFactory->sqlSession<-rowbound<-resultHandler myBatis uses a Java enumeration wrapper for transaction isolation levels, called TransactionIsol......

writeademo
20分钟前
0
0
Java NIO:浅析I/O模型

也许很多朋友在学习NIO的时候都会感觉有点吃力,对里面的很多概念都感觉不是那么明朗。在进入Java NIO编程之前,我们今天先来讨论一些比较基础的知识:I/O模型。下面本文先从同步和异步的概念...

yzbty23
20分钟前
0
0
了解iOS消息推送一文就够:史上最全iOS Push技术详解

本文作者:陈裕发, 腾讯系统测试工程师,由腾讯WeTest整理发表。 1、引言 开发iOS系统中的Push推送,通常有以下3种情况: 1)在线Push:比如QQ、微信等IM界面处于前台时,聊天消息和指令都会...

JackJiang-
22分钟前
0
0
Mysql汉子转拼音

update t_app_city SET CITY_NAME_BEGIN = ELT(INTERVAL(CONV(HEX(LEFT(CONVERT(CITY_NAME USING gbk),1)),16,10), 0xB0A1,0xB0C5,0xB2C1,0xB4EE,0xB6EA,0xB7A2,0xB8C1,0xB9FE,0xBBF7, 0xBFA......

尘叙缘
24分钟前
0
0
大数据构建智慧城市“新引擎”,加速推进新旧动能转换

——“大数据与智慧城市”技术交流分享会——济南站召开 7月13日,“大数据携手智慧城市,助力山东新旧动能转换”技术交流分享会——济南站在山东信息通信技术研究院会议室成功举办,此次会议...

左手的倒影
25分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部