- 360筆試題目 推薦度：
- 相關(guān)推薦
360筆試題目
編程題、傳教士人數(shù)M，野人C，M≥C，開(kāi)始都在岸左邊，
�、俅荒茌d兩人，傳教士和野人都會(huì)劃船，當(dāng)然必須有人劃船
�、趦砂哆叡ＷC野人人數(shù)不能大于傳教士人數(shù)
把所有人都送過(guò)河，設(shè)計(jì)一方案，要求編程實(shí)現(xiàn)，
360筆試題目
。思路：
深度搜索。
狀態(tài)：左岸和右岸的人數(shù)+船的位置。
每一個(gè)狀態(tài)下，會(huì)有5種狀態(tài)可以轉(zhuǎn)移，
即：
1，運(yùn)送2個(gè)傳教士到對(duì)岸;
2，運(yùn)送2個(gè)野人到對(duì)岸;
3，運(yùn)送1個(gè)傳教士到對(duì)岸;
4，運(yùn)送1個(gè)野人到對(duì)岸;
5，運(yùn)送1個(gè)傳教士和一個(gè)野人到對(duì)岸。
從初始狀態(tài)開(kāi)始搜，搜索這五種情況，
進(jìn)入下一狀態(tài)，判斷該狀態(tài)是否滿足條件，
即兩岸野人的個(gè)數(shù)是否比該岸的傳教士多，
如果滿足條件，則繼續(xù)搜索該狀態(tài)下的五種情況。
深度搜索下去，直到找到最后的解。
注意：
1，如果搜索的狀態(tài)在之前已經(jīng)出現(xiàn)過(guò)了，就不深入下去了，
否則會(huì)出現(xiàn)死循環(huán)，比如運(yùn)兩個(gè)野人過(guò)去，再運(yùn)回來(lái)，狀態(tài)復(fù)原了，
如果一直這么搜下去，就沒(méi)玩沒(méi)了了。
2，狀態(tài)包括船的信息，如果兩邊的人數(shù)都是一樣，但是船的位置不一樣，
那么這是兩種狀態(tài)。
3，要搜索的目標(biāo)狀態(tài)是人都在對(duì)岸且船在對(duì)岸。
PS：
當(dāng)M=C>3時(shí)，沒(méi)有解。
當(dāng)M>C時(shí)，有解。
[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)) //野人會(huì)吃牧師
return false;
if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部運(yùn)輸過(guò)去
return true;
//檢查該節(jié)點(diǎn)是否出現(xiàn)過(guò)
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) //該狀態(tài)已經(jīng)搜索過(guò)了
return false;
visit.push_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1\n");
printf("%s\n",s);
return true;
}
flag = !flag;
visit.pop_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("%s\n",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)) //野人會(huì)吃牧師
return false;
if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部運(yùn)輸過(guò)去
return true;
//檢查該節(jié)點(diǎn)是否出現(xiàn)過(guò)
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) //該狀態(tài)已經(jīng)搜索過(guò)了
return false;
visit.push_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1\n");
printf("%s\n",s);
return true;
}
flag = !flag;
visit.pop_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("%s\n",s);
if(!dfs(M,C,0,0))
cout << "Can not find the solution."<
return 0;
}
【360筆試題目】相關(guān)文章：
360筆試題目06-27
筆試題目05-29
美的筆試的題目06-18
UBI 筆試題目05-19
APL筆試題目10-05
雅虎筆試題目09-25
Adobe筆試題目06-23
用友筆試題目08-15
SUN筆試題目09-05