php试题: 四人过桥问题

寂寞大萝卜

那是一个漆黑寂静的夜 一家四口穿过了诅咒丛林来到了通往人类世界的无妄之桥 桥头仅有的一盏长明灯  映照着对过桥者的警示：无妄之桥，每次最多只可通行两人，桥上诅咒密布，必须在此长明灯庇佑下方可通过，如果38分钟内未能全员通过——后果自负。。

四人过桥,同一时间只能过两人,并且必须有一人提灯,如何在38分钟内四人均走到桥另一端.

老人,   20分钟,
中年人,  10分钟,
小孩,  5分钟,
年青人,  3分钟


如何处理???



帖代码的。

穷举所有情况。

用到了几个函数相互递归。复制PHP内容到剪贴板PHP代码:

<?php
//建模数据
$mans=array(
1=>array(
'name'=>'老人',
'time'=>20,
),
2=>array(
'name'=>'中年人',
'time'=>10,
),
3=>array(
'name'=>'小孩',
'time'=>5,
),
4=>array(
'name'=>'青年人',
'time'=>3,
),
);
//初始未过河的人
$a=array(
1=>1,2,3,4,
);
//初始已过河的人
$b=array();
//2人过河
functionGo($a,$b,$m,$serialize=array(),$time=0){
$mm=explode(',',$m);
array_push($serialize,$m);
//过河
unset($a[$mm[0]]);
unset($a[$mm[1]]);
$b[$mm[0]]=$mm[0];
$b[$mm[1]]=$mm[1];

//
$time+=max($GLOBALS['mans'][$mm[0]]['time'],$GLOBALS['mans'][$mm[1]]['time']);

if($a){
doBack($a,$b,$serialize,$time);
}else{
//
if($time<=38){
echo'<fontcolor=red>';
}
echocommonLanguage($serialize).'总时间:'.$time.'<br/>'."/r/n";
if($time<=38){
echo'</font>';
}
array_pop($serialize);
}
}
//1人提灯回去
functionBack($a,$b,$m,$serialize=array(),$time=0){
//过河
unset($b[$m]);
$a[$m]=$m;
array_push($serialize,$m);
//time
$time+=$GLOBALS['mans'][$m]['time'];
doGo($a,$b,$serialize,$time);
}
//遍历已过河的人,从中选择1个人提灯回去.
functiondoBack($a,$b,$serialize=array(),$time=0){
$array=Get1Elem($b);
foreach($arrayas$v){
Back($a,$b,$v,$serialize,$time);
}
}
//从未过河的人中选择2个人过河.
functiondoGo($a,$b,$serialize=array(),$time=0){
$array=Get2Elem($a);
foreach($arrayas$v){
$a;
Go($a,$b,$v,$serialize,$time);
}
}
//从几个人中选择2个人的所有情况
functionGet2Elem($array){
$array2=$array;
foreach($arrayas$k=>$v){
foreach($array2as$kk=>$vv){
if($k!=$kk){
$ar=array($v,$vv);
sort($ar);
$ra[]=implode(',',$ar);
}
}
}
returnarray_unique($ra);
}
//从未过河的所有人中选择1个人的所有情况
functionGet1Elem($array){
$aa=array();
foreach($arrayas$k=>$v){
$aa[$k]=$v;
}
return$aa;
}
//自然语言翻译
functioncommonLanguage($serialize){
foreach($serializeas$v){
$v=explode(',',$v);
foreach($vas$kk=>$vv){
$r.=$GLOBALS['mans'][$vv]['name'].'('.$GLOBALS['mans'][$vv]['time'].')';
}
count($v)==2?$r.='=>':$r.='<=';
}

return$r;

}
//开始穷举
doGo($a,$b);
?>


运行结果：

