3分钟内找出答案的人具有编程的潜力

z6z6j6 · 发表于 2006-12-19 17:40:37

马上注册，结识高手，享用更多资源，轻松玩转三维网社区。

您需要登录才可以下载或查看，没有帐号？注册

x

天黑,雨,四人欲过一座桥.桥破旧,每次最多能容两人同时通过.且只有一支手电(过桥必须用手电). 9 m( |4 d! W( M( N' Y
( ]! d" s! \3 {+ P- N* c
甲单独过桥需1分钟,乙需2分钟,丙需5分钟,丁需7分钟. 5 N" @! J" [; ? l
' t8 W7 S9 B( I& H
则四人全部通过的最短时间是多少.
7 v& d, I) V, ]5 q0 o& S8 l8 ]1 H: a$ }2 Z. C' T
呵呵,试试看.

江边 · 发表于 2006-12-19 19:46:14

9分钟可以么？？

xiaopan83 · 发表于 2006-12-19 19:46:17

8min

江边 · 发表于 2006-12-19 19:48:05

8分钟也能过啊？？？？？我看要9分钟才行。楼上要告诉答案的话，请发信息给我，别告诉其他人啊！

[ 本帖最后由江边于 2006-12-20 09:08 编辑 ]

wgc3306 · 发表于 2006-12-20 08:20:21

1、2过桥，所用时间：2分钟。

1回来，所用时间：1分钟。共用时间3分钟。

5、7过桥，所用时间：7分钟。共用时间10分钟。

2回来，所用时间：2分钟。共用时间：12分钟。

1、2过桥，所用时间：2分钟。共用时间：14分钟。

江边 · 发表于 2006-12-20 09:02:58

厉害！不过我算的是9分钟，再试试。

lizy323 · 发表于 2006-12-20 12:49:20

俺也用14分钟，同5楼

……看来，编程与俺无缘了。

难道是，甲乙过，乙拿手电，1分钟后，丁上桥，1分钟后，甲拿手电返回，再1分钟后，丙拿手电上桥，等丁过桥后（已8分钟，丙拿手电在桥头等一下）甲过桥。共9分钟。

[ 本帖最后由 lizy323 于 2006-12-20 13:06 编辑 ]

namezg · 发表于 2006-12-20 18:32:30

九分种是不可能的,丁至少过河一次,花7分种,就算其余四次都是1分种(不过这是不可能的),也需11分种,哪来的九分种一说。不会不负责任瞎说。也算是14分，不知还有没有更少的。

xiaopan83 · 发表于 2006-12-20 19:16:27

没人相信8MIN就可以啊！！！！！:Q

lizy323 · 发表于 2006-12-21 00:21:34

甲与丁过，丁拿手电，1分钟后，乙上桥，再2分钟后丙上桥，7分钟时丁在桥头等一分钟，与丙在第8分钟同时过桥。

果然8分钟呀！

江边 · 发表于 2006-12-22 08:48:23

八分钟有两个人赞成了，我的九分钟就没有人赞成么？？？？

九楼啊！都没有人相信我九分钟！郁闷

helen000 · 发表于 2006-12-22 09:06:13

我同意8分钟，也没说在同一边

[ 本帖最后由 helen000 于 2006-12-22 09:07 编辑 ]

z6z6j6 · 发表于 2006-12-22 10:47:09

按照编程的思想，14分钟
先让甲和乙过去,甲回去，丙和丁过去，乙回去，最后甲和乙过去。2+1+7+2+2=14分钟。
利用求图的最小生成树的算法，很容易解决
#include
#include

int a[4]={1,2,5,7}; //每人过河时间
int mark[4]; //0左1右
int mark1[100]; //状态控制，只有2^4*2=32种状态
int min;//最短时间

int test(int light) //返回状态值
{
int i,j;
j=0;
for(i=0;i<4;i++)
{
j*=2;
j+=mark;
}
j*=2;
j+=light;
return j;
}

int search(int time,int light) //搜索
{
int state;
int i,j,stime;

state=test(light);
if(state==31) //终态：人和手电都在右岸
{
if(time return 1;
}

if(mark1[state]==1) return 0;

mark1[state]=1;

for(i=0;i<4;i++) //1人
{
if(mark==light)
{
mark=!mark;
stime=a;
search(time+stime,!light);
mark=!mark;
}
}

for(i=0;i<4;i++) //2人
{
if(mark==light)
{
mark=!mark;

for(j=i+1;j<4;j++)
{
if(mark[j]==light)
{
mark[j]=!mark[j];
stime=a[j]>a?a[j]:a;

search(time+stime,!light);
mark[j]=!mark[j];
}
}

mark=!mark;
}
}

mark1[state]=0;
return 0;
}

void main()
{
memset(mark,0,sizeof(mark));
memset(mark1,0,sizeof(mark1));

min=100;

search(0,0);

printf("%d\n",min);
}
结果是14分钟。
提供一个思路：让走的慢的两人同时过桥。

gotry · 发表于 2006-12-22 11:25:38

九分钟多一点可以！！方法如下：
甲、乙一起过，乙拿手电；甲过去时，乙到了桥中间，此时丙开始上桥；乙过去时，丙走过五分之一，此时乙把手电给甲，甲再上桥把手电给丙，来回一分钟不到；当甲重新到对面后，丁可以上桥了！！

gotry · 发表于 2006-12-22 11:28:29

刚才没注意看还是八分钟的对，哈哈，思路和我的一样，应该让甲丁先一起过！！！！

axian · 发表于 2006-12-22 12:18:19

唉,2分钟嘛?甲乙一起过，上面背着丙丁

xie3321 · 发表于 2006-12-22 13:14:56

我觉得应该是14分钟啊.

2005llnn · 发表于 2006-12-22 13:30:05

标准答案：9分钟
甲单独过桥需1分钟,乙需2分钟,丙需5分钟,丁需7分钟
甲乙同过桥需2分钟，交电筒给在桥另一端的丙丁
丙丁同过桥需7分钟，
四人均过桥共需9分钟。
我在2分钟内找出答案。

z6z6j6 · 发表于 2006-12-22 14:23:23

注意是必须用手电，而且要拿着手电照着才能国，不能给别人照着:time:

wgc3306 · 发表于 2006-12-24 13:34:35

白天再走的话，几分钟呢，如果打的要几分钟呢？

qisskiss · 发表于 2006-12-26 16:00:21

我一分钟内的答案是9分钟

qisskiss · 发表于 2006-12-26 16:03:01

不能给别人照着,那我可就有点琢磨不透了

qisskiss · 发表于 2006-12-26 16:07:49

你自己编的题吗?有漏洞啊!
首先不把条件先讲清楚,后来才说不能给其它人照路.另外这四个人是都在桥的一侧还是桥两侧都有人,一共是四个人.

icanyes · 发表于 2006-12-26 17:34:16

应该是六分钟嘛，
快的带上慢的，慢的有快的带路肯定变快拉，
所以由甲来回带就行拉，最短时间应该是甲来回三次的时间和
6分钟

njx · 发表于 2006-12-27 10:40:39

我的答案是16分钟：
因考虑只有一只手电，且一次只能通过2人，所以速度最快者带着。
甲+丁=7
甲回=1
甲+丙=5
甲回=1
甲+乙=2
所以等于16分。

		自动登录	找回密码
密码			注册

通知

[讨论] 3分钟内找出答案的人具有编程的潜力

马上注册，结识高手，享用更多资源，轻松玩转三维网社区。

浏览过的版块