某人1次可以走1个，2个或3个台阶，写程序计算走N个台阶的各种走法。

在java eye论坛上看到的，
大致意思是：
某人1次可以走1个，2个或3个台阶，写程序计算走N个台阶的各种走法。
试了一下，很简单。

package interest.chess;

import java.util.LinkedList;
import java.util.List;


/**
 * 某人1次可以走1个，2个或3个台阶
 * 写程序计算走N个台阶的各种走法。
 * 
 * @time: Nov 4, 2010 5:23:18 PM
 * @author [e-mail]
 */
public class Test {
	public static void main(String[] args) {
		int n = 5;
		List<String> stepHis = new LinkedList<String>();
		System.out.println("总共方法有" + go(n, stepHis) + "种。");
	}
	
	/**
	 * 计算要走的步数，并保存在stepHis种
	 * @param steps 还有多少步要走
	 * @param number 走法的数目
	 * @param stepHis 保存该种走法的列表
	 * @return 总共走法数
	 */
	public static int go(int steps, List<String> stepHis){
		int thisNumber = 0;
		//剩余步数为0，那么可以把之前记录的his都打出来了
		if(steps == 0){
			if(stepHis.size()>0){
				thisNumber++;
			}
			printHis(stepHis);
		}else{
			//如果步数超过1,2或3，那么减掉该步骤，继续算剩余步数的走法
			for(int i = 1; i <=3; i++ ){
				if((steps - i) >= 0){
					List<String> thisStepHis = (List<String>)((LinkedList<String>)stepHis).clone();
					thisStepHis.add(i + ",");
					thisNumber += go(steps-i, thisStepHis);
				}
			}
		}
		
		return thisNumber;
	}
	/**
	 * 打印步数
	 * @param stepHis
	 */
	public static void printHis(List<String> stepHis){
		for(String str : stepHis){
			System.out.print(str);
		}
		System.out.println();
	}
}

评论

4 楼 suntao19830709 2010-12-10  

dengzhangtao 写道

suntao19830709 写道

dengzhangtao 写道

能给解释一下吗，  为什么

你得先告诉别人解释哪里？不会是全部要解释吧？

怎么理解，你写的递归。。？？
我这里不是很理解。

如果每次都可以走i个台阶(i为1或2或3)
步骤一：只要N大于i，N个台阶的走法总是可以转化成先走i个台阶，再走(N-i)个台阶。
步骤二：然后用N代替N-i，重复步骤一。

另外，上面注释有的比较老了，忘了删。
例如 @param number 走法的数目

3 楼 dengzhangtao 2010-12-02  

suntao19830709 写道

dengzhangtao 写道

能给解释一下吗，  为什么

你得先告诉别人解释哪里？不会是全部要解释吧？

怎么理解，你写的递归。。？？
我这里不是很理解。

2 楼 suntao19830709 2010-12-02  

dengzhangtao 写道

能给解释一下吗，  为什么

你得先告诉别人解释哪里？不会是全部要解释吧？

1 楼 dengzhangtao 2010-12-01  

能给解释一下吗，  为什么