ARTICLE · 1138744
小学奥数过桥问题(含习题可打印)
小学奥数过桥问题(含习题可打印)根据题目描述可以捕捉到以下信息： 1、一次最多过2个人 2、必须有手电筒，所以过河之后必须有人送回手电筒 3、2人同行时间按慢的算。 解法分析 我们把这四个人分别标记为a、b、c、d 序号：a b c d 时间：1 2 5 10 由于2人同行，时间按慢的算，所以要想过河总时间最短，所以c和d2个人肯定不能分开过河，如果他们两个分开过河，那分别需要5分钟和10分钟，一共15分钟，如果他们两个一起过河，则总共只需要10分钟。 能不能让他们最先过河呢，也不能，如果让他们两个先过河，那么回来送手电筒至少需要5分钟，而且后面再过河还得5分钟，所以我们要控制来回送手电的时间就必须让时间最短的2个人来送手电筒，也必须让他们最先开始过河。 由此得出，a、b先过河，c、d一起过河 我们按步骤走一下 
总共过河时间一共17分钟。 最优解验证 时间还能更短吗？我们推理一下，4个人要全部过河，一次限制2人，且必须有人返回送手电筒，那么至少得5趟，3趟过去加2趟回来，一趟都少不了，过去3趟按最省时的办法也得cd、ab然后再ab，最后一趟ab是返回送手电筒之后再去过河。 也就是说过河的时间最少是10+2+2=14 回来的两趟最省时的办法就是派a和b回来，时长为1+2=3 14+3=17，所以17就是最优解，再没有比17更短的过河方案了。 公式推广 我们把过河的人数设为n，过河需要的总时间设为Tₙ，过河的人按过河时间从小到大标注为a₁、a₂、a₃......aₙ。 当n=1时，Tₙ = a₁ 当n=2时，Tₙ = a₂ 当n=3时，Tₙ = a₁+a₂+a₃ 当n>3的时候我们每轮先把最慢的2个人送过河，直到人群只剩3个或者2个人。 每轮送最慢的2个人有2种走法 一、两快摆渡(每次先把最慢的两个人送过河) 走法 时间：a₁ + 2a₂ + aₙ 我们分别分析一下n等于4、5的情况，然后推导出递推公式 当n=4时，先把a₃和a₄送过河 a₁、a₂过河，时间a₂ a₁返回送手电筒，时间a₁ a₃、a₄过河，时间a₄ a₂返回送手电筒，时间a₂ 花费时长：a₁+2a₂+a₄ 最后还剩2个人，a₁和a₂，一趟过去，时间是a₂ Tₙ = a₁+2a₂+a₄+(a₂) 当n=5时，先把a₄和a₅送过河 a₁、a₂过河，时间a₂a₁返回送手电筒，时间a₁ a₄、a₅过河，时间a₅a₂返回送手电筒，时间a₂花费时长：a₁+2a₂+a₅ 最后还剩3个人，a₁、a₂、a₃，根据前面的推理，当过河人数为3时，过河时间为a₁+a₂+a₃ Tₙ = a₁+2a₂+a₅+(a₁+a₂+a₃) 当n越来越大时，不管多大，只要n大于3，我们就每次先把最慢的2个送过河，然后继续循环送剩下人群里最慢的两个，直到只剩下2个或3个人为止。 根据前面n=4和n=5的推理，最慢的2个人过河时长为a₁+2a₂+aₙ 所以当有n个人过河时，过河最短时间的公式为： Tₙ = Tₙ₋₂+(a₁+2a₂+aₙ) 当n为偶数时 Tₙ = Tₙ₋₂+(a₁+2a₂+aₙ) =Tₙ-₄+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ) =T₂+(a₁+2a₂+a₄)+(a₁+2a₂+a₆)+...+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ) =a₂+(a₁+2a₂+a₄)+(a₁+2a₂+a₆)+...+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ)当n为奇数时 Tₙ = Tₙ₋₂+(a₁+2a₂+aₙ) =Tₙ-₄+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ) =T₃+(a₁+2a₂+a₅)+(a₁+2a₂+a₇)+...+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ) = (a₁+a₂+a₃)+(a₁+2a₂+a₅)+(a₁+2a₂+a₇)+...+(a₁+2a₂+aₙ₋₂)+(a₁+2a₂+aₙ) 二、最快摆渡(让最快的a₁来回跑) 走法：a₁aₙ 过、a₁ 回、a₁aₙ₋₁ 过、a₁ 回 时间：2a₁ + aₙ₋₁ + aₙ 当有n个人过河时，过河最短时间的公式为： Tₙ = Tₙ₋₂+(2a₁ + aₙ₋₁ + aₙ) 当n为偶数时 Tₙ = Tₙ₋₂+(2a₁ + aₙ₋₁ + aₙ) =Tₙ-₄+(2a₁ + aₙ₋₃ + aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) =T₂+(2a₁+a₃+a₄)+(2a₁+a₅+a₆)+...+(2a₁ + aₙ₋₃ + aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) =a₂+(2a₁+a₃+a₄)+(2a₁+a₅+a₆)+...+(2a₁ + aₙ₋₃+ aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) 当n为奇数时 Tₙ = Tₙ₋₂+(2a₁ + aₙ₋₁ + aₙ) =Tₙ-₄+(2a₁ + aₙ₋₃ + aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) =T₃+(2a₁+a₄+a₅)+(2a₁+a₆+a₇)+...+(2a₁ + aₙ₋₃ + aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) = (a₁+a₂+a₃)+(2a₁+a₄+a₅)+(2a₁+a₆+a₇)+...+(2a₁ + aₙ₋₃ + aₙ₋₂)+(2a₁ + aₙ₋₁ + aₙ) 两种走法综合起来的递归公式是 相关练习 
这就是过桥问题的相关内容，为大家准备了配套习题，附有完整解析希望能帮助大家掌握相关知识点！
题目：四个人过河，分别需要1分钟、2分钟、5分钟、10分钟，一次只能过两人，必须有一人返回送手电筒，最少几分钟可以全部过河?
题意分析
a₁a₂ 过、a₁ 回、aₙ₋₁和aₙ过、a₂ 回
Tₙ = Tₙ₋₂ + min( a₁ + 2a₂ + aₙ , 2a₁ + aₙ₋₁ + aₙ )
更生动的推理过程请看视频👇
关注
重播 分享 赞