360筆試題目

 　　編程題、傳教士人數M，野人C，M≥C，開始都在岸左邊，

　�、俅�只能載兩人，傳教士和野人都會劃船，當然必須有人劃船

　�、趦砂哆叡ＷC野人人數不能大于傳教士人數

　　把所有人都送過河，設計一方案，要求編程實現，

360筆試題目

。

　　思路：

　　深度搜索。

　　狀態：左岸和右岸的人數+船的位置。

　　每一個狀態下，會有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 visit; //記錄已經訪問過的狀態

　　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;

　　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 visit; //記錄已經訪問過的狀態

　　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;

　　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筆試題目】相關文章：

360筆試題目06-27

筆試題目05-29

美的筆試的題目06-18

職場經典筆試題目07-21

UBI 筆試題目05-19

APL筆試題目10-05

雅虎筆試題目09-25

Adobe筆試題目06-23

用友筆試題目08-15

SUN筆試題目09-05