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

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 ((short)(-15074))時間16年前 (2010/03/01 11:25)推噓2(2推 0噓 0→)

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

※ 引述《hcldesmond (●^▽^●)》之銘言： : 相信大家都聽過經典的狼羊草過河問題 : 以下的也很類似 : --- : 有四對情侶要過河，河上有一艘小艇，每次最多只能載二人 : 河中央有一個小島，可讓部分人或所有人暫時站在那裡 : 四位男生互相妒忌，任何時候某位女生與其他男生待在一起時，她的男友必然在她身邊 : 四位女生都怕自己的男友會移情別戀，所以任何一位女生在小島或岸邊獨處時， : 除了她的男友外，其他男生都不能獨自划艇，即使他的目的地不是該女生所在之處 : 問題是：每次小艇載人從一地往另一地算一步的話，如何用最少步數把所有人帶到對岸？今天心血來潮 (其實是正好在弄另一個類似的東西 XD) 寫了支程式來跑這個舊題目 XD 以下是程式所給的答案: (防雷空白頁) 1. [ABCD<ab>cd] [] [] 2. [ABCDcd] [<a>b] [] 3. [ABCD<ac>d] [b] [] 4. [ABCDd] [b] [<a>c] 5. [ABCD<ad>] [b] [c] 6. [ABCD] [b] [<a>cd] 7. [AB<CD>a] [b] [cd] 8. [ABa] [b] [CDc<d>] 9. [ABa] [<b>d] [CDc] 10. [Aa<Bb>] [d] [CDc] 11. [Aa] [d] [BC<D>bc] 12. [<AD>a] [d] [BCbc] 13. [a] [d] [ABCD<b>c] 14. [<ab>] [d] [ABCDc] 15. [] [d] [ABCDab<c>] 16. [] [<cd>] [ABCDab] End.[] [] [ABCDabcd] 計 16 步仔細一看可以發現「有女生獨處時其男朋友之外不得獨划」這條規則其實用到次數不多只影響 11. 時從目的地回來的人選而己有趣的是如果將條件限嚴一點成「女生獨處時任何男生皆不得獨划」最少步數依然是 16 步船也是這樣子的移動只有 10,11,12 三步更改而已: 9. [ABa] [<b>d] [CDc] 10. [<AB>ab] [d] [CDc] 11. [ab] [d] [ABCD<c>] 12. [a<bc>] [d] [ABCD] 13. [a] [d] [ABCD<b>c] 頁末防雷 -- 'You've sort of made up for it tonight,' said Harry. 'Getting the sword. Finishing the Horcrux. Saving my life.' 'That makes me sound a lot cooler then I was,' Ron mumbled. 'Stuff like that always sounds cooler then it really was,' said Harry. 'I've been trying to tell you that for years.' -- Harry Potter and the Deathly Hollows, P.308 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92