100个python算法超详细讲解：谜语博士的难题

【100个python算法超详细讲解】@谷哥技术

谜语博士遇到了两个难题，先来看第一个难题。

谜语博士的难题（一）
1．问题描述
诚实族和说谎族是来自两个岛屿的不同民族，已知诚实族的人永远说真
话，而说谎族的人永远说假话。
一天，谜语博士遇到三个人，知道他们可能是来自诚实族或说谎族的
人。为了调查这三个人到底来自哪个族，博士分别问了他们问题，下面是他
们的对话：
博士问：“你们是什么族的？”
第一个人回答说：“我们之中有两个来自诚实族。”
第二个人说：“不要胡说，我们三个人中只有一个是来自诚实族的。”
第三个人接着第二个人的话说：“对，确实只有一个是诚实族的。”
请根据他们的回答编程判断出他们分别是来自哪个族的。
2．问题分析
假设这三个人分别用A、B、C三个变量来代表，若某个人说谎则其对应
的变量值为0，若诚实则其对应的变量值为1。根据题目中三个人的话分析如
下：
1）第一个人回答说：“我们之中有两个来自诚实族。”
因此如果第一个人（用A代表第一个人）说的是真话，则A来自诚实族，
另外两个人中一个来自诚实族，一个来自说谎族，则有表达式(not A)and
A+B+C==2
如果A说的是假话，则A来自说谎族，A的话也一定是假话，因此三个人
中来自诚实族的人必定不是两个，则有表达式(not A) and A+B+C !=2
2）第二个人说：“不要胡说，我们三个人中只有一个是来自诚实族的。”
如果第二个人（用B来代表第二个人）说的是真话，则B来自诚实族，而
另外两个人都来自说谎族，则有表达式B and A+B+C==1
如果第二个人B说的是假话，则B来自说谎族，且三个人中来自诚实族的
人数必定不是一个，则有表达式(not B) and A+B+C !=1
3）第三个人说：“对，确实只有一个是诚实族的。”
如果第三个人（用C代表第三个人）说的是真话，则C来自诚实族，另外
两个人都来自说谎族。则有表达式C and A+B+C==1
如果C说的是假话，则C来自说谎族，且有表达式：(not C) and A+B+C
!=1
3．算法设计
在问题分析中我们已经列出了各种可能情况，接下来就可以使用穷举法
来获得最终的判断结果了。
下面使用Python中的逻辑表达式将问题分析中得到的6个条件表达出来，
逻辑表达式如下：
(A and A+B+C = =2 or (not A) and A+B+C !=2) and (B and A+B+C = =1 or (not B) and A+B+C !=1)
and (C and A+B+C = =1 or (not C) and A+B+C !=1)
在程序中穷举每个人的各种可能情况，并代入上面的逻辑表达式中进行
推理运算，则使该逻辑表达式的值均为真的结果就是正确的结果。
4．确定程序框架
程序的流程图如图6.13所示

 5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: ?TF-8 -*-
#author: liuhefei
#desc: 谜语博士的难题(一)
if __name__ == "__main__":
#分别使用A、B、C代表第一个、第二个和第三个人，说谎对应的变量值为0，诚实对应的变
量值为1
for A in range(2):
for B in range(2):
for C in range(2):
#逻辑判断条件
if ((A and A + B + C == 2) or (not A and A + B + C != 2))
and ((B and A + B + C == 1) or (not B and A + B + C != 1))
and ((C and A + B + C == 1) or (not C and A + B + C != 1)):
a = "诚实族" if A else "说谎族"
b = "诚实族" if B else "说谎族"
c = "诚实族" if C else "说谎族"
print("第一个人来自" + a )
print("第二个人来自" + b)
print("第三个人来自" + c)

还可以将上面的程序中的逻辑判断条件分开判断，即使用多个if语句，代
码如下：         

#!/usr/bin/python3
# -*- coding: ?TF-8 -*-
#author: liuhefei
#desc: 谜语博士的难题(一)
if __name__=="__main__":
# 分别使用A、B、C代表第一个、第二个和第三个人，说谎对应的变量值为0，诚实对应的变量值为1
for A in range(2):
for B in range(2):
for C in range(2):
#使用多个if语句判断
if (A and A + B + C == 2) or (not A and A + B + C != 2):
if(B and A + B + C == 1) or (not B and A + B + C != 1):
if(C and A + B + C == 1) or (not C and A + B + C != 1):
if A == 0:
a = "说谎族"
else:
a = "诚实族"
if B == 0:
b = "说谎族"
else:
b = "诚实族"
if C == 0:
c = "说谎族"
else:
c = "诚实族"
#print(A,B,C)
print("第一个人来自" + a)
print("第二个人来自" + b)
print("第三个人来自" + c)

两种方式的运行结果都是相同的。
6．运行结果
在PyCharm下运行程序，结果如图6.14所示。由图6.14可见，这三个人都
来自说谎族。

