学好顶级算法谜题，不再为了编程而编程

谜题趣味非凡。顶级谜题的解可没那么浅显易得，需要灵光一闪才能发现。算法谜题是指谜题的解法就是算法，解题的步骤可以被机器自动执行。算法可以用英文或者其他任何自然语言来描述，但是为了更加精确，往往会用伪代码进行描述。之所以称为“伪代码”，是因为它尚未细化到足以在计算机上运行的程度，与用编程语言编写的代码不大一样。

当今世界有越来越多的人以计算机编程为业。为了学习编程，我们首先要通过简单的例子学习基本的编程结构，例如赋值语句和控制循环之类，而编程习题往往涉及将算法的伪代码转译为用所学编程语言编写的代码。程序员同样能从求解谜题所需的分析技能中获益。无论是将规格说明转换为编程结构，还是定位早期代码中的错误（也就是调试过程），这些分析技能都不可或缺。

谜题（puzzle）就是一种最棒的实际应用，它的优势在于易于描述和引人注目。后者如今尤为重要。让我们看一下今天推荐的这本算法书。

编程的乐趣：用 Python 解算法谜题

本书创新地通过求解有趣的谜题来教授读者编程，为枯燥的编程学习过程注入了很强的趣味性，谜题是来自真实世界的应用，饶有趣味、易于描述。

学习编程是从解谜题开始的，在经历一两次失败的解谜尝试后，读者会豁然开朗——可能是一种搜索策略、一个数据结构或一个数学公式，谜题的算法就跃然而出了，剩下的事情就是用Python语法和语义将算法“翻译”成可实现的代码。

读者只需掌握初级的编程概念，就可以阅读本书。本书包含了21 个谜题，其中很多谜题都家喻户晓并广为流传，如多皇后、汉诺塔、在几秒钟内解决数独问题、六度分隔等。每个谜题后面都配有不同难度的编程习题，读者可以先自行完成编码，再对照本书给出的答案进行探索和提升。

书中有哪些顶级算法谜题：

• 谜题1保持一致
• 谜题2参加派对的最佳时间
• 谜题3拥有（需要一点校准的）读心术
• 谜题4让皇后保持分离
• 谜题5请打碎水晶
• 谜题6寻找假币
• 谜题7跳到平方根
• 谜题8猜猜谁不来吃晚餐
• 谜题9美国达人秀
• 谜题10多皇后
• 谜题11请满铺庭院
• 谜题12汉诺塔
• 谜题13没条理的工匠
• 谜题14再也不玩数独了
• 谜题14再也不玩数独了
• 谜题15统计零钱的组合方式
• 谜题16贪心是好事
• 谜题17字母也疯狂
• 谜题18充分利用记忆
• 谜题19要记得周末
• 谜题20六度分隔
• 谜题21问题有价

样章试读：谜题9美国达人秀

本谜题涵盖的编程结构与算法范型：通过列表表示二维表格。

你决定举办一档叫作“谁是达人”的电视节目

，春季假期后有很多选手报名，而你将主持节目的海选。每位选手都有自己的绝活（如插花、跳舞、滑板等），而你在海选中检验他们的表现。多数选手的表现都不能令你满意，但是有一部分选手能做到。现在你有一组选手，他们会每人向你表演至少一项绝活。

在你的节目中，你希望能突出表现多种多样的绝活。如果每周全都是各种插花表演，对收视率是没有帮助的。你拿出选手列表，整理出他们的绝活列表。然后你去找制作人，让他答应在节目中覆盖这些绝活。你的制作人会削减这张列表（例如，他们认为观众不喜欢重复的节目），交由你选出最终的列表。他们也告诉你，要控制成本。

你明白最好的控制成本、提高收视率的方法是联系尽量少的选手，同时提供尽量多的节目种类。因此你想在最终的列表中选出最少的选手，而他们能演出所有的绝活。

假设你最后选出了表9-1所示的选手与绝活。

表9-1

在上面的例子中，你可以选择Aly、Bob、Don和Eve，从而覆盖所有绝活。Aly会柔术和代码，Bob会跳舞和魔术，Don会跳舞和唱歌，Eve会跳舞、动作和代码。他们总共有6种绝活。

你能用尽量少的人覆盖所有的绝活吗？更一般地说，你怎样选择最少的选手（行），做到能够覆盖表格中所有的绝活（列）？表9-2中展示另一个例子。

表9-2

在我们第一个例子中，你选择的选手数量可以少于4位。你只需要聘请Aly、Cal和Eve即可。Aly会柔术和代码，Cal会唱歌和魔术，Eve会跳舞、动作和代码。他们总共有6种绝活。

