Re: [問題] 四對情侶過河問題

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 ((short)(-15074))時間16年前 (2009/08/10 06:07)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

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