论坛首页 综合技术论坛

逻辑题:住楼问题

浏览 2194 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2008-07-08  
引用
Baker, Cooper, Fletcher, Miller, 和Smith住在一动5层公寓的不同楼层。Baker不在顶楼住。Cooper不在底楼住。Fletcher既不在顶楼也不在底楼。Miller住的楼层比Cooper住的高。Smith和Fletcher的楼层不相邻。Fletcher和Cooper的楼层不相邻。问每个人住的楼层。

把B,C,F,M,S代表表示这五个人分别所住的楼层
也就是说B,C,F,M,S只会取1-5的数值
然后把条件重新排列一下
1. Baker不在顶楼:B可能1,2,3,4
2. Cooper不在底楼:C可能2,3,4,5
3. Fletcher既不在顶楼也不在底楼:F可能2,3,4
4. Miller住的楼层比Cooper住的高: M > C
5. Smith和Fletcher的楼层不相邻: |S-F|>1
6. Fletcher和Cooper的楼层不相邻: |F-C|>1

由 条件 4 稍微推导一下,得到间接条件
7. C不可能顶层,M不可能底层

问题的关键在于两个 不相邻条件, 也就是条件5和条件6
由于它们都是指定与 Fletcher 不相关联,而 Fletcher 只能在2,3,4中取值

依次推导即可。

若 F = 2,由不相邻条件5,6,则 S 与 C 只能在4,5中取值; 根据条件7,只能是 C = 4, 则 S = 5 , 而此时, 根据条件4, M > C, 唯一一个比C大的值5已经被 S 占了,矛盾,所以此路不通

若 F = 3, 由不相邻条件5,6,则 S 与 C 只能在1,5中取值; 而综合条件2和7, C不在顶楼也不在底楼,矛盾,此路也不通

只剩下一种可能性, F = 4
然后后面的就好推断了
依次为:C = 2, S = 1, B = 3, M = 5

     
   发表时间:2008-07-08  
这类问题用Prolog解决是最便捷的。
nobottom(B,[A,B,C,D,E]).
nobottom(C,[A,B,C,D,E]).
nobottom(D,[A,B,C,D,E]).
nobottom(E,[A,B,C,D,E]).
notop(A,[A,B,C,D,E]).
notop(B,[A,B,C,D,E]).
notop(C,[A,B,C,D,E]).
notop(D,[A,B,C,D,E]).
notopbottom(B,[A,B,C,D,E]).
notopbottom(C,[A,B,C,D,E]).
notopbottom(D,[A,B,C,D,E]).

high(E,A,[A,B,C,D,E]).
high(E,B,[A,B,C,D,E]).
high(E,C,[A,B,C,D,E]).
high(E,D,[A,B,C,D,E]).
high(D,A,[A,B,C,D,E]).
high(D,B,[A,B,C,D,E]).
high(D,C,[A,B,C,D,E]).
high(C,A,[A,B,C,D,E]).
high(C,B,[A,B,C,D,E]).
high(B,A,[A,B,C,D,E]).

nonext(A,C,[A,B,C,D,E]).
nonext(A,D,[A,B,C,D,E]).
nonext(A,E,[A,B,C,D,E]).
nonext(B,D,[A,B,C,D,E]).
nonext(B,E,[A,B,C,D,E]).
nonext(C,A,[A,B,C,D,E]).
nonext(C,E,[A,B,C,D,E]).
nonext(D,A,[A,B,C,D,E]).
nonext(D,B,[A,B,C,D,E]).
nonext(E,A,[A,B,C,D,E]).
nonext(E,B,[A,B,C,D,E]).
nonext(E,C,[A,B,C,D,E]).
solve(X,B,C,F,M,S):-  
   X=[1,2,3,4,5],
   member(B,X),
   notop(B,X),
   member(C,X),
   nobottom(C,X),
   member(F,X),
   notopbottom(F,X),
   member(M,X),
   high(M,C,X),
   member(S,X),
   nonext(S,F,X),
   nonext(F,C,X),
   B\==C,
   B\==F,
   B\==M,
   B\==S,
   C\==F,
   C\==M,
   C\==S,
   F\==M,
   F\==S,
   M\==S.

执行
| ?- solve(X,B,C,F,M,S).

B = 3
C = 2
F = 4
M = 5
S = 1
X = [1,2,3,4,5]
0 请登录后投票
   发表时间:2008-07-09  
好像是离散数学里有这东东
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics