- 浏览: 4172534 次
最新评论
php试题: 四人过桥问题
那是一个漆黑寂静的夜 一家四口穿过了诅咒丛林来到了通往人类世界的无妄之桥 桥头仅有的一盏长明灯 映照着对过桥者的警示:无妄之桥,每次最多只可通行两人,桥上诅咒密布,必须在此长明灯庇佑下方可通过,如果38分钟内未能全员通过——后果自负。。
四人过桥,同一时间只能过两人,并且必须有一人提灯,如何在38分钟内四人均走到桥另一端.
老人, 20分钟,
中年人, 10分钟,
小孩, 5分钟,
年青人, 3分钟
如何处理???
四人过桥,同一时间只能过两人,并且必须有一人提灯,如何在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 分钟过河的有两种走法。
相关推荐
C++实现的数据结构的课程设计,四人过桥题目,算法实现,内含源代码,解决需要求得最短路径问题、有四个人打算过河,这个桥每次最多只能有两个人通过,他们都在桥的某一段,并且是在晚上,过桥需要一只手电筒,而...
四年级奥数题:火车过桥问题习题及答案(B).doc
四人过桥的编程实现,参考博文https://blog.csdn.net/zb872676223/article/details/80205953
奥数:火车过桥(答案版)整理.doc
小四数学第15讲:火车过桥(学生版).docx
小四数学第15讲:火车过桥(教师版).docx
这个问题如果用图论来建模的话,就可以以4个人在桥两端的状态来作为节点来构造一个有向图,如下图所示,以已经过桥了的人的状态作为图的节点,初始时没有人过桥,所以以空
火车过桥问题.pdf
中班数学活动:过桥.doc
包括生产者消费者问题和猴子过桥问题的源代码实现,用C#实现的,带可视化界面,并且包含一个猴子过桥问题exe的安装包生产工程。
过桥问题是一个数学难题,其中一组N人必须在晚上过一座桥。 天很黑,他们只有提着灯才能过桥。 只提供一盏灯,最多两个人可以同时穿过。 如果灯不在一侧,则不可能从一侧穿过。 过马路的时间是最慢的人过马路的时间...
大班体育教案:过桥摘水果.doc
用进程模拟车辆过桥,利用linux进程间通信知识
幼儿园教案2021-中班数学活动:过桥.doc
本文给出了过桥用时最少的一种方法。并不保证采用其他方法仍然可以达到该值。可以肯定,采用其他方法所用时间不能小于采用本文方法所用时间。
这个题目是求N个人(N由自己输入)过桥的最少时间,规则是晚上过桥,只有一个火把,每次最多两个人一起过桥,每个人的过桥时间不一样(每个人过桥的时间由用户输入),两个人一起过去的时候以过桥时间最大的那个人...
幼儿园教案2021-大班体育教案:过桥摘水果.doc
在两个城市南北方向之间存在一条铁路,多列火车可以分别从两个城市的车站排队等待进入车道向对方城市行驶,该铁路在同一时间,只能允许在同一方向上行车,如果同时有相向的火车行驶将会撞车。请模拟实现两个方向行车...
这个题目是求N个人(N由自己输入)过桥的最少时间,规则是晚上过桥,只有一个火把,每次最多两个人一起过桥,每个人的过桥时间不一样(每个人过桥的时间由用户输入),两个人一起过去的时候以过桥时间最大的那个人...
描述一个场景:在悬崖两边有一大堆猴子,猴子大小不一,中间有一个独木桥,每次只能单方向通过一定量的猴子,要使用一种调度算法,要使猴子序列能安全通过独木桥到达对岸!