欢迎关注异步社区头条号，程序员的思想汇 IT学习的集散地
本谜题涵盖的程序结构和算法范型：读取来自用户的输入，用于条件分析的控制流程，以及信息编码与解码。
你是一位魔术师，拥有读心术这种超能力。你的助手走向观众，取出一套普通的52张扑克牌，而你在房间外，看不到里面的任何东西。5位观众每人从中抽取一张扑克牌，助手收起这5张牌，向所有观众依次展示其中的4张。在展示这4张牌中的每张牌时，助手会要求观众集中精神在这张牌上，而你则望向别处，尽量感应所有观众集体的意念。几秒后，这几张牌会展示给你，这有助于校准你对这些观众的读心的能力。
看到这4张牌后，你宣布已经面向这些观众校准了自己的读心能力，随即离开房间。助手向观众展示出第5张牌后，把牌收了起来。同样，观众集中精神在这第5张牌上。你回到房间，聚精会神片刻，正确地指出秘密的第5张牌。
你与助手同谋合计并排练了这套把戏。然而，每个人都在密切关注这一切，助手给你的唯一信息只有这4张牌。
这套把戏是怎样得逞的？
原来，助手通过展示扑克牌的顺序，向魔术师传达了第5张牌是什么。助手需要选出需要隐藏的扑克牌——他/她不能允许观众从抽取的5张牌中选择隐藏牌。这是助手与魔术师之间的一种合作方式。
举一个实用的例子，假设观众选择了红心♥10、方块♦9、红心♥3、黑桃♠Q、方块♦J这5张牌。
图3-1
现在有了一套读心算法，我们准备写两段程序，对应助手与魔术师的工作任务。
第一段程序取助手的5张牌作为输入，选出待隐藏的牌，编码剩余的4张牌，并按正确的顺序打印。助手可以向做魔术师的你读出这4张牌，让你猜出隐藏牌。
1. deck = ['A_C','A_D','A_H','A_S','2_C','2_D','2_H','2_S',
'3_C','3_D','3_H','3_S','4_C','4_D','4_H','4_S',
'5_C','5_D','5_H','5_S','6_C','6_D','6_H','6_S',
'7_C','7_D','7_H','7_S','8_C','8_D','8_H','8_S',
'9_C','9_D','9_H','9_S','10_C','10_D','10_H',
'10_S','J_C','J_D','J_H','J_S','Q_C','Q_D',
'Q_H','Q_S', 'K_C','K_D','K_H','K_S']
2. def AssistantOrdersCards():
3. print ('Cards are character strings as shown below.')
4. print ('Ordering is:', deck)
5. cards, cind, cardsuits, cnumbers = [], [], [], []
6. numsuits = [0, 0, 0, 0]
7. for i in range(5):
8. print ('Please give card', i+1, end = ' ')
9. card = input('in above format:')
10． cards.append(card)
11． n = deck.index(card)
12． cind.append(n)
13． cardsuits.append(n % 4)
14． cnumbers.append(n // 4)
15． numsuits[n % 4] += 1
16． if numsuits[n % 4] > 1:
17． pairsuit = n % 4
18． cardh = []
19． for i in range(5):
20． if cardsuits[i] == pairsuit:
21． cardh.append(i)
22． hidden, other, encode = \
22a. outputFirstCard(cnumbers, cardh, cards)
23． remindices = []
24． for i in range(5):
25． if i != hidden and i != other:
26． remindices.append(cind[i])
27． sortList(remindices)
28． outputNext3Cards(encode, remindices)
29． return
第1行的列表deck定义牌从小到大的数值顺序。第5行与第6行初始化了一些变量。在第5行里，你可以看到一个单条语句赋值多个变量的例子。第7～17行是一个for循环，从键盘读取5张牌的输入。输入的牌名必须与deck列表中声明的字符格式一致。
第8行是一条print语句，打印'Please give card'与扑克牌号。print语句中的end = ' '表示打印空格替代换行符。第9行打印'in above format:'，读取用户的字符输入并写入变量card，随后追加到列表cards中。这两行代码在一起产生的输出会像是这样：
Please give card 1 in above format:
随后等待用户输入字符串。第11 行是至关重要的一行，取扑克牌对应的字符串，确定它在列表deck中的数值索引。这一索引很重要，因为它决定了怎样比较两张牌的顺序。例如，'A_C'的索引为0，'3_C'的索引为8，'K_S'的索引为51。
第12～17行填充了多个数据结构，用于助理的编码任务。将5张牌的索引保存于cind，同时将5张牌的花色保存于cardsuits。将牌的索引对4取模，便可以得到牌的花色。梅花牌（花色0）的索引都是4的倍数，而方块牌（花色1）的索引都是4的倍数加1，依此类推。要取到牌的“数字”，即A（1）到K（13），将下标直接整除（//）4即可得到，因为所有A位于每副牌的开始位置，然后是2，依此类推。我们的算法要助手选择出5张牌中出现过多于一次的花色——至少存在一种这样的花色，但是如果存在两种出现两次的花色，我们按照输入的顺序选择其中之一，将花色号保存于pairsuit变量（第15～17行）。
第18～21行确定pairsuit值相等的两张牌。可能同样花色的牌有3张甚至更多，但是我们在过程outputFirstCard中只选用前两张牌。
过程outputFirstCard（第22行与第22a行）确定两张牌中的哪张作为隐藏牌，乃至哪张牌作为展示给魔术师的第一张牌。它也确定了要通过剩余3张牌编码的具体数值。注意第22行末尾的\符号，它的意思是第22行与22a行可以一起视为同一条语句。如果在这里不使用\符号，那么Python会崩溃。我们会在后面更详细地讲解oututFirstCard的细节。
第23～26行从5张牌中移除隐藏牌与第一张牌，并保存剩余的索引到长度为3的列表remindices中。按索引值的升序对remindices做排序（第27行）。最后，过程outputNext3Cards对保存于变量encode的编码数值，按编码规则对3张牌排序。这个过程也会在后面进行详细讲解。
第29行有一个return语句，表示过程的结束。到目前为止我们的过程都有点随意，还没有使用过return语句。第29行并不是必需的，过程没有它也同样能正常工作。如果你需要返回一个值，也就是需要实现一个函数，那么就必须用到return语句了。这一点在我们后文中函数与前面谜题中的函数的代码中都有体现。
这里是函数outputFirstCard，用于确定两张牌中的哪张作为隐藏牌。我们要编码一个1到6的数值，并恰当地选出这两张牌。函数会分别返回隐藏牌、第一张展示的牌以及要编码的数值。
1. def outputFirstCard(ns, oneTwo, cards):
2. encode = (ns[oneTwo[0]] - ns[oneTwo[1]]) % 13
3. if encode > 0 and encode <= 6:
4. hidden = oneTwo[0]
5. other = oneTwo[1]
6. else:
7. hidden = oneTwo[1]
8. other = oneTwo[0]
9. encode = (ns[oneTwo[1]] - ns[oneTwo[0]]) % 13
10． print ('First card is:', cards[other])
11． return hidden, other, encode
在这里不用担心两张牌的花色，因为是相同的。我们重新使用刚才展示过的这个牌的圆环（如图3-2所示）来讲解这段代码。
图3-2
假设第一张牌是红心♥10，第二张牌是红心♥3。那么，第二行会计算(10 − 3) % 13 = 7。既然encode = 7，那么我们选择隐藏第二张牌红心♥3，并编码数值(3 - 10) % 13 = 6。顺时针方向上，从10（第一张展示的牌）开始递增6步，可得3（隐藏牌）。另一方面，如果第一张牌是红心♥3，第二张牌是红心♥10，第二行会计算出(3 − 10) % 13 = 6。同样，也会选出红心♥3做隐藏牌，对6做编码。
下面是过程outputNext3Cards，它会对参数中的列表ind所保存的其余3张牌做排序，来对参数code给出的数值编码。
1. def outputNext3Cards(code, ind):
2. if code == 1:
3. s, t, f = ind[0], ind[1], ind[2]
4. elif code == 2:
5. s, t, f = ind[0], ind[2], ind[1]
6. elif code == 3:
7. s, t, f = ind[1], ind[0], ind[2]
8. elif code == 4:
9. s, t, f = ind[1], ind[2], ind[0]
10． elif code == 5:
11． s, t, f = ind[2], ind[0], ind[1]
12． else:
13． s, t, f = ind[2], ind[1], ind[0]
14． print ('Second card is:', deck[s])
15． print ('Third card is:', deck[t])
16． print ('Fourth card is:', deck[f])
这个过程假设 ind[0] < ind[1] < ind[2]，然后改变纸牌的顺序对 code进行编码。
最后是排序过程：
1. def sortList2(tlist):
2. for ind in range(0, len(tlist) - 1):
3. iSm = ind
4. for i in range(ind, len(tlist)):
5. if tlist[iSm] > tlist[i]:
6. iSm = i
7. tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]
排序过程与谜题2中的排序代码几乎完全相同。唯一的区别在于第5行，元素中的值是可比较的牌号，因此可以直接比较两个元素（而不是像谜题2那样比较两个元组）。
现在我们已经实现了助手编码任务的自动化，接下来切换到魔术师的任务上。
这是一个解码程序，取4张假设正确编码的牌，打印出“隐藏”牌号。当你太忙没时间排练时，助手也可以使用这个工具自己排练。助手可以在一副扑克牌中随机选出5张牌，隐藏一张牌，对其他牌排序并输入到这个程序中。这个程序会生成隐藏牌，助手可以检查是否正确地按顺序输入了牌。
1. def MagicianGuessesCard():
2. print ('Cards are character strings as shown below.')
3. print ('Ordering is:', deck)
4. cards, cind = [], []
5. for i in range(4):
6. print ('Please give card', i + 1, end = ' ')
7. card = input('in above format:')
8. cards.append(card)
9. n = deck.index(card)
10． cind.append(n)
11． if i == 0:
12． suit = n % 4
13． number = n // 4
14． if cind[1] < cind[2] and cind[1] < cind[3]:
15． if cind[2] < cind[3]:
16． encode = 1
17． else:
18． encode = 2
19． elif ((cind[1] < cind[2] and cind[1] > cind[3])
20． or (cind[1] > cind[2] and cind[1] < cind[3])):
21． if cind[2] < cind[3]:
22． encode = 3
23． else:
24． encode = 4
25． elif cind[1] > cind[2] and cind[1] > cind[3]:
26． if cind[2] < cind[3]:
27． encode = 5
28． else:
29． encode = 6
30． hiddennumber = (number + encode) % 13
31． index = hiddennumber * 4 + suit
32． print ('Hidden card is:', deck[index])
到第10行之前，两个程序几乎完全相同，不同的是在第5行我们只输入4个牌号，而不是5个。第11～13行确定隐藏牌的花色与第一张牌的数字（1～13）。程序的其余部分便是根据第二、三、四张牌的数值排序，确定出第一张牌与隐藏牌之间的距离差。第14行与第15行检查这3张牌是否为递增顺序，如果是，那么encode表示的距离差等于1。如果第一张牌是3张牌中最小的牌（完整的4张牌中的第二张牌），而其余两张牌为降序，则encode等于2。
第19～20行检查3张牌中的第一张牌的数值是否为中间大小。如果成立，encode表示的距离差会是3或者4。注意第19行和第20行对应同一条语句，Python中可以使用括号来表示语句的连续。我们在elif后面增加了一个额外的“(”，同时在第20行通过匹配的“)”结束这行elif语句。如果使用“\”的话，这对额外的括号就没有必要了。如果移除括号，且没有使用“\”，会报出一条语法错误。
第30行与第31行确定隐藏牌是哪张。我们已知它的花色，利用第一张牌的牌号与encode表示的距离差就可以确定隐藏牌的牌号。不过如果要确定牌的字符串表示，还需要确定隐藏牌在列表deck中的索引。
如果作为魔术师的你没有排练的伙伴怎么办？这段代码会有一些帮助：
1. def ComputerAssistant():
2. print ('Cards are character strings as shown below.')
3. print ('Ordering is:', deck)
4. cards, cind, cardsuits, cnumbers = [], [], [], []
5. numsuits = [0, 0, 0, 0]
6. number = int(input('Please give random number of' +
' at least 6 digits:'))
7. for i in range(5):
8. number = number * (i + 1) // (i + 2)
9. n = number % 52
10． cards.append(deck[n])
11． cind.append(n)
12． cardsuits.append(n % 4)
13． cnumbers.append(n // 4)
14． numsuits[n % 4] += 1
15． if numsuits[n % 4] > 1:
16． pairsuit = n % 4
17． cardh = []
18． for i in range(5):
19． if cardsuits[i] == pairsuit:
20． cardh.append(i)
21． hidden, other, encode = \
21a. outputFirstCard(cnumbers, cardh, cards)
22． remindices = []
23． for i in range(5):
24． if i != hidden and i != other:
25． remindices.append(cind[i])
26． sortList(remindices)
27． outputNext3Cards(encode, remindices)
28． guess = input('What is the hidden card?')
29． if guess == cards[hidden]:
30． print ('You are a Mind Reader Extraordinaire!')
31． else:
32． print ('Sorry, not impressed!')
这段程序根据输入的6位数字“随机”生成5张牌。输入的这6位数字会被打散，生成5张牌，使之难以根据输入的数字猜出对应的结果。你可以将这个数字视为随机性的种子。这段程序的工作内容与原先相同——“隐藏”一张牌，并按正确的顺序打印出剩余的4张牌。随后，它读取魔术师的猜测结果，返回魔术师的猜测是否正确。这样一来，想掌握这套戏法的年轻魔术师可以独自排练。每次正常排练时，输入一个不同的6位或更多位的数字。
第6～9行是相对于AssistantOrdersCards的主要修改。注意，第6行语句跨了两行，与前面的print语句相似。input只取一个参数，我们需要在两个字符串中间加入一个“+”。
魔术师输入一个大数字，保存在变量number中。我们想基于number生成总共5个“随机”的索引。我们在第8行使用了一些算术式，基于number来生成“随机”数字。我们完全可以使用Python内置的随机数生成器，但是我们在这里只要做到防止魔术师轻易从number得出隐藏牌就可以，使魔术师只能通过4张展示出的牌来解码出隐藏牌。我们假设魔术师有动力诚实地排练！
第28～32行读取魔术师的猜测作为输入，确定猜测结果是否正确。
这道题目考察了信息的编码与通信方面的问题。假设你在附近有外人能旁听到声音的环境中，想与朋友秘密通信。你想告诉朋友一点信息，告诉他你是否有空参加今天的晚宴。如果你通过“Hey, buddey Alex”来打招呼而不是通过“Hey, Alex buddy”来打招呼，则如果之前有商定的码号，Alex便能够得知你是否有空。例如，“buddy”在“Alex”之前表示“没空”，反过来表示“有空”。
在这套扑克牌戏法中，我们基于3张牌有6种排列方式，所以能传递一个1到6之间的数值。一般而言，如果我们有n张牌，它们可以有n!种排列方式，其中n!读作“n的阶乘”，等于n乘以n − 1乘以n − 2直到乘以1为止。这意味着发送者与接收者在商定排列顺序对应的数值信息之后，我们可以通过一个具体的排列方式，传递一个1到n!之间的数值。即使侦听者知道里面可能在传递秘密信息，只要侦听者不清楚排列方式与数值之间的对应关系，侦听者就无法从传输的排列中得出数值的信息。
这意味着，你和你的助手完全可以商定展示牌的不同顺序，或者商定一个不同的全局牌号排序（见下面的习题3），这样一来即使观众了解戏法的原理，也不能正确猜出隐藏牌。如果有人想要在你之前喊出隐藏牌来干扰这套扑克牌戏法，助手可以展示出真正的隐藏牌，使质疑者很大可能看到与他们猜测的结果不同而感到尴尬。需要注意的是，这套戏法如果正确地重复过多次数，精明的观众将有可能发现背后商定的顺序。
你能想出一套类似的、只有4张牌的戏法吗？就是说，助手找4位观众上台，每人随机抽取一张牌，隐藏其中一张牌，通过某种方式宣示其余的3张牌，将隐藏牌传达给魔术师。同之前一样，助手会选择出要隐藏哪张牌。
这看起来很难，与5张牌的谜题不同，4张牌的花色有可能完全不同。这意味着助手除了隐藏牌的牌号，还需要传达隐藏牌的花色，仅通过3张牌来完成这一切。
助手传递信息的方法有很多。助手可以在按某种顺序宣布牌的同时，悄悄把牌按正面或反面放置在桌上。有意思的问题是，在允许助手自由选择隐藏牌的条件下，需要传递的信息量是多少？
考虑图3-3所示的更大的这个牌环，与前面包含13张牌的环相似，但是包含了完整的一套52张牌。它的展示顺序与变量deck中保存的顺序相同。4张牌会随机地分布在这个环的不同位置上。
图3-3
任意两张牌在最坏情况下的最短距离是多少？在最坏情况下，牌会均匀散布，如梅花♣Q、方块♦2、红心♥5和黑桃♠8。这种情况下相邻的每一对牌都相距13跳。这意味着，不管选择哪些牌，助手总可以选择最多相距13跳的一对牌。与5张牌的戏法类似，最先展示的牌将能够在顺时针方向13跳以内抵达隐藏牌。
想象一下，助手怎样才能最巧妙地向魔术师传递一个1到13之间的数值？一个方法是，将隐藏牌放到桌面，当然让它正面朝下，然后将其他3张牌分别放置在隐藏牌的左侧或者右侧。每张牌的左或右，都为魔术师增加了一位的信息量。然后，令所有3张展示的牌都正面朝上放置或者都正面朝下放置，又能增加一位的信息量。一共4比特，足够编码一个0到15之间的数值。与大部分戏法一样，分散观众的注意力是戏法的重要部分！
习题1 ComputerAssitant程序中有一个小bug，源自这段代码的偷懒：
7． for i in range(5):
8． number = number * (i + 1) // (i + 2)
9． n = number % 52
我们基于输入的数字来生成5张“随机”牌。这个策略存在的问题是，它并没有检查确保这5张牌各不相同。实际上，如果你输入的数字是888888，会生成这样排列的5张牌：['A_C', 'A_C', '7_H', 'J_D', 'K_S']。你可以发现问题所在：我们没有在ComputerAssistant中查重复的牌。修正这个过程，检查牌是否不同，并执行上面的循环生成“随机”数值，迭代直到生成5张不同的牌为止。
习题2 修改ComputerAssistant，以防存在两对同花色的牌，则在选择隐藏牌与第一张牌时，选择其中需要编码的数值更小的一对牌。
习题3 一些魔术师更喜欢按不同的方式对牌排序，将花色置为首要排序因子，而不是按数值排序，如下：
deck = ['A_C','2_C','3_C','4_C','5_C','6_C','7_C','8_C',
'9_C','10_C','J_C','Q_C','K_C','A_D','2_D','3_D',
'4_D','5_D','6_D','7_D','8_D','9_D','10_D','J_D',
'Q_D','K_D','A_H','2_H','3_H','4_H','5_H','6_H',
'7_H','8_H','9_H','10_H','J_H','Q_H','K_H','A_S',
'2_S','3_S','4_S','5_S','6_S','7_S','8_S','9_S',
'10_S','J_S','Q_S','K_S']
修改ComputerAssitant允许魔术师按如上的顺序进行排练。注意，按索引提取牌的牌号与花色的计算逻辑需要修改。同样，助手读牌的顺序也需要修改。需要正确处理一些细节，才能正确解出这道谜题的变体。
难题4 编写ComputerAssistant4Cards，允许排练这套4张牌的戏法。你可以选择上文描述的编码策略，利用这样的手段提供信息：（1）每张牌放置于桌面上的隐藏牌的左侧还是右侧；（2）所有3张牌是全部正面朝上还是正面朝下。你也可以设计自己的编码策略，确保对任意抽取的4张牌都能操作这套戏法。
[1] 擅长数学的读者可以认出这是鸽洞原理：给出n个洞和n+1只鸽子，每只鸽子需飞过几个洞，至少有一个洞会有两只鸽子飞过。
这是一本介绍通过解决复杂谜题来学习编程的书，书中的代码用Python语言编写。与以往的编程书不同，本书将对代码功能的理解与编程语言语法和语义的理解分离开来，从解每个谜题开始，先给出解谜题的算法，随后用Python语法和语义实现对应的算法，并适当做出解释。本书包含了21个谜题，其中很多谜题都广为流传，如多皇后、汉诺塔、在几秒钟内解决数独问题、验证六度分隔猜想等，每个谜题后面都配有不同难度的编程习题，帮读者加深对相关算法的理解。
本书在算法谜题的趣味性和计算机编程的实用性之间搭建了一座桥梁，内容饶有趣味，讲述易于理解，适合已掌握初级编程概念并对算法感兴趣的学习者阅读和参考。
如果你想获取更多的IT学习知识
请关注异步社区头条号
我们会持续为您提供更多的优质内容
| 留言与评论（共有 0 条评论） |
