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

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

第一个程序：给定台阶数，每次走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

评论

1 楼 LinApex 2013-05-11  

已经碰到过这个问题。