100个python算法超详细讲解：旅客国籍

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

1．问题描述
在一个旅馆中住着6个不同国籍的人，他们分别来自美国、德国、英
国、法国、俄罗斯和意大利。他们的名字分别叫A、B、C、D、E和F，要说
明的是名字的顺序与前面提到的国籍不一定是相互对应的。现在已知：
1）A和美国人是医生。
2）E和俄罗斯人是教师。
3）C和德国人是技师。
4）B和F曾经当过兵，而德国人从未参过军。
5）法国人比A年龄大，意大利人比C年龄大。
6）B同美国人下周要去西安旅行，而C同法国人下周要去杭州度假。
现要求根据上述已知条件，编程求出A、B、C、D、E和F各是哪国人。
2．问题分析
根据问题描述中给定的条件可进行如下分析：
·由“A和美国人是医生”可知A不是美国人。
·由“E和俄罗斯人是教师”可知E不是俄罗斯人。
·由“C和德国人是技师”可知C不是德国人。
·又因为A的职业是医生，与俄罗斯人和德国人的职业不同，故A不是俄
罗斯人也不是德国人。E的职业是教师，与美国人和德国人的职业不同，故E
不是美国人也不是德国人。C的职业是技师，与美国人和俄罗斯人不同，故C
不是美国人也不是俄罗斯人。
·由“B和F曾经当过兵，而德国人从未参过军”可知，B和F不是德国人。
·由“法国人比A年龄大，意大利人比C年龄大”可知，A不是法国人，C不
是意大利人。
·由“B同美国人下周要去西安旅行，而C同法国人下周要去杭州度假”可
知，B不是美国人，也不是法国人，C不是法国人。
用条件矩阵将上面的分析结果表示出来：

根据上面的条件矩阵使用消去法，即可得到问题的结果。
3．算法设计
下面给出从条件矩阵初始化到完成消去得到结果的整个过程中条件矩阵
每一步的变化，矩阵中加粗的元素表示在该步骤中该元素发生了变化。具体
变化过程如下：
1）初始化条件矩阵。

 2）将问题分析中得出的结果在条件矩阵中表示出来。

 条件矩阵中为0的项表示不是该国的人，同时将条件矩阵中每一列的0号
元素都置为1，用来表示该列尚未进行处理。
3）第4列只有一个元素为0，执行消去操作。
执行消去操作时从只有一个元素为非0的列开始消去。

 将条件矩阵中非零元素所在行的其他元素都置为0，同时置a[0][4]为0，
表示条件矩阵中第4列已处理完毕。
4）第1列只有一个元素为0，执行消去操作。
显然，当条件矩阵位于状态（c）时，第1列中只有一个元素非0，可执
行消去操作。

5）第3列只有一个元素为0，执行消去操作。
显然，当条件矩阵位于状态（d）时，第3列中只有一个元素非0，可执
行消去操作。

6）第6列只有一个元素为0，执行消去操作。
显然，当条件矩阵位于状态（e）时，第6列中只有一个元素非0，可执
行消去操作。

7）第5列只有一个元素为0，执行消去操作。
显然，当条件矩阵位于状态（f）时，第5列中只有一个元素非0，可执行
消去操作。

8）第2列只有一个元素为0，执行消去操作。
当条件矩阵位于状态（g）时，只有第2列还未被处理，经观察发现，该
非零元素所在行（第3行）的所有其他元素都已经为0了，但在我们编程实现
时，程序还是会对该行的每个元素都检查一遍。 

执行消去操作后的矩阵状态为状态（h）所示。该矩阵中除了第0列以外
每列都只有一个元素非0，由此就可推断出A、B、C、D、E、F到底是哪国
人。
4．确定程序框架
总结上述矩阵状态的变化过程，可得出程序执行的简要流程，如图6.9所
示。 

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

#!/usr/bin/python3
# -*- coding: ?TF-8 -*-
#author:liuhefei
#desc: 旅客国籍
country = [" ", "美国", "英国", "法国", "德国", "意大利", "俄罗斯"] #国名
def Nationality():
#初始化条件矩阵
a = []
for i in range(7):
b = []
for j in range(7):
b.append(j)
a.append(b)
for i in range(1, 7): #条件矩阵每一列的第0号元素作为该列数据处理的标记
a[0][i] = 1 #标记该列尚未处理
a[1][1] = a[2][1] = a[3][1] = a[5][1] = 0 #输入条件矩阵中的各种条件
a[1][3] = a[2][3] = a[3][3] = 0 #0表示不是该国人
a[1][4] = a[2][4] = a[3][4] = a[5][4] = a[6][4] = 0
a[3][5] = 0
a[1][6] = a[3][6] = a[5][6] = 0
x = 0
y = 0
while a[0][1] + a[0][2] + a[0][3] + a[0][4] + a[0][5] + a[0][6] > 0:
#当所有6列均处理完毕后退出循环
for i in range(1, 7): #i为列坐标
if a[0][i] != 0: #若该列尚未处理，则进行处理
e = 0
for j in range(1, 7): #j变量保存行坐标，e变量是该列中非0元素的计数器
if a[j][i] != 0:
#统计每列中的非0元素个数
x = j #x变量保存行坐标
y = i #y变量保存列坐标
e += 1
if e == 1: #若该列只有一个元素为非零，则进行消去操作
for t in range(1, 7):
if t != i:
a[x][t] = 0 #将非零元素所在行的其他元素置0
a[0][y] = 0 #设置该列已处理完毕的标记
print("矩阵最终状态为：")
#输出执行消去操作后矩阵的最终状态
for i in range(7):
print(a[i])
print("推断结果为：")
for i in range(1, 7):
print(chr(ord('A') - 1 + i), '来自: ', end='')
for j in range(1, 7):
if a[i][j] != 0:
print(country[a[i][j]], '。')
break
if __name__ == '__main__':
Nationality()

 6．运行结果
在PyCharm下运行程序，结果如图6.10所示。根据运行结果可知：A是意
大利人，B是俄罗斯人，C是英国人，D是德国人，E是法国人，F是美国人。

 7．拓展训练
根据题意生成条件矩阵，再使用消去法进行推理判断是一种常用的方
法，该方法对于解决较为复杂的逻辑问题是十分有效的，希望读者能够掌
握。