我们会使用晚餐邀请谜题（谜题8）中同样的策略。这两个问题很相似，不过在晚餐邀请谜题里，我们想邀请最多数量的人，而在这里我们想选择最少数量的人。而它们的共性在于，我们需要检查所有可能的组合（如选手的子集），排除不能覆盖所有绝活的子集，然后选择最小的子集。它们的另一个共性是贪心策略不可用。

两道谜题使用的数据结构是不同的，这里我们需要一张表示选手与绝活之间关系的表格，而非一张不喜欢的关系图。我们的例子可以转化为类似这样的数据结构：

Talents = ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code']
Candidates = ['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay']
CandidateTalents = [['Flex', 'Code'], ['Dance', 'Magic'],
                    ['Sing', 'Magic'], ['Sing', 'Dance'],
                    ['Dance', 'Act', 'Code'], ['Act', 'Code']]

我们有一个绝活列表（表格的列）和一个选手列表（表格的行）。我们需要一个列表的列表 CandidateTalents ，用于表示表格中的条目。 CandidateTalents 中的条目对应表格的行，而条目的顺序很重要，因为它对应选手在列表 Candidates 中的顺序。Bob是 Candidates 中的第二位选手，他的绝活对应 CandidateTalents 中的第二个列表，也就是 ['Dance', 'Magic'] 。

你可能会猜，两道谜题的代码会非常相似。我们会基于优化版的谜题8，为这道谜题稍微不同地组织代码。

9.1每次生成并测试一个组合

这是顶层过程的代码，会每次生成一个组合，检查是否正确，取最小数量的正确组合。

 1.     Hire4Show(candList, candTalents, talentList):
 2.        n =(candList)
 3.        hire = candList[:]
 4.         i (2**n):
 5.            Combination = []
 6.            num = i
 7.             j(n):
 8.                 (num % 2 == 1):
 9.                    Combination = [candList[n-1-j]] + Combination
10．                num = num // 2
11．            Good(Combination, candList, candTalents, talentList):
12．                (hire) > (Combination):
13．                    hire = Combination
14．        ('Optimum Solution:', hire)

第4～10行生成值 num = i 对应的组合。第11行调用函数 Good ——这会在后面详述——用于检查给定的选手组合是否覆盖所有绝活。如果是，则与当前已知最优的选手组合比较，如果选手人数少于最优组合，则更新最优组合（第12～13行）。

第3行与谜题8的对应行的 invite = [] 不同。在谜题8中，我们希望最大化能邀请的客人数量，因此将一个空列表作为最初的最优组合。在这里，我们想最小化聘请的选手数量，因此将完整的选手列表作为最初的最优组合。我们假定完整的选手组合能够满足覆盖所有绝活的要求。如果不能满足，可以重新考量绝活的列表。

9.2确定缺少一门绝活的组合

我们调用函数 Hire4Show 来确定一个给定的选手组合是否包含所有绝活。我们要做的这项检查与谜题8有很大不同，这一点会在下面展示。

 1.     Good(Comb, candList, candTalents, AllTalents):
 2.         tal  AllTalents: 
 3.            cover = 
 4.             cand Comb: 
 5.                candTal = candTalents[candList.index(cand)]
 6.                 tal  candTal: 
 7.                    cover = 
 8.             cover: 
 9.                
10．        

for

循环（第2～9行）对绝活列表遍历每项绝活 tal 。对组合中的每位选手（第4行开始的内层 for

循环），我们使用选手在选手列表 candList 中的索引，作为“选手-绝活”数据结构的索引（第5行）。

我们现在需要在 for

循环的迭代中（第2行开始）检查选手的绝活中是否覆盖绝活 tal ，这项检查在第6行完成。如果选手拥有绝活 tal ，我们在第7行做标记。不过，如果遍历完内层 for

循环没有找到当前选手组合中有覆盖绝活 tal 的选手，我们便得知这个选手组合需要被抛弃——缺少一项绝活，便不能视为正确的组合。因此我们能省却检查其他绝活，直接返回 False

即可（第9行）。

如果我们检查了所有的绝活且在所有的迭代中都没有返回 False

，意味着该组合覆盖了所有的绝活，可以返回 True

（第10行）。

我们对开始的例子运行以下这段代码。例子中的表格转化为代码是：

Talents = ['Sing', 'Dance', 'Magic', 'Act', 'Flex', 'Code']
Candidates = ['Aly', 'Bob', 'Cal', 'Don', 'Eve', 'Fay']
CandidateTalents = [['Flex', 'Code'], ['Dance', 'Magic'],
                    ['Sing', 'Magic'], ['Sing', 'Dance'],
                    ['Dance', 'Act', 'Code'], ['Act', 'Code']]

