人在德国社区 - Powered by Discuz! Board

标题: [其他] 一个经典问题，只要你给出算法即可，当然一定要明确 [打印本页]

作者: 班超 时间: 2006-12-10 17:36 标题: 一个经典问题，只要你给出算法即可，当然一定要明确

爱因斯坦在20世纪初出的。
　　
1、在一条街上，有5座房子，喷了5种颜色。
　　2、每个房里住着不同国籍的人
　　3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
　　问题是：谁养鱼？
　　
提示：
　　1、英国人住红色房子
　　2、瑞典人养狗
　　3、丹麦人喝茶
　　4、绿色房子在白色房子左面
　　5、绿色房子主人喝咖啡
　　6、抽Pall Mall 香烟的人养鸟
　　7、黄色房子主人抽Dunhill 香烟
　　8、住在中间房子的人喝牛奶
　　9、挪威人住第一间房
　　10、抽Blends香烟的人住在养猫的人隔壁
　　11、养马的人住抽Dunhill 香烟的人隔壁
　　12、抽Blue Master的人喝啤酒
　　13、德国人抽Prince香烟
　　14、挪威人住蓝色房子隔壁
　　15、抽Blends香烟的人有一个喝水的邻居
　　

作者: 班超 时间: 2006-12-10 17:39 标题: 哦

发帖时间起3小时内给出好办法者偶请你吃饭。

[ 本帖最后由班超于 2006-12-10 17:48 编辑 ]

作者: trau 时间: 2006-12-10 18:14

小班班，这题俺做过不止两次了，你干脆直接请我吃饭好了:naughty:

作者: 班超 时间: 2006-12-10 18:25 标题: 好

原帖由 trau 于 2006-12-10 18:14 发表
小班班，这题俺做过不止两次了，你干脆直接请我吃饭好了:naughty:

请写出来办法。

作者: dongfeng71 时间: 2006-12-10 18:37

很容易解，德国人住绿色的房子、喝咖啡、抽Prince 牌香烟、养鱼。

班超班长老请大餐噢！

作者: dongfeng71 时间: 2006-12-10 19:51

目前得出的唯一的解答刚刚已经通过音频对话详细阐述给出题人了，打字传上来太繁琐，推理结果是唯一的，即：

黄	蓝	红	绿	白
水	茶	牛奶	咖啡	啤酒
Dunhill	Blends	Pall Mall	Prince	Blue Master
猫	马	鸟	鱼	狗
挪威	丹麦	英国	德国	瑞典

作者: 班超 时间: 2006-12-10 20:01 标题: ok

原帖由 dongfeng71 于 2006-12-10 19:51 发表
目前得出的唯一的解答刚刚已经通过音频对话详细阐述给出题人了，打字传上来太繁琐，推理结果是唯一的，即：

黄蓝
红
绿
白
水
茶
牛奶咖啡啤酒 Dunhill
Blen ...

作者: maxmax 时间: 2006-12-10 20:39

答案并不是唯一的,应该有两组.
因为第9条说到、挪威人住第一间房,即挪威人可能住左边第一间,也可能住右边第一间.但其实两组答案是一个意思.

作者: dongfeng71 时间: 2006-12-10 22:31

原帖由 maxmax 于 2006-12-10 20:39 发表
答案并不是唯一的,应该有两组.
因为第9条说到、挪威人住第一间房,即挪威人可能住左边第一间,也可能住右边第一间.但其实两组答案是一个意思.

提醒的很好！应当考虑最右边的房是第一间房的情况。如果这样定义第一间房，也只有一种解答，即：

绿	白	红	蓝	黄
咖啡	啤酒	牛奶	茶	水
Prince	Blue Master	Pall Mall	Blends	Dunhill
鱼	狗	鸟	马	猫
德国	瑞典	英国	丹麦	挪威

非常感谢！看来还是集思广益啊。

班超老前辈要兑现承诺哦，俺们期待着你的大餐宴请噢！

作者: trau 时间: 2006-12-10 22:57

嗯。。。答案和6楼一样，不过8楼说的那点当初我也没有考虑到

至于算法就是从9开始，然后根据提示找出可能出现的情况，最后再和已知的进行比较，一一排除。

老早就把算法通过msn总结给出题人了，不过被告知比较繁琐，晕~~~~~~

等最科学的算法

作者: sagood 时间: 2006-12-10 23:24

另类解法zz：

有五个房子，每个房子的颜色不同，里面分别住着不同国家的人，每个人都有自己
养的不同的宠物，喜欢和不同的饮料，抽不同牌子的烟。现在已知以下的一些信息
：

