山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

求解一道题

楼主0000000009（）2005-12-01 20:49:24 在 C/C++ / C++ 语言提问

4名成员伯纳、艾吉、埃达姆、劳瑞赶往演出现场，他们途中要经过一座小桥。当他们赶到桥头时，天已经黑了，周围没有灯。他们只有一只手电筒。现在规定：一次最多只许两人一起过桥，过桥人手里必须有手电筒，两个人过桥后必须有一个人拿手电筒回来，手电筒不能用扔的方式传递。4个人的步行速度都不同，若两人同行，则以较慢者的速度为准。伯纳需花1分钟过桥，艾吉过桥需花2分钟，埃达姆需花5分钟过桥，劳瑞需花10分钟过桥。请问：他们能在17分钟内过桥吗？

我的问题是如何用程序来实现?
谢谢问题点数：20、回复次数：10Top

1 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-01 20:51:08 得分 10

先找到数学的解法, 再写程序

如果直接用程序解的话, 一般这种题想到的只是穷举.Top

2 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-01 20:53:15 得分 0

正好17分钟可以过.Top

3 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-01 21:02:41 得分 0

用程序穷举的话.
假设4人初始状态在桥A端, 现在需要到B端
状态1: A(4), B(0) (A端4人, B端0人)
第一次, 需要选出2人到B端有C(4,2)选择

状态2: A(2), B(2)
第二次, 从B端选一人回到A端, 有C(2,1)选择

状态3: A(3), B(1)
第三次, 从A端选二人到B端, 有C(3,2)

状态4: A(1), B(3)
第四次, 从B端选一人回到A端, 有C(3,1)选择

状态5: A(2), B(2)
第五次, A端两个人到B端. C(2,2)

所以从状态1 -> 状态5
共有C(4,2)*C(2,1)*C(3,2)*C(3,1)*C(2,2) = 6*2*3*3*1 = 108(种)

也就是说, 只要在程序中列举出这108种可能情况, 然后取得最小值, 看是否能够在17分钟内完成任务.
Top

4 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2005-12-01 21:20:35 得分 0

A 1
B 2
C 5
D 10
//==============
　A　B　→　2
　 A　←　1　　　　　　
C　D　→　10　
B　←　2　　　　　
A　B　→　2

结果刚好17分钟Top

5 楼0000000009（）回复于 2005-12-01 21:21:26 得分 0

答案是:
设a用1分钟
b 2
c 5
d 10

ab过a回，cd过b回，ab过，正好17分，这是我用脑子才出来的，我想如果用程序来实现只能用穷举，这才是计算机的特点。除了穷举还有别的方法吗?
如果只能用穷举该怎么做? 递归?
能给段代码吗?
Top

6 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2005-12-01 21:23:42 得分 0

http://www.oursci.org/magazine/200204/020411-01.htmTop

7 楼jiajun870207（○o絕戀oヤ煙）回复于 2005-12-01 22:24:07 得分 0

