五五謎題(prolog程序) (2008-04-02 14:48:29)
標簽： it 分類： 技術交流
內(nèi)容: 1． 有5棟5種顏色的房子 2． 每一位房子的主人國籍都不同 3． 這五個人每人只喝一個牌子的飲料，只抽一個牌子的香煙，只養(yǎng)一種寵物 4． 沒有人有相同的寵物，抽相同牌子的煙，喝相同牌子的飲料 已知條件： 1． 英國人住在紅房子里 2． 瑞典人養(yǎng)了一條狗 3． 丹麥人喝茶 4． 綠房子在白房子的左邊 5． 綠房子主人喝咖啡 6． 抽PALL MALL 煙的人養(yǎng)了一只鳥 7． 黃房子主人抽DUNHILL煙 8． 住在中間房子的人喝牛奶 9． 挪威人住在第一間房子 10． 抽混合煙的人住在養(yǎng)貓人的旁邊 11． 養(yǎng)馬人住在抽DUNHILL煙人的旁邊 12． 抽BLUE MASTER煙的人喝啤酒 13． 德國人抽PRINCE煙 14． 挪威人住在藍房子旁邊 15． 抽混合煙的人的鄰居喝礦泉水 問題：誰養(yǎng)魚？ ============================= 這是個非常有趣的邏輯難題： 有五個房子，每個房子的顏色不同，里面分別住著不同國家的人，每個人都有自己 養(yǎng)的不同的寵物，喜歡和不同的飲料，抽不同牌子的煙。現(xiàn)在已知以下的一些信息 ： 英國人（englishman）住在紅色（red）的房子里。 西班牙人（spaniard）養(yǎng)了一條狗（dog）。 挪威人（norwegian）住在左邊的第一個房子里。 黃房子（yellow）里的人喜歡抽kools牌的香煙。 抽chesterfields牌香煙的人與養(yǎng)狐貍（fox）的人是鄰居。 挪威人（norwegian）住在藍色（blue）的房子旁邊。 抽winston牌香煙的人養(yǎng)了一只蝸牛（Snails）。 抽Lucky Strike牌香煙的人喜歡喝桔子汁（orange juice）。 烏克蘭人（ukrainian）喜歡喝茶（tea）。 日本人（japanese）抽parliaments牌的煙。 抽kools牌的香煙的人與養(yǎng)馬（horse）的人是鄰居。 喜歡喝咖啡（coffee）的人住在綠（green）房子里。 綠（green）房子在象牙白（ivory）房子的右邊（圖中的右邊）。 中間那個房子里的人喜歡喝牛奶（milk）。 根據(jù)以上條件，你能告訴我哪個房子里的人養(yǎng)斑馬（zebra），哪個房子里的人喜 歡喝水（water）嗎？或者你能把所有的東西都對號入座嗎？ 這是個典型的條件約束的問題，根據(jù)每個條件，我們都可以排除一些情況，直到最 后找到答案。不過由于這個問題的條件太多，如果人工來解答，是很要花上一點時 間的。還不如我們用這個時間來編一個程序，讓計算機來解答。真的，編程花的時 間一定要比人工計算還要少！ 使用Prolog來解決這類的問題，一般使用的是“選擇再校驗”的方法。即用某種方 法提出一系列的可能的解，再由校驗部分來判斷此解是否合乎題意。直到找到答案 為止。 我們先來分析一下到底有多少種可能的解。 每個房子有不同的顏色，所以就顏色來說就有5！種情況，而一共有五個特征：顏 色、國籍、寵物、香煙和飲料。所以一共就有5!*5種情況，即600種。不是很多， 完全可以使用程序窮舉出來。 下面介紹如何使用Prolog來編寫解答的程序。 在此程序中使用結構h(C,N,P,Y,D)來儲存房間的信息。C,N,P,Y,D分別對應顏色、 國籍、寵物、香煙和飲料。由于有五個房間，所以使用列表來儲存所有房間的信息 。此列表為： [h(C1,N1,P1,Y1,D1),h(C2,N2,P2,Y2,D2),h(C3,N3,P3,Y3,D3),h(C4,N4,P4,Y4, D4),h(C5,N5,P5,Y5,D5)] 一開始所有房間的情況都是未知的，所以就使用變量來代表每個房間的情況。 在后面的條件中經(jīng)常要讀取房間的某個信息，所以下面就先編寫五個謂詞來完成這 項工作。 color(h(C,N,P,Y,D),C). nation(h(C,N,P,Y,D),N). pet(h(C,N,P,Y,D),P). yan(h(C,N,P,Y,D),Y). drink(h(C,N,P,Y,D),D). 這幾個謂詞很容易理解，所以就不多作解釋了。 在條件中還用到了房間之間的相對位置的信息，下面的謂詞就是完成這個任務的。 next(A,B,[A,B,C,D,E]). next(B,C,[A,B,C,D,E]). next(C,D,[A,B,C,D,E]). next(D,E,[A,B,C,D,E]). next(B,A,[A,B,C,D,E]). next(C,B,[A,B,C,D,E]). next(D,C,[A,B,C,D,E]). next(E,D,[A,B,C,D,E]). middle(X,[_,_,X,_,_]). first(A,[A|X]). 上面，next/3用來判斷列表中兩個元素是否相鄰；middle/2用來讀取列表的中間的 元素；first/2讀取列表的第一個元素。當然，next/3不但可以判斷相鄰，它還能 找出相鄰的元素來。例如： ?- next(4,X,[1,2,3,4,5]). X = 5 ; X = 3 ; no 很明顯，next找出了列表[1,2,3,4,5]中與4相鄰的元素。這里列表的元素是簡單的 數(shù)字，如果是上面說所的表示房間信息的結構h(C,N,P,Y,D)，它的功能也是相同的 。 前面說過，我們將使用“選擇再校驗”的方法找出答案，那么我們靠什么來選擇呢 ？這里將使用以前介紹過的member/2謂詞。還記得member/2的定義么？ member(A,[A|X]). member(A,[B|X]) :- member(A,X). 它的第二個參數(shù)是一個列表，它可以判斷第一個參數(shù)是否在這個列表中。我們是使 用遞歸的方法編寫member/2的，如果不太清楚，請閱讀列表這一章。
?- member(2,[1,2,3]). yes 我們曾經(jīng)說過Prolog的謂詞有多種使用方法，所以member/2還可以用來遍歷列表的 所有元素。 ?-member(X,[1,2,3,4,5]). X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; no 這正是我們需要的功能，使用它就可以選擇出所有的情況了。 有了以上的準備工作，我們就可以開始正式編寫解答部分了。我們先把程序列出來 ，然后再來講解。解題的謂詞為solve/3，第一個參數(shù)X返回所以東西對號入座后的 房間列表，第二參數(shù)TT返回養(yǎng)斑馬的人住的房間，第三個參數(shù)TTT返回喜歡喝水的 人的房間。 solve(X,TT,TTT):- %首先把X綁定為房間列表，注意此時的房間的屬性還不能確定，所以都使用變量 代表。 X=[h(C1,N1,P1,Y1,D1),h(C2,N2,P2,Y2,D2),h(C3,N3,P3,Y3,D3),h(C4,N4,P4, Y4,D4),h(C5,N5,P5,Y5,D5)], %英國人（englishman）住在紅色（red）的房子里。 member(Z1,X), %首先從X列表中選擇一個房間Z1， color(Z1,red), %Z1的顏色是red。 nation(Z1,englishman), %Z1里住的人是englishman。下同。 %西班牙人（spaniard）養(yǎng)了一條狗（dog）。 member(Z2,X), pet(Z2,dog), nation(Z2,spaniard), %挪威人（norwegian）住在左邊的第一個房子里。 first(Z3,X), nation(Z3,norwegian), %黃房子（yellow）里的人喜歡抽kools牌的香煙。 member(Z4,X), yan(Z4,kools), color(Z4,yellow), %抽chesterfields牌香煙的人與養(yǎng)狐貍（fox）的人是鄰居。 member(Z5,X), pet(Z5,fox), next(Z6,Z5,X), %用next(Z5,Z6,X)也一樣。 yan(Z6,chesterfields), %挪威人（norwegian）住在藍色（blue）的房子旁邊。 member(Z7,X), color(Z7,blue), next(Z8,Z7,X), nation(Z8,norwegian), %抽winston牌香煙的人養(yǎng)了一只蝸牛（Snails）。 member(Z9,X), yan(Z9,winston), pet(Z9,snails), %抽Lucky Strike牌香煙的人喜歡喝桔子汁（orange juice）。 member(Z10,X), drink(Z10,'orange juice'), yan(Z10,'Lucky Strike'), %烏克蘭人（ukrainian）喜歡喝茶（tea）。 member(Z11,X), nation(Z11,ukrainian), drink(Z11,tea), %日本人（japanese）抽parliaments牌的煙。 member(Z12,X), nation(Z12,japanese), yan(Z12,parliaments), %抽kools牌的香煙的人與養(yǎng)馬（horse）的人是鄰居。 member(Z13,X), pet(Z13,horse), next(Z14,Z13,X), yan(Z14,kools), %喜歡喝咖啡（coffee）的人住在綠（green）房子里。 member(Z15,X), color(Z15,green), drink(Z15,coffee), %綠（green）房子在象牙白（ivory）房子的右邊（圖中的右邊）。 member(Z16,X), color(Z16,ivory), next(Z17,Z16,X), %這里我們沒有使用右邊的條件，而是假設它們是鄰居，所 以最后的答案有兩個。 color(Z17,green), %這一點請讀者自己修改，當然還需要編寫一個判斷右邊的 謂詞。 %中間那個房子里的人喜歡喝牛奶（milk）。 middle(Z18,X), drink(Z18,milk), %以上是所有的條件，下面開始回答我們的問題。 %找出寵物為zebra的房間。 member(TT,X), pet(TT,zebra), %找出喝水的房間。 member(TTT,X), drink(TTT,water). 你閱讀這個程序應該沒有什么問題吧。它簡直就是把我們的條件直接翻譯成 Prolog語言。例如： %抽chesterfields牌香煙的人與養(yǎng)狐貍（fox）的人是鄰居。 member(Z5,X), pet(Z5,fox), next(Z6,Z5,X), %用next(Z5,Z6,X)也一樣。 yan(Z6,chesterfields), 用語言來描述就是：首先Z5是個房子，對應于member(Z5,X)；然后它的寵物是fox ，對應于pet(Z5,fox)；它的鄰居是Z6，對應于next(Z6,Z5,X)；最后Z6的人抽 chesterfields，對應于yan(Z6,chesterfields)。你看只要把原始的條件稍加分解 ，就變成了我們的Prolog程序。 哈哈，這樣的程序誰都可以編出來，你看到Prolog的優(yōu)勢了吧。Prolog是描述型的 語言，你只要使用Prolog的語言把問題描述一遍就行了，剩下的問題就讓計算機代 勞吧:)。如果使用其它的語言，例如C、Basic等，你就不得不自己考慮程序的流程 ，所以這些語言都叫作過程型的語言。比起Prolog可是低級多了。 好了，最后讓我們來運行一下程序。 ?- solve(X,TT,TTT). X = [h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse, chesterfields,tea), h(red,englishman,snails,winston,milk),h(iory,spaniard,dog,'Lucky Strike','orange juice'), h(green,japanese,zebra,parliaments,coffee)] TT = h(green,japanese,zebra,parliaments,coffee) TTT = h(yellow,norwegian,fox,kools,water) ; X = [h(yellow,norwegian,fox,kools,water),h(blue,ukrainian,horse, chesterfields,tea), h(red,englishman,snails,winston,milk),h(green,japanese,zebra, parliaments,coffee), h(ivory,spaniard,dog,'Lucky Strike','orange juice')] TT = h(green,japanese,zebra,parliaments,coffee) TTT = h(yellow,norwegian,fox,kools,water) no 由于第13個條件中我們沒有使用題目中的右邊的限制，所以答案就有兩個，你可以 看到這兩個答案的最后兩個房間正好倒了過來。 再花點功夫把答案更美觀地寫出來，這個程序就完美了。 好了，到現(xiàn)在為止我只用了1個小時，那些手工解題的朋友們，怎么樣，答案出來 了么
分享
頂
閱讀┊ ┊ ┊┊ ┊打印┊
已投稿到：
排行榜 圈子
加載中，請稍候......
前一篇：博弈論與納什平衡Game Theory and Nash Equilibrium
后一篇：形式化方法
評論 重要提示：警惕虛假中獎信息 在插畫中找尋曾經(jīng)的美好 關注每日最熱門博客
發(fā)評論 旅游行攝，輕品日本 是誰改變了你的博客？ 關注每日最熱門博客
登錄名： 密碼： 找回密碼 注冊
昵 稱：
驗證碼： 請點擊后輸入驗證碼
