※ 引述《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)