一个经典问题 - 过桥问题【数学吧】

05月19日漏签0天

数学吧关注：904,304贴子：8,807,112

4回复贴，共1页

<返回数学吧

一个经典问题 - 过桥问题

只看楼主收藏回复

就是问有N个人晚上要过桥，桥只能最多2人走，且必须拿手电筒才能过，求最快的过桥方案
有个方案是每次都想办法依靠最快的两个人把剩下的最慢的两个人弄到河对岸去，直到剩下3个人或者2个人
有谁知道怎么证明这种方法一定能得到最快的方案呢

送TA礼物

1楼2012-10-16 21:31回复

快慢一起不是取慢的速度吗这样一般选速度接近的一起走

IP属地:安徽

2楼2012-10-16 21:34

收起回复

计算过程是这样的：
如果N=1、2、3，过法显然
当N大于3时，考虑最快的两个和目前剩下的最慢的两个
有两种方案：第一种是最快的一个分别带最慢的那两个过桥，来回两次
第二种方案是最快的两个先过去，然后回来一个，然后最慢的两个再过去，前面先过去的最快的其中一个再回来
比较两种方案，选用较快的那种
如此一直做下去只到只剩2个或者3个人没过

3楼2012-10-16 21:44

有人会吗

4楼2012-10-16 22:23

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

4回复贴，共1页

<返回数学吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴

日	一	二	三	四	五	六

一个经典问题 - 过桥问题

登录百度账号

扫二维码下载贴吧客户端