ddddddddddddddd

哥，你的好像没有说出有几种登台阶方法。

[ 本帖最后由 Celavia 于 2010-4-16 09:43 编辑 ]

/**
 * @(#)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);//测试线性结果
         
      
    }
}