问题描述
问题：编写一个用来解决“野蛮人和传教士”问题的递归程序。三个传教士和三个野蛮人渡河，只有一条可以同时搭载2人的小船。如果在河任一边的岸上野蛮人数比传教士人数多，野蛮人就会把传教士吃掉。该如何渡河？我用的方法是：go(intx1,inty1,intx2,inty2)back(intx1,inty1,intx2,inty2){{if(x1==0&&y1==0&&x2==3&&y2==3)back(x1-2,y1,x2+2,y2);go(x1+1,y1,x2-1,y2);back(x1,y1-2,x2,y2+2);go(x1,y1+1,x2,y2-1);back(x1-1,y1-1,x2+1,y2+1);go(x1+1,y1+1,x2-1,y2-1);}}下面是我的代码，请高手帮我优化一下，为了防止它无究递归下去，我限制了他求解的个数为1（加了一个flag）很容易陷入"一个野人和一个传教士过河，一个传教士和一个野人返回，一个野人和一个传教士过河，一个野人和一个传教士过河"这样死递归，最后StackOverException,问怎么消除这种情况呢？importjava.util.Iterator;importjava.util.LinkedList;importjava.util.Scanner;classTest{staticbooleanflag=false;staticLinkedList<String>list=newLinkedList<String>();staticvoidGo(intx1,inty1,intx2,inty2){if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)return;if((x1>y1&&y1!=0)||(x2>y2&&y2!=0))return;if(flag)return;/*去掉这句就有问题了*/list.add("两个野人过河");Return(x1-2,y1,x2+2,y2);list.removeLast();list.add("两个传教士过河");Return(x1,y1-2,x2,y2+2);list.removeLast();list.add("一个野人和一个传教士过河");Return(x1-1,y1-1,x2+1,y2+1);list.removeLast();}staticvoidReturn(intx1,inty1,intx2,inty2){if(x1<0||y1<0||x2<0||y2<0||x1>3||y1>3||x2>3||y2>3)return;if((x1>y1&&y1!=0)||(x2>y2&&y2!=0))return;if(x1==0&&y1==0&&x2==3&&y2==3){flag=true;for(Iterator<String>i=list.iterator();i.hasNext();){System.out.println(i.next());}/*try{System.in.read();System.in.read();}catch(IOExceptione){//TODOAuto-generatedcatchblocke.printStackTrace();}*/return;}list.add("一个野人返回");Go(x1+1,y1,x2-1,y2);list.removeLast();list.add("一个传教士返回");Go(x1,y1+1,x2,y2-1);list.removeLast();list.add("一个传教士和一个野人返回");Go(x1+1,y1+1,x2-1,y2-1);list.removeLast();}publicstaticvoidmain(String[]args){Go(3,3,0,0);}}