英国人（englishman）住在红色（red）的房子里。
西班牙人（spaniard）养了一条狗（dog）。
挪威人（norwegian）住在左边的第一个房子里。
黄房子（yellow）里的人喜欢抽kools牌的香烟。
抽chesterfields牌香烟的人与养狐狸（fox）的人是邻居。
挪威人（norwegian）住在蓝色（blue）的房子旁边。
抽winston牌香烟的人养了一只蜗牛（Snails）。
抽Lucky Strike牌香烟的人喜欢喝桔子汁（orange juice）。
乌克兰人（ukrainian）喜欢喝茶（tea）。
日本人（japanese）抽parliaments牌的烟。
抽kools牌的香烟的人与养马（horse）的人是邻居。
喜欢喝咖啡（coffee）的人住在绿（green）房子里。
绿（green）房子在象牙白（ivory）房子的右边（图中的右边）。
中间那个房子里的人喜欢喝牛奶（milk）。
根据以上条件，你能告诉我哪个房子里的人养斑马（zebra），哪个房子里的人喜
欢喝水（water）吗？或者你能把所有的东西都对号入座吗？

这是个典型的条件约束的问题，根据每个条件，我们都可以排除一些情况，直到最
后找到答案。不过由于这个问题的条件太多，如果人工来解答，是很要花上一点时
间的。还不如我们用这个时间来编一个程序，让计算机来解答。真的，编程花的时
间一定要比人工计算还要少！

使用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)]

一开始所有房间的情况都是未知的，所以就使用变量来代表每个房间的情况。

在后面的条件中经常要读取房间的某个信息，所以下面就先编写五个谓词来完成这
项工作。

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相邻的元素。这里列表的元素是简单的
数字，如果是上面说所的表示房间信息的结构h(C,N,P,Y,D)，它的功能也是相同的
。

前面说过，我们将使用“选择再校验”的方法找出答案，那么我们靠什么来选择呢
？这里将使用以前介绍过的member/2谓词。还记得member/2的定义么？

member(A,[A|X]).
member(A,[B|X]) :- member(A,X).

它的第二个参数是一个列表，它可以判断第一个参数是否在这个列表中。我们是使
用递归的方法编写member/2的，如果不太清楚，请阅读列表这一章。

?- member(2,[1,2,3]).

yes

我们曾经说过Prolog的谓词有多种使用方法，所以member/2还可以用来遍历列表的
所有元素。

?-member(X,[1,2,3,4,5]).

X = 1 ;

X = 2 ;

X = 3 ;

X = 4 ;

X = 5 ;
no

这正是我们需要的功能，使用它就可以选择出所有的情况了。

有了以上的准备工作，我们就可以开始正式编写解答部分了。我们先把程序列出来
，然后再来讲解。解题的谓词为solve/3，第一个参数X返回所以东西对号入座后的
房间列表，第二参数TT返回养斑马的人住的房间，第三个参数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）养了一条狗（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牌香烟的人与养狐狸（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牌香烟的人养了一只蜗牛（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牌的香烟的人与养马（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牌香烟的人与养狐狸（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的优势了吧。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个条件中我们没有使用题目中的右边的限制，所以答案就有两个，你可以
看到这两个答案的最后两个房间正好倒了过来。

作者: dongfeng71 时间: 2006-12-11 01:19

破解谁养斑马的新问题：

这道题如果用列出5乘5矩阵的方法，推理填空解答，明显比班超出的第一道题难一些，需要经过先后两次可能性讨论，因为在推理过程中先后两次出现了符合条件的两种可能结果。每一次，其中的一种可能结果被填入并且在此基础上依照已知条件继续推理填空，就会和已知条件相矛盾，于是只能采用另一种可能结果。最终只有一个正确答案，即：

黄	蓝	红	白	绿
水	茶	牛奶	橘汁	咖啡
kools	Chesterfields	Winston	Lucky Strike	Parliaments
狐狸	马	蜗牛	狗	斑马
挪威	乌克兰	英国	西班牙	日本

LZ 提出的循环嵌套、每种排列组合逐一检验的方法我不太懂，根本不了解 Prolog 程序，准备请教一下班超、qquchn 版主，当然还有 Sagood 等 Infomatik 专家。

[ 本帖最后由 dongfeng71 于 2006-12-11 01:32 编辑 ]

作者: bbyuanyuan 时间: 2006-12-11 11:44

这些个Prolog语句虽然没学过但也能看，可是这个里似乎是每个条件都新建了一个房间，最后编号一直到了z18...
怎么在最后把这些z都和x里头的h对应起来呀？

欢迎光临人在德国社区 (http://csuchen.de/bbs/)