3790

积分

好友

主题
发表于 2012-10-17 00:58:39 | 查看: 547| 回复: 4
纯粹用来活动脑细胞的一个题目。

编程题、传教士人数M,野人C,M≥C,开始都在岸左边,
①船只能载两人,传教士和野人都会划船,当然必须有人划船
②两岸边保证野人人数不能大于传教士人数   
把所有人都送过河,设计一方案,要求编程实现。


思路:

深度搜索。

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

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

即:

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

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

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

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

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


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

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

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

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

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


注意:

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

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

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

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

那么这是两种状态。

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


PS:

当M=C>3时,没有解。

当M>C时,有解。


[code=cpp]#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;

bool flag = true; //true:表示在右岸
vector<string> 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<visit.size(); i++)
    if( visit==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."<<endl;
  return 0;
}
[/code]

这个应该属于人工智能领域的。
顿时觉得以后的压力很大啊!


发表于 2012-10-19 15:19:25
这是143吗??

回复 显示全部楼层 道具 举报

发表于 2012-10-19 17:35:57
yc574 发表于 2012-10-19 16:19
这是143吗??

不是

回复 显示全部楼层 道具 举报

发表于 2012-10-19 20:54:42
admin 发表于 2012-10-19 18:35
不是

貌似不是JAVA 是什么语言?

回复 显示全部楼层 道具 举报

发表于 2012-10-19 21:19:10
yc574 发表于 2012-10-19 21:54
貌似不是JAVA 是什么语言?

C++

回复 显示全部楼层 道具 举报

手机版|Copyright|CSUW

GMT-8, 2019-1-17 04:50 , Processed in 0.034294 second(s), 16 queries .

Powered by CSUW

© 2001-2012 CSUW.ORG

返回顶部