如果我们运行

Hire4Show(Candidates, CandidateTalents, Talents)

产生输出

Optimum Solution: ['Aly', 'Cal', 'Eve']

与我们期望的完全一致。

如果对第二个稍大的例子运行代码

ShowTalent2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
CandidateList2 = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
CandToTalents2 = [[4, 5, 7], [1, 2, 8], [2, 4, 6, 9],
                  [3, 6, 9], [2, 3, 9], [7, 8, 9],
                  [1, 3, 7]]
Hire4Show(CandidateList2, CandToTalents2, ShowTalent2)

会产生输出

Optimum Solution: ['A', 'B', 'D']

9.3应用

这道谜题是集合覆盖问题（set-covering problem）的一个实例，而集合覆盖问题有很多应用场景。例如，汽车公司可能希望在能得到所有汽车配件供应的前提下，与最少汽车配件供应商合作，减少公司需要做的审查数量。NASA也希望在确保执行所有维护工作的前提下，最小化发射到太空的 工具 集合的总重量。

集合覆盖是一个难题：包括我们编写的算法在内的所有已知算法，对所有问题实例都要保证选中集合的基数最小，对某些实例可能需要耗费选手数量的指数时间。在这种意义上，集合覆盖问题与晚餐邀请谜题（谜题8）是等价的。

如果对绝对的最小基数不感兴趣，我们可以使用一种贪心法来解决问题。它可以做到快速，因为它只需要对表格做少量扫描或者遍历。适用本谜题的贪心算法会首先选出拥有最多绝活的选手，一旦该选手被选出，该选手覆盖的所有绝活都从表格中移除。这一过程持续至覆盖到所有绝活为止。

对于我们第二个稍大的例子，选手 A

到 G

中，我们会首先选出 C

，他覆盖4项绝活：2、4、6和9。变小的表格如表9-3所示。

表9-3

这里选手 G

覆盖3个（额外的）绝活。 G

会中选，因为其他选手都只覆盖两个绝活。选出 C

和 G

后，得到表9-4所示的表格。

表9-4

我们仍需要覆盖绝活5，这需要选手 A

；也需要绝活8，这需要选手 B

或 F

。总共4位选手。我们知道这并非最优解，前面的代码已经给出了3位选手的结果。

9.4习题

习题1

在第一个例子中，Eve会“完胜”Fay，因为她会Fay会的所有绝活，而且会得更多。修改代码，将被完胜的选手移出表格，这能使组合的生成更加高效。

习题2

在我们的第一个例子里，Aly一定会被选出，因为她是唯一会柔术的选手。在表格中可以看得一清二楚，因为柔术一列只有一个标记。类似地，在我们第二个例子中， D

是覆盖绝活4的唯一选手，而 F

是覆盖绝活7的唯一选手。

修改原始代码，做到：（1）识别出拥有独一无二绝活的选手；（2）削减表格，移除这些选手的所有相关绝活；（3）基于削减后的表格找出最优的选择；（4）加入步骤1中发现的选手。

难题3

你认为一部分选手眼里只有自己，要的薪水比应当得到的多。因此你需要一个方法，来选出接受你给的薪水的选手。你为每位选手赋予一个权重，表示你认为的他们各自的价码。修改代码允许它找出一组选手，像之前一样能覆盖所有绝活，但是最小化价码的权重。

假设给出：

ShowTalentW = [1, 2, 3, 4, 5, 6, 7, 8, 9]
CandidateListW = [('A', 3), ('B', 2), ('C', 1), ('D', 4),
                  ('E', 5), ('F', 2), ('G', 7)]
CandToTalentsW = [[1, 5], [1, 2, 8], [2, 3, 6, 9],
                  [4, 6, 8], [2, 3, 9], [7, 8, 9],
                  [1, 3, 5]]

其中 CandidateListW 中二元组的数字对应每位选手有多贵。你的代码意在最小化开销，应当产生：

Optimum Solution: [('A', 3), ('C', 1), ('D', 4), ('F', 2)]
Weight is: 10

注意，如果Eve 比Fay贵得多，那么这里“完胜”的优化不再可行！只有当Eve与Fay的权重相同或者更小时，这一优化才能成立。所以如果你在使用习题1中的代码，要小心这一点。

习题4

还记得习题2中面向独一无二选手的优化吗？将它加入习题3用于选择最小权重选手集合的代码中。