題目：有3只狼和3只羊要過河，只有一條船，一次最多只能坐兩只動物并且每次必須有動物開船，如果某一邊的狼的個數(shù)大于羊的個數(shù)，羊?qū)⒈怀缘?，編程給出解。
參考答案：
package ch1;
public class LangAndYang {
public static void main(String[] args) {
int state[] = {3,3};
// 第1、2個元素表示左岸的狼和羊的數(shù)量
new LangAndYang().next(state,null);
}
public void next(int state[],StringBuffer str){
int[] newState;
if(str==null){ //表示第一步
// 一只狼一只羊
newState = move(state,"-1-1");
next(newState,new StringBuffer("-1-1"));
// 兩只狼過河
newState = move(state,"-2-0");
next(newState,new StringBuffer("-2-0"));
return;
}
if(state[0]==0 && state[1]==0){ // 全部轉(zhuǎn)移到右岸了
printResult(str);
return;
}
if(str!=null && hasExist(str)){ // 看是否為死循環(huán)
return;
}
// 考慮向右轉(zhuǎn)移
if(str.charAt(0)=='+'){
// 兩只狼
if(state[0]>=2 && !str.substring(0,4).equals("+2+0")){
newState = move(state,"-2-0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-2-0"));
}
}
// 一只狼
if(state[0]>=1 && !str.substring(0,4).equals("+1+0")){
newState = move(state,"-1-0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-1-0"));
}
}
// 一只羊
if(state[1]>=1 && !str.substring(0,4).equals("+0+1")){
newState = move(state,"-0-1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-0-1"));
}
}
// 一只狼一只羊
if(state[0]>=1 && state[1]>=1 && !str.substring(0,4).equals("+1+1")){
newState = move(state,"-1-1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-1-1"));
}
}
// 兩只羊
if(state[1]>=2 && !str.substring(0,4).equals("+0+2")){
newState = move(state,"-0-2");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-0-2"));
}
}
}else{ // 考慮向左轉(zhuǎn)移
// 兩只狼
if(state[0]<2 && !str.substring(0,4).equals("-2-0")){
newState = move(state,"+2+0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+2+0"));
}
}
// 一只狼
if(state[0]<3 && !str.substring(0,4).equals("-1-0")){
newState = move(state,"+1+0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+1+0"));
}
}
// 一只羊
if(state[1]<3 && !str.substring(0,4).equals("-0-1")){
newState = move(state,"+0+1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+0+1"));
}
}
// 一只狼一只羊
if(state[0]<3 && state[1]<3 && !str.substring(0,4).equals("-1-1")){
newState = move(state,"+1+1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+1+1"));
}
}
// 兩只羊
if(state[1]<2 && !str.substring(0,4).equals("-0-2")){
newState = move(state,"+0+2");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+0+2"));
}
}
}
}
/*
* 第一個參數(shù)表示狀態(tài)，第二個參數(shù)表示走法，向右用-，向左用+
* 返回值表示新的狀態(tài)
*/
public int[] move(int state[],String info){
int lang = 0;
try{
lang = Integer.parseInt(info.substring(0,2));
}catch(Exception e){
lang = Integer.parseInt(info.substring(1,2));
}
int yang = 0;
try{
yang= Integer.parseInt(info.substring(2));
}catch(Exception e){
yang = Integer.parseInt(info.substring(3));
}
int[] result = new int[state.length];
result[0] = state[0]+lang;
result[1] = state[1]+yang;
return result;
}
/*
* 驗(yàn)證狀態(tài)是否合適，狼的個數(shù)不能大于羊
*/
public boolean check(int state[]){
if(state[0]>state[1] && state[1]>0){ //左邊有羊，并且狼比羊多
return false;
}else if(state[0]<state[1] && state[1]<3){ // 右邊有羊，并且狼比羊多
return false;
}else
return true;
}
/*
* 防止死循環(huán)，例如 先過去一只狼一只羊，然后回來一只羊，然后再過去一只狼，然后回來兩只狼，就回到初始狀態(tài)了
*/
public boolean hasExist(StringBuffer str){
int langSum=0;
int yangSum=0;
for(int i=0;i<str.length()/4;i++){
if(str.charAt(i*4)=='-'){
langSum += str.charAt(i*4+1)-'0';
yangSum += str.charAt(i*4+3)-'0';
}else{
langSum -= str.charAt(i*4+1)-'0';
yangSum -= str.charAt(i*4+3)-'0';
}
if(langSum==0 && yangSum==0 && i%2==1)
return true;
}
return false;
}
public void printResult(StringBuffer str){
System.out.println("-----方案------");
for(int i=str.length()/4-1;i>=0;i--){
if(str.charAt(i*4)=='-'){
System.out.println("運(yùn)過去"+str.charAt(i*4+1)+"只狼，"+str.charAt(i*4+3)+"只羊");
}else{
System.out.println("---------------運(yùn)回來"+str.charAt(i*4+1)+"只狼，"+str.charAt(i*4+3)+"只羊");
}
}
System.out.println();
}
}
希望大家真正把代碼理解了，而不是把代碼保存下來。
