`
MouseLearnJava
  • 浏览: 465614 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

列出走楼梯或者台阶的所有走法

    博客分类:
  • Java
阅读更多

本篇文章主要用来简单模仿走楼梯或者台阶,列出走完楼梯或者台阶所有的走法。

第一个程序:给定台阶数,每次走1步,2步或者3步。
第二个程序:给定台阶数据,每次走的最小台阶数,每次走的最大台阶数以及设定最多能走几次。采用Stack来实现。

第一个程序和运行结果如下:
/**
 * 程序主要用来简单模仿走楼梯(台阶). 给定台阶数,每次走1步, 2步 或者 3步, 列出走完台阶所有的走法.
 * 
 * 例如3级台阶就有四种走法: 
 * 1 1 1 
 * 1 2 
 * 2 1 
 * 3
 * 
 * @author Eric
 * @version 1.0
 * 
 */
public class Stairs {

	// 统计个数
	private int currentCount = 1;
	
	/**
	 * @param remainingSteps
	 *            : 剩余的台阶数,开始调用的值是总的台阶数
	 * @param currentSteps
	 *            : 递归过程中某种情况下,已经走的步骤,如 1 2 走了三步的情况
	 */
	public void walkStairs(int remainingSteps, String currentSteps) {
		/*
		 * 当剩下小于等于三级台阶时,输出楼梯的走法
		 */
		if (remainingSteps <= 3) {
			printWalkWays(remainingSteps, currentSteps);
		} else {
			for (int step = 1; step <= 3; step++) {
				walkStairs(remainingSteps - step, currentSteps + " " + step);
			}
		}
	}

	private StringBuilder getCurrentCountStepInformation(String currentSteps) {
		return new StringBuilder().append("第").append(currentCount++).append(
				"种走法").append(currentSteps);
	}

	/**
	 * 输出满足条件的台阶走法
	 * 
	 * @param remainingSteps
	 * @param currentSteps
	 */
	private void printWalkWays(int remainingSteps, String currentSteps) {
		if (1 == remainingSteps) {
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 1").toString());
		} else if (2 == remainingSteps) {
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 1 1").toString());
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 2").toString());
		} else if (3 == remainingSteps) {
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 1 1 1").toString());
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 1 2").toString());
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 2 1").toString());
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.append(" 3").toString());
		} else {
			/**
			 * 0 ==remainingSteps, 表明已经走完台阶了,直接输出就可以了
			 */
			System.out.println(getCurrentCountStepInformation(currentSteps)
					.toString());
		}
	}

	public static void main(String args[]) {
		Stairs s = new Stairs();
		// 调用方法前需要先判断STEPS是否是大于0的。
		s.walkStairs(5, "");
	}
}


如走5阶台阶有如下几种走法:
第1种走法 1 1 1 1 1
第2种走法 1 1 1 2
第3种走法 1 1 2 1
第4种走法 1 1 3
第5种走法 1 2 1 1
第6种走法 1 2 2
第7种走法 1 3 1
第8种走法 2 1 1 1
第9种走法 2 1 2
第10种走法 2 2 1
第11种走法 2 3
第12种走法 3 1 1
第13种走法 3 2

第二个程序和运行结果如下:

/**
 * 题目:走楼梯
 *    给定台阶数目 -- SUM,
 *    每次最大的台阶数 -- MAX
 *    每次最小的台阶数 -- MIN
 *    期望值(最多在几步之内完成) -- EXPECT
 * 
 * 思路:
 *    采用递归的方法实现。采用Stack结构来存储。
 *        
 */

import java.util.Stack;

/**
 * 题目:走楼梯
 *    给定台阶数目 -- SUM,
 *    每次最大的台阶数 -- MAX
 *    每次最小的台阶数 -- MIN
 *    期望值(最多在几步之内完成) -- EXPECT
 * 
 * 思路:
 *    采用递归的方法实现。采用Stack结构来存储。
 *        
 * @author Eric
 * @version 1.0
 *
 */
public class Stair2 {

 private Stack<Integer> stack = new Stack<Integer>();

 private int currentCount = 0;

 /**
  * @param min
  * @param max
  * @param current
  * @param expect
  * @param sum
  */
 private void getWalkWays(int min, int max, int current, int expect, int sum) {
  //当Stack中的数据和与总的台阶数一样时,输出结果
  if (sum == current) {
   //输出满足条件的内容,其中,期望值(最多在几步之内完成)
   if ( expect >= stack.size()) {
    print(stack);
   }
  }
  //循环最小值到最大值
  for (int currentIndex = min; currentIndex <= max; currentIndex++) {
   /*
    * 如果当前Stack中的值的和(current)加上当前循环的值(currentIndex)
    * 小于等于总的台阶数,那么就先把当前循环的值压入到Stack中,
    * 当前Stack中所有数据值的和加上当选循环的值
    * 递归调用getWalkWays方法
    * 然后,将stack的pop值去掉并修改Stack中当前所有元素的和
    */
   if (current + currentIndex <= sum) {
    stack.push(currentIndex);
    current += currentIndex;
    getWalkWays(min, max, current, expect, sum);
    current -= stack.pop();
   }
  }
 }

 /**
  * 得到输出的前缀。
  * 如: 
  *   第50中走法
  * @return  
  */
 private String getCountInformation() {
  return new StringBuilder().append("第").append(++currentCount).append(
    "中走法:").toString();
 }

 /**
  * 打印当前Stack中的元素
  * 如:
  *   第50中走法:4 4 2
  * 
  * @param stack
  */
 private void print(Stack stack) {
  // 添加满足条件集合的元素个数范围
  StringBuilder sb = new StringBuilder();
  sb.append(getCountInformation());
  for (Object o : stack) {
   sb.append(o).append(" ");
  }
  System.out.println(sb.deleteCharAt(sb.length() - 1).toString());

 }

 /**
  * 输出符合条件的走楼梯条件信息。
  *
  */
 private void printResultTips(int min, int max, int sum, int expectTimes) {
   System.out.println(new StringBuilder().append("条件==》").append("台阶数为").append(sum)
     .append(", 每步走的最小台阶数为").append(min).append(", 每步走的最大台阶数为")
     .append(max).append(",最多走的次数是").append(expectTimes).toString());  
 }

 /**
  * 测试方法
  *
  */
 public void test() {
  int min = 2;
  int max = 4;
  int expectTimes = 4;
  int totalSteps = 10;
  
  printResultTips(min, max, totalSteps, expectTimes);
  getWalkWays(min, max, 0,expectTimes,totalSteps);
 }

 public static void main(String[] args) {
  //测试
  new Stair2().test();
 }
}

条件==》台阶数为10, 每步走的最小台阶数为2, 每步走的最大台阶数为4,最多走的次数是4
第1中走法:2 2 2 4
第2中走法:2 2 3 3
第3中走法:2 2 4 2
第4中走法:2 3 2 3
第5中走法:2 3 3 2
第6中走法:2 4 2 2
第7中走法:2 4 4
第8中走法:3 2 2 3
第9中走法:3 2 3 2
第10中走法:3 3 2 2
第11中走法:3 3 4
第12中走法:3 4 3
第13中走法:4 2 2 2
第14中走法:4 2 4
第15中走法:4 3 3
第16中走法:4 4 2
0
0
分享到:
评论
1 楼 LinApex 2013-05-11  
已经碰到过这个问题。

相关推荐

    极简楼梯台阶式计划总结PPT模板.pptx

    【极简楼梯台阶式计划总结PPT模板】是一种设计简洁、结构清晰的演示文稿工具,主要用于呈现工作或项目的总结、进度以及未来规划。在IT行业中,这种模板可以帮助专业人士高效地整理和展示他们的工作成果、挑战、解决...

    电信设备-可上下楼梯台阶的折叠式箱包、行李移动装置.zip

    4. **材料与性能**:列出使用的材料及其特性,如耐用性、轻便性,以及任何特殊的防护措施,以确保设备和人员的安全。 5. **适用场景**:列举出这款装置在电信行业中可能应用的具体场景,如住宅区、商业楼宇、基站等...

    递归函数大集成

    由于这是一个穷举法解决问题的例子,输出将列出所有符合条件的球员位置分配情况。 #### 3. 下楼梯问题 本问题要求计算从顶部到底部的不同走法数量,每次可以跳1、2或3个台阶。 **代码解析:** ```c #include #...

    人版数学七年级(上册)期末模拟试卷与答案共2套.doc

    20. **动态走法**:根据上楼梯的走法归纳出规律,找出有四个台阶时的走法数量。 解答题部分包括计算、解方程、错误分析、等差数列的规律、角度的计算以及几何体的性质等,这些都是初中数学的重要知识点。 通过这些...

    四年级数学上册 练习三(2) 苏教版 试题.doc

    5. **长方形面积**:第六题要求利用长方形的面积公式(长×宽=面积)来确定可能的长宽组合,题目提供了一个面积(96平方厘米)和限制条件(长和宽都是整厘米数),学生需要列出所有可能的长宽对。 6. **智力冲浪**...

    三年级奥数间隔问题PPT学习教案.pptx

    【奥数间隔问题】在小学三年级的奥数学习中,间隔问题是一种常见的...通过画图和列出方程式,可以帮助学生更好地理解和解答这类问题。在教学过程中,教师应引导学生分析问题的本质,培养他们的逻辑思维和抽象思考能力。

    北京市装修定额说明和计算规则.doc

    2. 定额项目中龙骨和面层分开列出,使用时应根据设计选择相应子目。 3. 面层装饰中,预制板的抹灰、粘贴面层已包括勾缝,不再另计。 4. 吊顶的其他项目,如金属格栅吸声板,按组装形式分项,可调整吸声体支架间距。 ...

    数学广角植树问题PPT课件.pptx

    6. **楼梯问题**:小明从1楼到3楼走了36级台阶,可以推断每层楼有18级台阶,那么从1楼到6楼需要走90级台阶。 7. **军事队列问题**:15个军人站成一列,每两人间距离1米,队伍总长是14米(不包括起始位置,所以是15 ...

    12级实训答疑汇编[归类].pdf

    6. 材料和做法未列出:对于护窗栏杆、楼梯踏步防滑条和美术字等,若未明确说明,通常意味着不考虑在内。 7. 轻质砖隔墙:若无合适子目,可以考虑用其他材料替代,如全塑钢板。 8. 楼梯踏步侧面做法:如果未标注,...

    XXXX广东建筑装饰工程定额计价规则.pptx

    在【楼地面工程】部分,定额计价规则详细列出了各种工程项目的计算规则。例如,地面垫层的计算方式是按照室内主墙面净空面积乘以设计厚度,以立方米计算,需扣除特定构筑物和设备的基础体积。找平层的工程量则根据主...

    重庆实验外国语学校2020小升初数学.docx

    从1楼到3楼走了2层楼梯,每层36级,所以从1楼到5楼走4层,需要4×36=144级台阶。 - 题目6:最大公约数和最小公倍数的关系是它们的乘积等于两个数的乘积。所以24和60的最大公约数和最小公倍数之和为24×60/(24,60)=...

    建筑施工组织2021-商铺单元验收交接表.doc

    3. 楼梯台阶及扶手:检查台阶的高度、深度是否一致,防滑性能如何,扶手安装牢固,无晃动,高度适宜,符合安全规范。 4. 墙面:检查墙面的平整度、色泽一致性,无空鼓、开裂、脱落现象,涂料或壁纸质量合格。 5. ...

    CleanSpecforionia73400TWD成品油轮技术规格书.docx

    主尺寸与特性**:具体列出油轮的长度、宽度、吃水深度等主要物理尺寸数据及其它技术参数。 ### 四、载重量与容量 - **004. 载重量与容量**:详细说明油轮的最大载重量(73,000DWT),以及各种舱室如货舱、燃料舱等...

    板块楼、地面分项工程质量检验评定表.doc

    4. **踏步、台阶**:检查楼梯的踏步和台阶是否水平,边缘处理是否安全,防止滑倒。 5. **镶 边**:查看镶边材料的固定情况,边缘是否平直,无松动。 允许偏差项目列出了不同材质板块的各项尺寸允许误差,如表面平整...

    苏版四年级数学上册易错题库完整.doc

    9. **几何问题**:题目18中通过树木的数量和时间计算汽车的速度,以及题目24中通过楼梯台阶数量求解楼层高度。 10. **应用问题**:题目14中通过已知的骡子运货量推算增加骡子后的总运货量。 11. **整数除法的余数...

    工业区清洁工工作规程.docx

    规程详细列出了清洁工的具体工作步骤。例如,垃圾周转过程中,清洁工需要收集楼层垃圾并将垃圾桶清洗干净,再套上新的垃圾袋,同时清理垃圾桶周围地面和墙面。对于小区道路、广场、地上、停车场的清扫,清洁工需使用...

    潘口和小漩水电站保洁服务方案.docx

    在方案中还包含了项目的成本预算,详细列出了各项服务的预计费用,以便合理分配资源,确保保洁服务的可持续性。 综上所述,该保洁服务方案全面而细致,旨在提供专业、高效的清洁服务,确保潘口和小漩水电站的工作...

    商铺单元验收交接表.doc

    这份表格详尽列出了商铺的各项设施、设备及其状况,便于验收人员进行逐项检查,确保无遗漏或损坏。 首先,验收内容包括基础结构部分,如地台、天花、吊顶等。地台的平整度和材料质量直接影响到商铺的使用和装修效果...

    建筑施工图基础教程实用教案.pptx

    1. 图纸目录:列出所有构成工程的图纸,包括每张图的名称、编号和顺序,方便查找。 2. 设计说明书:概述整个工程的概况和总体要求,小型工程的设计说明书一般包含在建筑施工图中。 3. 建筑施工图:详细展示建筑的...

    XXXX《建筑识图与构造》土建.pptx

    课程的教学大纲详细列出了各个学习模块,包括: 1. 制图基本知识:这部分介绍了制图工具的使用方法,如丁字尺、三角板、图板、圆规等,还涉及到图纸的规格、图线绘制、尺寸标注等内容,以及几何作图技巧。 2. 投影...

Global site tag (gtag.js) - Google Analytics