※ [本文轉錄自 Cabin 信箱]
作者: cabin.bbs@bbs.ntu.edu.tw
標題: [邏輯問題 vs 窮舉法]
時間: Wed Apr 14 01:44:49 1999
作者: Gide (生氣也是因為在乎你) 看板: Joke
標題: [邏輯問題 vs 窮舉法]
時間: Tue Apr 13 13:37:06 1999
[邏輯問題 vs 窮舉法]
常可見到如下的邏輯問題:
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
發信人: user (gto) 看板: a-wu
日期: Tue Apr 13 09:11:55 1999
標題: 邏輯思考
此題源自1981年柏林的邏輯學院,有98%的測驗者無法解題:
前題:1.有五個房子排成一列
2.所有房屋外表顏色都不一樣
3.所有屋主都來自不同的國家
4.所有的屋主都養不同的寵物,喝不同的飲料,抽不同牌的香煙
提示:1.英國人住在紅色房間裡
2.瑞典人養了一隻狗
3.丹麥人喝茶
4.綠色房子在白色房子的左邊
5.綠色房屋的屋主喝咖啡
6.抽Pall Mall 香煙的屋主養鳥
7.黃色屋主抽Dun-Hill 香煙
8.位於最中間的屋主喝牛奶
9.挪威人住在第一房間裡
10.抽Blend 香煙的人住在養貓人家的隔壁
11.養馬的屋主隔壁住抽Dun-Hill 香煙的人家
12.抽Blue Master香煙的屋主喝啤酒
13.德國人抽Prince 香煙
14.挪威人住在藍色房子隔壁
15.只喝白開水的人家住在抽Blend 香煙的隔壁
最後要請問Question:誰養魚??
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
這類問題(看似)十分複雜, (好像)需要十分精闢的分析推理能力, 以及紮實的
邏輯訓練才能夠解出.
我這裡要指出的是: 就算把這類題目解出來了, 也和理性及分析能力沒有太大的
關係.
這種題目和猜幾A幾B是一樣的題目. 引述我以前post過的一篇<論歸謬法, 窮舉法
及理性的極限>中的一段, 讀者就能了解我的意思了:
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
2. 再舉一個我曾寫過的電腦程式為例
大家一定都玩過猜數字的遊戲, 也或許曾用basic寫過程式來一個人進行這個遊
戲.由電腦出題, 我們猜, 電腦提供我們資訊, 幾A幾B, 然後我們修正我們的答
案, 直到最後猜出來了, 電腦告訴我們:「Congratulations! You got the right
answer!」然後程式結束。我不知道大家有沒有試過把這個程式反過來寫, 也就
是我們出題目, 讓電腦來猜, 我們提供電腦資訊, 然後電腦修正答案, 直到最後
猜出來, 我們告訴電腦「4A0B」, 然後電腦說: 「Ha! Ha! I got the right
answer! 」程式結束。讀者至此可以先想一想這樣的程式要怎麼設計。我有最
快的解法, 但是答案會讓大家大失所望。
我讓電腦建立一長串的字串, 此字串從0123始, 9876終, 也就是如下的一個字串
0123、0124、0125、0126、0127、...、0986、0987
1023、1024、1025、1026、1027、...、1986、1987
...
9012、9013、9014、9015、9016、...、9875、9876
共10行,每行分別以0、1、2、3...9開頭
而每行各有9*8*7=504個4位數(由組合得知)
所以整個字串的長度是10*504*4=20160, 非常可觀
電腦第一個會猜整個字串的頭4位數, 就一開始而言會猜"0123"
而如果我們設定的答案是"3718"的話, 我們就告訴電腦"0A2B"
於是電腦會先將"0123"砍除, 並從0124開始核對至最後一個數9876
"如果0124是正確答案的話, 那麼0123與之相比是不是0A2B?不是, 0124亦砍
除"
"如果0125是正確答案的話, 那麼0123與之相比是不是0A2B?不是, 0124亦砍
除"
蔮
"如果3742是正確答案的話, 那麼0123與之相比是不是0A2B?是, 3742保留"
(即使3742不是正確答案)
蔮
就這樣一直核對至9876。經過第一次篩選, 原本長度20160的字串可能已被砍
去大半。於是電腦再從剩下來的字串的第一位開始問, 再將不符合我們回答的
資訊的4位數砍除。如此, 大約只要4次, 就可以把正確答案逼出來。
這是最快、最正確的解法。但也十分讓人失望。
因為當我們以人工在玩時, 我們會作分析、猜測, 我們感覺到在遊戲的過程中,
我們在運作我們的理性, 而愉悅的感覺亦是由此而生。但原來最快的、最正確
的解法居然是如此暴力而不理性的作法。
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
所以, 要解上述的邏輯題目, 其實可以借助電腦幫忙.
step 1.列出所有的配對可能
英國人 Pall Mall 紅色 狗 第一間
瑞典人 Dun-Hill 白色 鳥 第二間
丹麥人 Blend 綠色 貓 第三間
挪威人 Blue Master 黃色 馬 第四間
德國人 Prince 藍色 魚 第五間
共有(5x5x5x5x5x4x4x4x4x4x3x3x3x3x3x2x2x2x2x2x1x1x1x1x1)/5!
=(3125x1024x243x32x1)/5!=207360000種可能, 然後一一將這些可能去和所有條件
比對, 只要有一條不合就劃掉, 最後一定只剩下一種可能(除非題目設計不良, 給
的條件不夠), 或者剩下多種可能, 但是詢問的問題(inquired item)在剩下的可能
中都具有相同的答案(以此題為例, 題目問誰養魚, 將所有可能與條件一一比對之
後最後剩下三種可能符合所有條件, 但三種可能之後養魚的都是英國人, 故答案是
英國人).
把這種題目叫做"邏輯問題", 我覺得有點可笑.
它只是龐大, 只是複雜而已, 解題時其實沒有任何分析與思考的成份在其中.
我將題目簡化, 然後用上述的窮舉法解給大家看:
前題:1.有兩個房子排成一列
2.所有房屋顏色都不一樣:綠色及白色
3.兩個屋主來自不同的國家:英國及美國
4.所有的屋主都養不同的寵物:鳥和魚
提示:1.英國人住綠色房子
2.養鳥的人住在白色房子左邊
最後要請問Question:誰養魚??
一個看似有理性分析成份在其中的解法是這樣的:
因為只有兩個房子, 由提示2知養鳥的人住在白色房子左邊, 所以白色房子一
定是在右邊的那一個. 而左邊的就一定是綠色房子, 由提示1知英國人住在裡
面, 由提示2知道英國人養鳥. 故養魚的是美國人.
但是這則理性分析其實是騙人的, 或者是說不必要的.
根本就可以這麼做:
列出所有配對可能:
美國人(A) 綠(C) 鳥(E) 第一間(1)
英國人(B) 白(D) 魚(F) 第二間(2)
總共有(2x2x2x2x1x1x1x1x1)/2!=8種可能
1. A-C-E-1, B-D-F-2
2. A-C-E-2, B-D-F-1
3. A-C-F-1, B-D-E-2
4. A-C-F-2, B-D-E-1
5. A-D-E-1, B-C-F-2
6. A-D-E-2, B-C-F-1
7. A-D-F-1, B-C-E-2
8. A-D-F-2, B-C-E-1
接著將兩則條件轉換
1.英國人住綠色房子 => B必須配C
2.養鳥的人住在白色房子左邊 => 和E配在一起的第四項
必須小於和D配在一起的第四項
接著一個一個可能去和兩則條件比對
由條件1知1,2,3,4種可能不合
由條件2知5,6,7不合, 故最後剩下第8種可能:
故知養魚的是美國人
所有這類邏輯問題都可以藉助電腦用上述方式解決
並可以發展出一套algorithm
我不覺得這類問題有任何的深度在其中, 充其量只是複雜龐大
只是能夠不藉助電腦就能把這類問題解出來的, 還是很厲害
--
☆ [Origin:椰林風情] [From: cs3po13.ht.ficnet.net.tw] [Login: **] [Post: **]
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: ccsun72.cc.ntu.