晕哦~`
我今天晚上才做完穷举类型的
想不到在这个地方又看见一道~~~
不过说回来你这个怕是比我做的题难多了哦~~
你可以去~~~萌动在线去看看有没有这样类型的题啊~~
让他们参考参考
也许会有答案的啊~~
好了
不说了哈~~
我今天晚上还要查点资料 ~~
是关于最短路径算法的~`
书上面还没有说清楚~`
有的我还搞不懂``
谁知道的话
告诉我一下哈~``
谢谢咯~``Top

8 楼Kvci（看了不笑就没小JJ同时又比较长的昵称__——————————————————————————————）回复于 2005-12-01 22:52:47 得分 0

状态空间图解就是啦
Top

9 楼ShowLovE（天天）回复于 2005-12-02 00:30:30 得分 10

这题和CTSC99的补丁VS错误差不多, 可以用SSSP,DFS,BFS...
我用BFS写的一个:
/************************
主要算法:BFS
设初始所有的人在河的南岸, 过桥后为岸.
0000代表所有的人南岸, 1111 表示所有的人在北岸, 即已经过河
把每一个状态看一个二进制数, 用来计算其值判重
************************/
#include<stdio.h>
#include<string.h>
#include<limits.h>

#define N 4 //人的数目
#define M 2 << N
#define MAX 1000 //设最多来回1000趟
#define max( i, j ) ( (i) > (j) ) ? ( i ) : ( j )

typedef struct
{
int sum, pos;
//sum 记录每次过去两人并返回一人所需要的时间, pos记录队列中的点的父亲结点, 主要用来构造最优解
char a[N+1], b[N+1];
}Status; //a记录返回后的状态, b记录过去后的状态.

typedef struct
{
int max, pos;
}HashDS; //pos用来Hash郑重, 把每个一个

HashDS Hash[MAX];
Status q[MAX];
char start[N+1] = "0000", final[N+1] = "1111", temp[N+1], go[N+1];
//temp记录中间结果, go记录次过河后没人返回进的状态
int t[N] = { 1, 2, 5, 10 };
//记录每人过河的时间
int used[N], min;
int GetHashNum( char* );
int convert();
int main()
{

int center, now, i, j, k, T, di, pos;
memset( Hash, 0, 2 * MAX * sizeof( Hash[0] ) );
memset( used, 0, N * sizeof( used[0] ) );
Hash[GetHashNum(start)].pos = 1;
center = now = 0;
q[center].sum = 0;
q[center].pos = -1;
strcpy( q[center].a, start );
min = INT_MAX;
while( center <= now )
{
for( i = 0; i < N; i++ )
for( j = i + 1; j < N; j++ )
{
strcpy( temp, q[center].a );
convert( );
if( !used[i] && !used[j] ) //选择在两岸的两人过河
{
used[i] = used[j] = 1;
temp[i] = temp[j] = '1';
T = max( t[i], t[j] ); //T记录两人中较慢的人所需要的时间
}
else
continue; //没有找到两人, 则继续下一个状态的扩展
if( strcmp( temp, final ) == 0 ) //如果达到目标状态, 记录所需要的时间, 目标状态不入队.
{
if( ( q[center].sum + T ) < min )
{
min = q[center].sum + T;
pos = center;
}
goto next; //此次中心状态已经没有扩展的必要, 进入下一次中心状态的扩展
}
else
{
strcpy( go, temp );
for( di = 0; di < N; di++ )
{
if( temp[di] == '1' )
{
temp[di] = '0';
k = GetHashNum( temp );
if( !Hash[k].pos ) //返回一人后的状态没有出现过, 入队列
{
Hash[k].pos = 1;
now++;
strcpy( q[now].a, temp );

strcpy( q[now].b, go );

q[now].sum = q[center].sum + T + t[di];
q[now].pos = center;
Hash[k].max = q[now].sum;
}
else //如果出现过, 但是所需的时间比前次所需的时间少, 仍然入队
{
if( q[center].sum + T + t[di] < Hash[k].max )
{
Hash[k].max = q[center].sum + T + t[di];
now++;
strcpy( q[now].a, temp );

strcpy( q[now].b, go );

q[now].pos = center;
q[now].sum = Hash[k].max;
}
}
temp[di] = '1';
}
}
}
}
next:
center++;
}
printf( "1111 %d\n", min );
for( i = pos; i >= 0; ) //从目标状态往前输出最优解
{
if( i != 0 )
printf( "%s\n%s\n", q[i].a, q[i].b );
else
printf( "%s\n", q[i].a );
i = q[i].pos;
}
return 0;
}
int GetHashNum( char s[] ) //二进制Hash
{
int su, i, base;
for( i = 0, base = 1, su = 0; i < N; i++ )
{
if( s[i] == '1' )
su += base;
base *= 2;
}
return su;
}
int convert( )
//对于某一种状态扩展, 记录每人的状态, 如果used[i] = 1则表示i已经过河
{
int i;
for( i = 0; i < N; i++ )
{
if( temp[i] == '1' )
used[i] = 1;
else
used[i] = 0;
}
return 0;
}

运行结果:
1111 17 //(A,B过河)
0011 //(B回来)
0111 //(C,D过河)
0100 //(A回来)
1100 //(A,B过河)
0000 //(初始状态)Top

10 楼ShowLovE（天天）回复于 2005-12-02 14:04:25 得分 0

在网上找到一个类似的问题所做成的在线flash小游戏...
有兴趣的玩一玩啊,挺有意思的...
http://www.tom-1.com/flash/1004.htm

下面是我的程序所得的答案:(程序稍做改动即可) 按时间从小到大排序分别设一家人为ABCDE
11111 29(A,B过桥)
00111(B回来)
01111(D,E过桥)
01100(A回来)
11100(A,C过桥)
01000(A回来)
11000(A,B过桥)
00000(初始状态)
过桥总耗时29秒...比归定少1秒...Top