逻辑题：住楼问题

引用

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不可能底层

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

依次推导即可。

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

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

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

     

评论

2 楼 xly_971223 2008-07-09  

好像是离散数学里有这东东

1 楼 dennis_zane 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]