谜语博士的难题（二）
1．问题描述
两面族是岛屿上的一个新民族，他们的特点是说话时一句真话一句假
话，真假交替。即如果第一句说的是真话，则第二句必为假话；如果第一句
说的是假话，则第二句必然是真话。但第一句话到底是真假却不得而知。
现在谜语博士碰到了三个人，这三个人分别来自三个不同的民族，诚实
族、说谎族和两面族。谜语博士和这三个人分别进行了对话。
首先，谜语博士问左边的人：“中间的人是哪个族的？”左边的人回答
说：“是诚实族的。”
谜语博士又问中间的人：“你是哪个族的？”中间的人回答说：“两面族
的。”
最后，谜语博士问右边的人：“中间的人到底是哪个族的？”右边的人回答
说：“是说谎族的。”
现在请编程求出这三个人各自来自哪个族。
2．问题分析
显然，谜语博士碰到的第二个难题要比第一个难题更为复杂。但是解题
思路与第一个难题是类似的，相信读者已经对该类问题的解题方法有所了解
了。
由于现在不仅需要判断三个人的民族，而且这三个人还存在相对的位置
关系，因此像谜语博士的难题（一）中那样简单定义三个变量还不足以描述
难题（二）中的情况。
首先还是用变量将三个民族表示出来，表示的时候还要考虑到他们之间
的位置关系。我们可以采用如下方式来定义变量：
·变量L=1，表示左边的人来自诚实族。
·变量M=1，表示中间的人来自诚实族。
·变量R=1，表示右边的人来自诚实族。
·变量LL=1，表示左边的人来自两面族。
·变量MM=1，表示中间的人来自两面族。
·变量RR=1，表示右边的人来自两面族。
根据上述变量定义方式，有：
·左边的人来自说谎族，则L!=1且LL!=1。
·中间的人来自说谎族，则M!=1且MM!=1。
·右边的人来自说谎族，则R!=1且RR!=1。
从上述变量定义可以看到，为解决第二个难题，变量的数目已经变为6
个。下面我们来分析题目中谜语博士与三个人的对话。
根据题目中三个人的回答做分析如下。
1）左边的人说中间的人是诚实族的。
若左边的人说的是真话，则他来自诚实族，且中间的人也是诚实族的。
这种情况可用表达式表达为：
L and (not LL) and M and (not MM)
上面的表达式的含义为左边及中间的人是诚实族的同时不可能是两面族
的。
若左边的人说的是假话，则可以肯定他不是诚实族的，且中间的人也不
是诚实族的。这种情况可用表达式表达为：
(not L) and (not M)
上面的表达式的含义为左边及中间的人肯定不是诚实族的，但不能确定
他们到底来自说谎族还是两面族。
综合起来，根据左边人的回答可得到逻辑表达式：
(L and (not LL) and M and (not MM)) or ( (not L) and (not M))
2）中间的人说自己是两面族的。
若中间的人说的是真话，则他来自两面族；若中间的人说的是假话，则
他来自说谎族。因此，可以判断出中间的人肯定不是诚实族的。这种情况可
用表达式表达为：
not M
3）右边的人说中间的人是说谎族的。
·若右边的人来自诚实族，则中间的人是说谎族的。这种情况可用表达式
表达为：
R and (not M) and (not MM)
·若右边的人来自两面族，则无法判断其话的真假，即无法确定中间的人
来自哪个族。这种情况可用表达式表达为：
RR and (not R)
·若右边的人来自说谎族，且中间的人不是说谎族的，而是诚实族或两面
族的。这种情况可用表达式表达为：
(not R) and (not RR) and (M or MM)
综合起来，根据右边的人的回答可得到逻辑表达式：
R and (not M) and (not MM) or (RR and (not R)) or ((not R) and (not RR) and (M or MM))
4）由于题目中说“三个人分别来自三个不同的民族”，因此可以得出如下
表达式：
(L+LL !=2 and M+MM !=2 and R+RR !=2) and (L+M+R ==1 and LL+MM+RR = =1)
3．算法设计
在问题分析中我们已经列出了各种可能的情况，接下来仍然使用穷举法
来获得最终的判断结果。
下面使用Python语言中的逻辑表达式将问题分析中得到的全部逻辑条件表
达出来，具体如下：
(L and (not LL) and M and (not MM)) or ( (not L) and (not M)) and (not M)
and (R and (not M) and (not MM) or (RR and (not R)) or ((not R) and (not RR) and (M or MM)))
and L+LL !=2 and M+MM !=2 and R+RR !=2 and L+M+R ==1 and LL+MM+RR = =1
在程序中穷举每个人的各种可能情况，并代入上面的逻辑表达式中进行
推理运算，则使该逻辑表达式的值均为真的结果就是正确的结果。
4．确定程序框架
该程序的流程图如图6.15所示。

 

 5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: ?TF-8 -*-
#author: liuhefei
#desc: 谜语博士的难题(二)
if __name__=="__main__":
#分别使用变量L、M、R表示左边、中间、右边的人来自诚实族
#分别使用变量LL、MM、RR表示左边、中间、右边的人来自两面族
#0表示说谎，1表示诚实
for L in range(2): #穷举
for M in range(2):
for R in range(2):
for LL in range(2):
for MM in range(2):
for RR in range(2):
if ((L and (not LL) and M and (not MM)) or ((not L)
and (not M)) and (not M)):
if ((R and (not M) and (not MM) or (RR and (not R)))
or ((not R) and (not RR) and (M or MM))):
if ((L + LL != 2) and (M + MM != 2) and (R
+ RR != 2)
and (L + M + R == 1) and (LL + MM +
RR == 1)):
# 使用三元表达式
l = "两面族" if LL else ("诚实族" if L else
"说谎族")
m = "两面族" if MM else ("诚实族" if M else
"说谎族")
r = "两面族" if RR else ("诚实族" if R else
"说谎族")
print("左边的人来自" + l)
print("中间的人来自" + m)
print("右边的人来自" + r)

6．运行结果
在PyCharm下运行程序，结果如图6.16所示。由图6.16可见，左边的人来
自两面族，中间的人来自说谎族，右边的人来自诚实族。