360笔试题目

时间:2018-12-31 12:00:00 资料大全 我要投稿

360笔试题目

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

360笔试题目

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

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

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

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笔试题目】相关文章:

1.360笔试题目

2.360产品助理笔试经验

3.360产品助理笔试分享

4.360产品类笔试经验

5.奇虎360校招笔试题

6.笔试程序题目

7.笔试题目

8.上海奇虎360(产品类)笔试经验