老人(20)中年人(10)  => 老人(20) <= 小孩(5)青年人(3) => 中年人(10) <= 老人(20)中年人(10) =>  总时间:75
老人(20)中年人(10) => 老人(20) <= 小孩(5)青年人(3) => 小孩(5) <=  老人(20)小孩(5) => 总时间:70
老人(20)中年人(10) => 老人(20) <= 小孩(5)青年人(3) =>  青年人(3) <= 老人(20)青年人(3) => 总时间:68
老人(20)中年人(10) => 老人(20) <=  老人(20)小孩(5) => 中年人(10) <= 中年人(10)青年人(3) => 总时间:80
老人(20)中年人(10)  => 老人(20) <= 老人(20)小孩(5) => 老人(20) <= 老人(20)青年人(3) =>  总时间:100
老人(20)中年人(10) => 老人(20) <= 老人(20)小孩(5) => 小孩(5) <=  小孩(5)青年人(3) => 总时间:70
老人(20)中年人(10) => 老人(20) <= 老人(20)青年人(3) =>  中年人(10) <= 中年人(10)小孩(5) => 总时间:80
老人(20)中年人(10) => 老人(20) <=  老人(20)青年人(3) => 老人(20) <= 老人(20)小孩(5) => 总时间:100
老人(20)中年人(10) =>  老人(20) <= 老人(20)青年人(3) => 青年人(3) <= 小孩(5)青年人(3) =>  总时间:68
老人(20)中年人(10) => 中年人(10) <= 小孩(5)青年人(3) => 老人(20) <=  老人(20)中年人(10) => 总时间:75
老人(20)中年人(10) => 中年人(10) <= 小孩(5)青年人(3)  => 小孩(5) <= 中年人(10)小孩(5) => 总时间:50
老人(20)中年人(10) => 中年人(10) <=  小孩(5)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) => 总时间:48
老人(20)中年人(10) =>  中年人(10) <= 中年人(10)小孩(5) => 老人(20) <= 老人(20)青年人(3) =>  总时间:80
老人(20)中年人(10) => 中年人(10) <= 中年人(10)小孩(5) => 中年人(10) <=  中年人(10)青年人(3) => 总时间:60
老人(20)中年人(10) => 中年人(10) <= 中年人(10)小孩(5)  => 小孩(5) <= 小孩(5)青年人(3) => 总时间:50
老人(20)中年人(10) => 中年人(10) <=  中年人(10)青年人(3) => 老人(20) <= 老人(20)小孩(5) => 总时间:80
老人(20)中年人(10) =>  中年人(10) <= 中年人(10)青年人(3) => 中年人(10) <= 中年人(10)小孩(5) =>  总时间:60
老人(20)中年人(10) => 中年人(10) <= 中年人(10)青年人(3) => 青年人(3) <=  小孩(5)青年人(3) => 总时间:48
老人(20)小孩(5) => 老人(20) <= 中年人(10)青年人(3) =>  小孩(5) <= 老人(20)小孩(5) => 总时间:75
老人(20)小孩(5) => 老人(20) <=  中年人(10)青年人(3) => 中年人(10) <= 老人(20)中年人(10) => 总时间:80
老人(20)小孩(5)  => 老人(20) <= 中年人(10)青年人(3) => 青年人(3) <= 老人(20)青年人(3) =>  总时间:73
老人(20)小孩(5) => 老人(20) <= 老人(20)中年人(10) => 小孩(5) <=  小孩(5)青年人(3) => 总时间:70
老人(20)小孩(5) => 老人(20) <= 老人(20)中年人(10) =>  老人(20) <= 老人(20)青年人(3) => 总时间:100
老人(20)小孩(5) => 老人(20) <=  老人(20)中年人(10) => 中年人(10) <= 中年人(10)青年人(3) => 总时间:80
老人(20)小孩(5)  => 老人(20) <= 老人(20)青年人(3) => 小孩(5) <= 中年人(10)小孩(5) =>  总时间:75
老人(20)小孩(5) => 老人(20) <= 老人(20)青年人(3) => 老人(20) <=  老人(20)中年人(10) => 总时间:100
老人(20)小孩(5) => 老人(20) <= 老人(20)青年人(3) =>  青年人(3) <= 中年人(10)青年人(3) => 总时间:73
老人(20)小孩(5) => 小孩(5) <=  中年人(10)青年人(3) => 老人(20) <= 老人(20)小孩(5) => 总时间:75
老人(20)小孩(5) =>  小孩(5) <= 中年人(10)青年人(3) => 中年人(10) <= 中年人(10)小孩(5) =>  总时间:55
老人(20)小孩(5) => 小孩(5) <= 中年人(10)青年人(3) => 青年人(3) <=  小孩(5)青年人(3) => 总时间:43
老人(20)小孩(5) => 小孩(5) <= 中年人(10)小孩(5) =>  老人(20) <= 老人(20)青年人(3) => 总时间:75
老人(20)小孩(5) => 小孩(5) <=  中年人(10)小孩(5) => 中年人(10) <= 中年人(10)青年人(3) => 总时间:55
老人(20)小孩(5) =>  小孩(5) <= 中年人(10)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) =>  总时间:45
老人(20)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) => 老人(20) <=  老人(20)中年人(10) => 总时间:70
老人(20)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) =>  小孩(5) <= 中年人(10)小孩(5) => 总时间:45
老人(20)小孩(5) => 小孩(5) <=  小孩(5)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) => 总时间:43
老人(20)青年人(3) =>  老人(20) <= 中年人(10)小孩(5) => 青年人(3) <= 老人(20)青年人(3) =>  总时间:73
老人(20)青年人(3) => 老人(20) <= 中年人(10)小孩(5) => 中年人(10) <=  老人(20)中年人(10) => 总时间:80
老人(20)青年人(3) => 老人(20) <= 中年人(10)小孩(5) =>  小孩(5) <= 老人(20)小孩(5) => 总时间:75
老人(20)青年人(3) => 老人(20) <=  老人(20)中年人(10) => 青年人(3) <= 小孩(5)青年人(3) => 总时间:68
老人(20)青年人(3) =>  老人(20) <= 老人(20)中年人(10) => 老人(20) <= 老人(20)小孩(5) =>  总时间:100
老人(20)青年人(3) => 老人(20) <= 老人(20)中年人(10) => 中年人(10) <=  中年人(10)小孩(5) => 总时间:80
老人(20)青年人(3) => 老人(20) <= 老人(20)小孩(5) =>  青年人(3) <= 中年人(10)青年人(3) => 总时间:73
老人(20)青年人(3) => 老人(20) <=  老人(20)小孩(5) => 老人(20) <= 老人(20)中年人(10) => 总时间:100
老人(20)青年人(3) =>  老人(20) <= 老人(20)小孩(5) => 小孩(5) <= 中年人(10)小孩(5) =>  总时间:75
老人(20)青年人(3) => 青年人(3) <= 中年人(10)小孩(5) => 老人(20) <=  老人(20)青年人(3) => 总时间:73
老人(20)青年人(3) => 青年人(3) <= 中年人(10)小孩(5) =>  中年人(10) <= 中年人(10)青年人(3) => 总时间:53
老人(20)青年人(3) => 青年人(3) <=  中年人(10)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) => 总时间:43
老人(20)青年人(3) =>  青年人(3) <= 中年人(10)青年人(3) => 老人(20) <= 老人(20)小孩(5) =>  总时间:73
老人(20)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) => 中年人(10) <=  中年人(10)小孩(5) => 总时间:53
老人(20)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) =>  青年人(3) <= 小孩(5)青年人(3) => 总时间:41
老人(20)青年人(3) => 青年人(3) <=  小孩(5)青年人(3) => 老人(20) <= 老人(20)中年人(10) => 总时间:68
老人(20)青年人(3) =>  青年人(3) <= 小孩(5)青年人(3) => 小孩(5) <= 中年人(10)小孩(5) =>  总时间:43
老人(20)青年人(3) => 青年人(3) <= 小孩(5)青年人(3) => 青年人(3) <=  中年人(10)青年人(3) => 总时间:41
中年人(10)小孩(5) => 中年人(10) <= 老人(20)青年人(3)  => 小孩(5) <= 中年人(10)小孩(5) => 总时间:55
中年人(10)小孩(5) => 中年人(10) <=  老人(20)青年人(3) => 老人(20) <= 老人(20)中年人(10) => 总时间:80
中年人(10)小孩(5) =>  中年人(10) <= 老人(20)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) =>  总时间:53
中年人(10)小孩(5) => 中年人(10) <= 老人(20)中年人(10) => 小孩(5) <=  小孩(5)青年人(3) => 总时间:50
中年人(10)小孩(5) => 中年人(10) <= 老人(20)中年人(10) =>  老人(20) <= 老人(20)青年人(3) => 总时间:80
中年人(10)小孩(5) => 中年人(10) <=  老人(20)中年人(10) => 中年人(10) <= 中年人(10)青年人(3) => 总时间:60
中年人(10)小孩(5)  => 中年人(10) <= 中年人(10)青年人(3) => 小孩(5) <= 老人(20)小孩(5) =>  总时间:55
中年人(10)小孩(5) => 中年人(10) <= 中年人(10)青年人(3) => 中年人(10) <=  老人(20)中年人(10) => 总时间:60
中年人(10)小孩(5) => 中年人(10) <= 中年人(10)青年人(3)  => 青年人(3) <= 老人(20)青年人(3) => 总时间:53
中年人(10)小孩(5) => 小孩(5) <=  老人(20)青年人(3) => 中年人(10) <= 中年人(10)小孩(5) => 总时间:55
中年人(10)小孩(5) =>  小孩(5) <= 老人(20)青年人(3) => 老人(20) <= 老人(20)小孩(5) =>  总时间:75
中年人(10)小孩(5) => 小孩(5) <= 老人(20)青年人(3) => 青年人(3) <=  小孩(5)青年人(3) => 总时间:43
中年人(10)小孩(5) => 小孩(5) <= 老人(20)小孩(5) =>  中年人(10) <= 中年人(10)青年人(3) => 总时间:55
中年人(10)小孩(5) => 小孩(5) <=  老人(20)小孩(5) => 老人(20) <= 老人(20)青年人(3) => 总时间:75
中年人(10)小孩(5) =>  小孩(5) <= 老人(20)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) =>  总时间:45
中年人(10)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) => 中年人(10) <=  老人(20)中年人(10) => 总时间:50
中年人(10)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) =>  小孩(5) <= 老人(20)小孩(5) => 总时间:45
中年人(10)小孩(5) => 小孩(5) <=  小孩(5)青年人(3) => 青年人(3) <= 老人(20)青年人(3) => 总时间:43
中年人(10)青年人(3) =>  中年人(10) <= 老人(20)小孩(5) => 青年人(3) <= 中年人(10)青年人(3) =>  总时间:53
中年人(10)青年人(3) => 中年人(10) <= 老人(20)小孩(5) => 老人(20) <=  老人(20)中年人(10) => 总时间:80
中年人(10)青年人(3) => 中年人(10) <= 老人(20)小孩(5)  => 小孩(5) <= 中年人(10)小孩(5) => 总时间:55
中年人(10)青年人(3) => 中年人(10) <=  老人(20)中年人(10) => 青年人(3) <= 小孩(5)青年人(3) => 总时间:48
中年人(10)青年人(3) =>  中年人(10) <= 老人(20)中年人(10) => 老人(20) <= 老人(20)小孩(5) =>  总时间:80
中年人(10)青年人(3) => 中年人(10) <= 老人(20)中年人(10) => 中年人(10) <=  中年人(10)小孩(5) => 总时间:60
中年人(10)青年人(3) => 中年人(10) <= 中年人(10)小孩(5)  => 青年人(3) <= 老人(20)青年人(3) => 总时间:53
中年人(10)青年人(3) => 中年人(10)  <= 中年人(10)小孩(5) => 中年人(10) <= 老人(20)中年人(10) =>  总时间:60
中年人(10)青年人(3) => 中年人(10) <= 中年人(10)小孩(5) => 小孩(5) <=  老人(20)小孩(5) => 总时间:55
中年人(10)青年人(3) => 青年人(3) <= 老人(20)小孩(5) =>  中年人(10) <= 中年人(10)青年人(3) => 总时间:53
中年人(10)青年人(3) => 青年人(3) <=  老人(20)小孩(5) => 老人(20) <= 老人(20)青年人(3) => 总时间:73
中年人(10)青年人(3) =>  青年人(3) <= 老人(20)小孩(5) => 小孩(5) <= 小孩(5)青年人(3) =>  总时间:43
中年人(10)青年人(3) => 青年人(3) <= 老人(20)青年人(3) => 中年人(10) <=  中年人(10)小孩(5) => 总时间:53
中年人(10)青年人(3) => 青年人(3) <= 老人(20)青年人(3) =>  老人(20) <= 老人(20)小孩(5) => 总时间:73
中年人(10)青年人(3) => 青年人(3) <=  老人(20)青年人(3) => 青年人(3) <= 小孩(5)青年人(3) => 总时间:41
中年人(10)青年人(3) =>  青年人(3) <= 小孩(5)青年人(3) => 中年人(10) <= 老人(20)中年人(10) =>  总时间:48
中年人(10)青年人(3) => 青年人(3) <= 小孩(5)青年人(3) => 小孩(5) <=  老人(20)小孩(5) => 总时间:43
中年人(10)青年人(3) => 青年人(3) <= 小孩(5)青年人(3) =>  青年人(3) <= 老人(20)青年人(3) => 总时间:41
小孩(5)青年人(3) =>  小孩(5) <= 老人(20)中年人(10) => 青年人(3) <= 小孩(5)青年人(3) =>  总时间:38
小孩(5)青年人(3) => 小孩(5) <= 老人(20)中年人(10) => 老人(20) <=  老人(20)小孩(5) => 总时间:70
小孩(5)青年人(3) => 小孩(5) <= 老人(20)中年人(10) =>  中年人(10) <= 中年人(10)小孩(5) => 总时间:50
小孩(5)青年人(3) => 小孩(5) <=  老人(20)小孩(5) => 青年人(3) <= 中年人(10)青年人(3) => 总时间:43
小孩(5)青年人(3) =>  小孩(5) <= 老人(20)小孩(5) => 老人(20) <= 老人(20)中年人(10) =>  总时间:70
小孩(5)青年人(3) => 小孩(5) <= 老人(20)小孩(5) => 小孩(5) <=  中年人(10)小孩(5) => 总时间:45
小孩(5)青年人(3) => 小孩(5) <= 中年人(10)小孩(5) =>  青年人(3) <= 老人(20)青年人(3) => 总时间:43
小孩(5)青年人(3) => 小孩(5) <=  中年人(10)小孩(5) => 中年人(10) <= 老人(20)中年人(10) => 总时间:50
小孩(5)青年人(3) =>  小孩(5) <= 中年人(10)小孩(5) => 小孩(5) <= 老人(20)小孩(5) => 总时间:45
小孩(5)青年人(3) => 青年人(3) <= 老人(20)中年人(10) => 小孩(5) <=  小孩(5)青年人(3) => 总时间:38
小孩(5)青年人(3) => 青年人(3) <= 老人(20)中年人(10)  => 老人(20) <= 老人(20)青年人(3) => 总时间:68
小孩(5)青年人(3) => 青年人(3) <=  老人(20)中年人(10) => 中年人(10) <= 中年人(10)青年人(3) => 总时间:48
小孩(5)青年人(3)  => 青年人(3) <= 老人(20)青年人(3) => 小孩(5) <= 中年人(10)小孩(5) =>  总时间:43
小孩(5)青年人(3) => 青年人(3) <= 老人(20)青年人(3) => 老人(20) <=  老人(20)中年人(10) => 总时间:68
小孩(5)青年人(3) => 青年人(3) <= 老人(20)青年人(3) =>  青年人(3) <= 中年人(10)青年人(3) => 总时间:41
小孩(5)青年人(3) => 青年人(3) <=  中年人(10)青年人(3) => 小孩(5) <= 老人(20)小孩(5) => 总时间:43
小孩(5)青年人(3) =>  青年人(3) <= 中年人(10)青年人(3) => 中年人(10) <= 老人(20)中年人(10) =>  总时间:48
小孩(5)青年人(3) => 青年人(3) <= 中年人(10)青年人(3) => 青年人(3) <=  老人(20)青年人(3) => 总时间:41

38 分钟过河的有两种走法。