三个商人和三个随从的Java实现与分析
Java程序如下：
import java.util.*;
public class Test4{
/**内部类，用来把保存过河过程中的路线和状态.
* 五个属性:
* to为ture表示去对岸，否则表示从对岸返回。同时true也表示船在本岸，false表示船在对岸.
* busiMansInBoat为在船里的商人数.
* servsInBoat为船里的仆人数.
* residualBusiMans为岸上的商人数，to为true时，表示是本岸.
* residualServants为岸上的仆人数，to为true时，表示是本岸.
*/
static class Path{
boolean to;
int busiMansInBoat;
int servsInBoat;
int residualBusiMans;
int residualServants;
Path(boolean to,int bmib,int sib,int rb,int rs){
this.to=to;
busiMansInBoat=bmib;
servsInBoat=sib;
residualBusiMans=rb;
residualServants=rs;
}
/*比较两个状态是不是相同.
*/
public boolean equals(Path p){
if(to==p.to){
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&residualBusiMans==p.residualBusiMans&&residualServants==p.residualServants;
}else if(to){
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&residualBusiMans==3-p.residualBusiMans-p.busiMansInBoat&&residualServants==3-p.residualServants-p.servsInBoat;
}else{
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&3-residualBusiMans-busiMansInBoat==p.residualBusiMans&&3-residualServants-servsInBoat==p.residualServants;
}
}
public String toString(){
if(to){
return "本岸(商人"+residualBusiMans+"个,仆人"+residualServants+"个)—–>"
+"[船上:"+busiMansInBoat+"个商人,"+servsInBoat+"个仆人]—–>"
+"对岸(商人"+(3-residualBusiMans-busiMansInBoat)+"个,仆人"+(3-residualServants-servsInBoat)+"个)";
}else{
return "本岸(商人"+(3-residualBusiMans-busiMansInBoat)+"个,仆人"+(3-residualServants-servsInBoat)+"个)<—–"
+"[船上:"+busiMansInBoat+"个商人,"+servsInBoat+"个仆人]<—–"
+"对岸(商人"+residualBusiMans+"个,仆人"+residualServants+"个)";
}
}
}
//保存路线的List
public static List<Path> pathList=new ArrayList<Path>();
/**过河方法.
* @param businessmans 商人数.
* @param servants 仆人数.
* @param schemes 方案集合.
* @param to 去还是返回，同时也表示是否在对岸.
*
*/
public static void passRiver(int businessmans,int servants,int[][] schemes,boolean to){
if(!to&&businessmans==3&&servants==3){
System.out.println("结果");
for(Path p : pathList){
System.out.println(p);
}
return;
}
int schemesStart=0; //从方案集中的那一种方案开始选择.
if(to){
schemesStart=2; //如果在本岸，则从第3种方案开始选择.
}
for(int i=schemesStart;i<schemes.length;i++){
int residualBusiMans=businessmans-schemes[i][0]; //按照方案岸上所剩商人数.
int residualServants=servants-schemes[i][1]; //按照方案岸上所剩仆人数.
if(residualBusiMans<0||residualServants<0){ //如果商人数或仆人数小于0，重新选择方案.
continue;
}
if(residualBusiMans!=0&&residualBusiMans<residualServants){ //如果仆人数大于商人数，重新选择方案.
continue;
}
if(3-residualBusiMans!=0&&3-residualBusiMans<3-residualServants){ //如果对岸的仆人数大于商人数,重新选择方案.
continue;
}
//按本方案，生成路线.
Path p=new Path(to,schemes[i][0],schemes[i][1],residualBusiMans,residualServants);
if(!isRepeat(p)){ //如果没有重复.
pathList.add(p);
passRiver(3-residualBusiMans,3-residualServants,schemes,!to); //从对岸返回.
pathList.remove(pathList.size()-1);
}
}
}
/**看看当前的路线是不是和以前的重复了.
*/
public static boolean isRepeat(Path p){
boolean repeat=false;
for(Path temp : pathList){
if(temp.equals(p)){
repeat=true;
break;
}
}
return repeat;
}
public static void main(String[] args)throws Exception{
//过河方案,每一种方案为一个一组数组,比如{1,0}表示船上要坐1个商人和0个仆人。方案可以用一个方法来生成:
int[][] sckemes={{1,0},{0,1},{1,1},{2,0},{0,2}};
passRiver(3,3,sckemes,true);
}
}
输出结果为：