四對情侶過河問題 - 拼圖

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

--