程式設計題、傳教士人數M,野人C,M≥C,開始都在岸左邊,
①船隻能載兩人,傳教士和野人都會划船,當然必須有人划船
②兩岸邊保證野人人數不能大於傳教士人數
把所有人都送過河,設計一方案,要求程式設計實現。
思路:
深度搜索。
狀態:左岸和右岸的人數+船的`位置。
每一個狀態下,會有5種狀態可以轉移,
即:
1,運送2個傳教士到對岸;
2,運送2個野人到對岸;
3,運送1個傳教士到對岸;
4,運送1個野人到對岸;
5,運送1個傳教士和一個野人到對岸。
從初始狀態開始搜,搜尋這五種情況,
進入下一狀態,判斷該狀態是否滿足條件,
即兩岸野人的個數是否比該岸的傳教士多,
如果滿足條件,則繼續搜尋該狀態下的五種情況。
深度搜索下去,直到找到最後的解。
注意:
1,如果搜尋的狀態在之前已經出現過了,就不深入下去了,
否則會出現無窮迴圈,比如運兩個野人過去,再運回來,狀態復原了,
如果一直這麼搜下去,就沒玩沒了了。
2,狀態包括船的資訊,如果兩邊的人數都是一樣,但是船的位置不一樣,
那麼這是兩種狀態。
3,要搜尋的目標狀態是人都在對岸且船在對岸。
PS:
當M=C>3時,沒有解。
當M>C時,有解。
[cpp] view plaincopyprint?
#include
#include
#include
#include
using namespace std;
bool flag = true; //true:表示在右岸
vector
bool dfs( int M, int C, int m, int c){
if( M<0||C<0||m<0||c<0) //非法
return false;
if( (M&&C>M) ||(m&&c>m)) //野人會吃牧師
return false;
if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部運輸過去
return true;
//檢查該節點是否出現過
char s[30];
if( !flag )
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
else
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
string str(s);
for( int i=0; i
if( visit[i]==str) //該狀態已經搜尋過了
return false;
_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0n");
printf("%sn",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2n");
printf("%sn",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1n");
printf("%sn",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0n");
printf("%sn",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1n");
printf("%sn",s);
return true;
}
flag = !flag;
_back();
return false;
}
int main(){
char s[30];
int M=6,C=6,m=0,c=0;
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
printf("%sn",s);
if(!dfs(M,C,0,0))
cout << "Can not find the solution."<
return 0;
}
#include
#include
#include
#include
using namespace std;
bool flag = true; //true:表示在右岸
vector
bool dfs( int M, int C, int m, int c){
if( M<0||C<0||m<0||c<0) //非法
return false;
if( (M&&C>M) ||(m&&c>m)) //野人會吃牧師
return false;
if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部運輸過去
return true;
//檢查該節點是否出現過
char s[30];
if( !flag )
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
else
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
string str(s);
for( int i=0; i
if( visit[i]==str) //該狀態已經搜尋過了
return false;
_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0n");
printf("%sn",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2n");
printf("%sn",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1n");
printf("%sn",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0n");
printf("%sn",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1n");
printf("%sn",s);
return true;
}
flag = !flag;
_back();
return false;
}
int main(){
char s[30];
int M=6,C=6,m=0,c=0;
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
printf("%sn",s);
if(!dfs(M,C,0,0))
cout << "Can not find the solution."<
return 0;
}