/**
* @(#)StepProblem.java
*
*·某人上楼梯,他一步可以迈一个台阶,两个台阶或三个台阶,共有n个台阶,编程输出他所有可能上法的种类.
* @author 许刚
* @version 1.00 2010/5/6
*/
import java.util.*;
public class StepProblem {
/**
* Creates a new instance of <code>StepProblem</code>.
*/
private int totalStep=4;
public int count=0;
public StepProblem() {
}
//递归方法计算
public void StepRecursion(int n){
if(n==0){
count++;
return ;
}
if(n>=1)
StepRecursion(n-1);
if(n>=2)
StepRecursion(n-2);
if(n>=3)
StepRecursion(n-3);
}
//使用树型结构
private class MTreeNode{
private int step;
private
int countStep;
private Vector<MTreeNode> child;
private MTreeNode parent;
public MTreeNode(int step,int countStep){
this.step=step;
this.countStep=countStep;
this.parent=null;
this.child=new Vector<MTreeNode>();
}
public MTreeNode(int step,MTreeNode parent){
this.step=step;
this.countStep=step+parent.getCountStep();
this.parent=parent;
this.child=new Vector<MTreeNode>();
}
public int getCountStep(){
return this.countStep;
}
public MTreeNode addChild(int step){
MTreeNode node=new MTreeNode(step,this);
child.add(node);
return node;
}
}
//线性方法计算
public void StepLinearity(int n){
Stack<MTreeNode> s=new Stack<MTreeNode>();
Vector<MTreeNode> result=new Vector<MTreeNode>();
MTreeNode root=new MTreeNode(0,0);
s.push(root);
do{
MTreeNode node=s.pop();
if(node.getCountStep()+1<n){
s.push(node.addChild(1));
}
else if(node.getCountStep()+1==n){
result.add(node.addChild(1));
}
if(node.getCountStep()+2<n){
s.push(node.addChild(2));
}
else if(node.getCountStep()+2==n){
result.add(node.addChild(2));
}
if(node.getCountStep()+3<n){
s.push(node.addChild(3));
}
else if(node.getCountStep()+3==n){
result.add(node.addChild(3));
}
}while(!s.isEmpty());
System.out.print("线性计算结果"+result.size());
}
public void OutputResult(){
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
StepProblem s=new StepProblem();
s.StepRecursion(10);//测试递归方法
System.out.println("递归结果"+s.count);
s.StepLinearity(10);//测试线性结果
}
}
2010-04-13 15:43
