计算java中的递归步骤

发布时间：2020-12-15 08:37:25 所属栏目：Java 来源：网络整理

导读：我想计算递归步数,并在达到某个限制时停止递归. 实际上我正在处理河内塔问题,我想限制为解决问题而执行的幻灯片数量.这是我的解决方案： class HanoiNK{ public static void main(String args[]){ int n = 4; int k = 5; try{ slide(k,n,'A','B','C'); }catc

我想计算递归步数,并在达到某个限制时停止递归.

实际上我正在处理河内塔问题,我想限制为解决问题而执行的幻灯片数量.这是我的解决方案：

class HanoiNK{

    public static void main(String args[]){

            int n = 4;
            int k = 5;

            try{
                slide(k,n,'A','B','C');
            }catch(Exception e){
                System.out.println(e);
            }
    }

    public static void slide(int counter,int height,char source,char buffer,char destination) throws Exception{      
        if(counter > 0){
            if(height == 1){                                
                System.out.println("move "+ height +" from " +
                                                source + " to " + destination);
            }else{  
                counter--;
                slide(counter,height - 1,source,destination,buffer);    
                System.out.println("move "+ hoehe +" from " +
                                                source + " to " + destination);
                counter--;
                slide(counter,buffer,destination);    
            }
        }else{
            throw new Exception("stop here");
        }
    }
}

这是现场示例：http://ideone.com/xeN4x

我的问题是我得到了

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
move 2 from C to B
java.lang.Exception: stop

作为输出.但是应该执行5次而不是6次幻灯片.有任何想法吗？

解决方法

由于您要计算移动的数量而不是递归深度,因此您需要存储在每个步骤中进行的移动次数.像这样的东西：

public static int slide(int counter,int hoehe,char quelle,char ablage,char ziel)
throws Exception{         
    if (hoehe == 1) {          
        System.out.println("move "+ hoehe +" from " +                                             
                quelle + " to " + ziel);   
        if (--counter == 0) throw new Exception("hier stoppen"); 
    } else {     
        counter = slide(counter,hoehe - 1,quelle,ziel,ablage);     
        System.out.println("move "+ hoehe +" from " +          
                quelle + " to " + ziel);             
        if (--counter == 0) throw new Exception("hier stoppen"); 
        counter = slide(counter,ablage,ziel);       
    }     
    return counter;
}

然后,您获得预期的结果：

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to A
java.lang.Exception: hier stoppen

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!