※ 引述《hcldesmond (●^▽^●)》之铭言： : 相信大家都听过经典的狼羊草过河问题 : 以下的也很类似 : --- : 有四对情侣要过河，河上有一艘小艇，每次最多只能载二人 : 河中央有一个小岛，可让部分人或所有人暂时站在那里 : 四位男生互相妒忌，任何时候某位女生与其他男生待在一起时，她的男友必然在她身边 : 四位女生都怕自己的男友会移情别恋，所以任何一位女生在小岛或岸边独处时， : 除了她的男友外，其他男生都不能独自划艇，即使他的目的地不是该女生所在之处 : 问题是：每次小艇载人从一地往另一地算一步的话，如何用最少步数把所有人带到对岸？ 写一下我推文里写的 19 步解好了 (以下有做法) 以 ABCD 表四男, abcd 表四女, []表地点, <>表要出发的人 1. [ABCD<ab>cd] [] [] 2. [ABCDcd] [a<b>] [] 3. [ABCD<bc>d] [a] [] 4. [ABCDd] [ab<c>] [] 5. [ABCD<cd>] [ab] [] 6. [ABCD] [abc<d>] [] 7. [<AB>CDd] [abc] [] 8. [CDd] [abc] [A<B>] 9. [<BC>Dd] [abc] [A] 10. [Dd] [abc] [AB<C>] 11. [<CD>d] [abc] [AB] 12. [d] [abc] [ABC<D>] 13. [<Dd>] [abc] [ABC] 14. [] [abc] [ABCD<d>] 15. [] [<ab>cd] [ABCD] 16. [] [cd] [ABCDa<b>] 17. [] [<bc>d] [ABCDa] 18. [] [d] [ABCDab<c>] 19. [] [<cd>] [ABCDab] End.[] [] [ABCDabcd] 想法很简单 既然男生被"绑"在女友身边 那一开始就先送女生出去 六步之後剩下 d 女 再把男生送过去 11.当中 D 男可以出发是因为所有男生都过去了 於是12.根据限制只有 D 男可以划回来 然後就是13.这一步把情形转成7.之前的反向 所以就全部过去了 至於最少步数的讨论 一个显然的下限是在没有任何限制时的步数 13 步 (六次两个过去一个过来 最後两个人过去 共 13 步) 而这里显然有不能到达13步的限制 因此接下来就是找有没有其他14~18步的解了 -- 'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.250.80 ※ 编辑: LPH66 来自: 140.112.250.80 (08/10 06:19)