2013年360笔试题目 - 范文无忧网

[2015KPMG毕马威笔试经验]先说一下我背景吧，我是上海复旦大学旁边的某个知名财经大学的学生，专业是工商管理，成绩一般般，在工商管理班是属于倒数的，不过放到年级上就是前30%的水平，所以填成绩排名时从来只...+阅读

编程题、传教士人数M，野人C，MC，开始都在岸左边，

①船只能载两人，传教士和野人都会划船，当然必须有人划船

②两岸边保证野人人数不能大于传教士人数

把所有人都送过河，设计一方案，要求编程实现。

思路：

深度搜索。

状态：左岸和右岸的人数+船的位置。

每一个状态下，会有5种状态可以转移，

即：

1，运送2个传教士到对岸;

2，运送2个野人到对岸;

3，运送1个传教士到对岸;

4，运送1个野人到对岸;

5，运送1个传教士和一个野人到对岸。

从初始状态开始搜，搜索这五种情况，

进入下一状态，判断该状态是否满足条件，

即两岸野人的个数是否比该岸的传教士多，

如果满足条件，则继续搜索该状态下的五种情况。

深度搜索下去，直到找到最后的解。

注意：

1，如果搜索的状态在之前已经出现过了，就不深入下去了，

否则会出现死循环，比如运两个野人过去，再运回来，状态复原了，

如果一直这么搜下去，就没玩没了了。

2，状态包括船的信息，如果两边的人数都是一样，但是船的位置不一样，

那么这是两种状态。

3，要搜索的目标状态是人都在对岸且船在对岸。

PS：

当M=C3时，没有解。

当MC时，有解。

[cpp] view plaincopyprint?

#include

using namespace std;

bool flag = true; true:表示在右岸

vectorvisit; 记录已经访问过的状态

bool dfs( int M, int C, int m, int c){

if( M0||C0||m0||c0) 非法

return false;

if( (MCM) ||(mcm)) 野人会吃牧师

return false;

if( flagM==0C==0 ||(!flagm==0c==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

using namespace std;

bool flag = true; true:表示在右岸

vectorvisit; 记录已经访问过的状态

bool dfs( int M, int C, int m, int c){

if( M0||C0||m0||c0) 非法

return false;

if( (MCM) ||(mcm)) 野人会吃牧师

return false;

if( flagM==0C==0 ||(!flagm==0c==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;

}