Question

一道智力题（转）

天黑,雨,四人欲过一座桥.桥破旧,每次最多能容两人同时通过.且只有一支手电(过桥必须用手电).

甲单独过桥需1分钟,乙需2分钟,丙需5分钟,丁需7分钟.

则四人全部通过的最短时间是多少.

呵呵,试试看.

Answer 1

7+1+5+1+2=16

Answer 2

16分钟

Answer 3

无赖算法：
甲乙二人执手电过桥，
不回，径自去睡大觉；
丙丁二人期盼无望，乃互击对方双眼，产生眼冒金星以助过桥。合计9分钟。

马加爵算法：
丁、丙、乙、甲四人按先后排列，各操一锤，齐向前者锤去，最后剩下甲，
甲找长绳一根，长度等于桥长，前端节点捆丁、丙、乙其中一人，后端节点捆余下二者，拖行过桥。
锤人及捆人时间忽略不计，合计2分钟。

哈哈，玩笑，其实可以通过程序来实现：

#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);
}

答案是：

甲+乙=2

甲回=1（2+1=3）

丙+丁=7（3+7=10）

乙回=2（10+2=12）

甲+乙=2（12+2=14）

Answer 4

15分钟