算法谜题
出版社:人民邮电出版社
出版日期:2014-1-1
ISBN:9787115338440
作者:Anany Levitin,Maria Levitin
页数:300页
内容概要
作者简介
Anany Levitin，美国Villanova大学计算科学教授。他是一本算法设计和分析名著的作者，该书被译为中文、希腊文等多国语言。他还在数学最优化算法、软件工程、数据管理、算法设计和计算机科学教育等领域发表过多篇论文。
Maria Levitin，独立咨询师。她在大型软件公司有多年的商业应用软件开发经验，现在她专注于Web应用和无线计算领域。
译者简介
赵勇，电子科技大学教授，极限网络计算与服务实验室主任，中国计算机学会大数据专家委员会委员。美国芝加哥大学博士，师从世界网格之父Ian Foster教授，其间在美国IBM研发中心、美国Argonne国家实验室实习。博士毕业后任职美国微软公司搜索与广告部，从事云平台上的大型广告系统开发，获微软杰出员工奖。
徐章宁，1984年生，毕业于上海交通大学。在EMC中国卓越研发集团任高级系统管理工程师，钟爱开源软件，从事软件运维工作多年。对各类知识有广泛兴趣，平日喜爱参与问答网站讨论，热爱读书摄影和写作。
高博，1983年生，毕业于上海交通大学。目前在EMC中国卓越研发集团任首席工程师，在信息科学和工程领域有近15年实践和研究经验。酷爱读书和写作，业余研究兴趣涉猎广泛。译著包括图灵奖作者高德纳的《研究之美》和布鲁克斯的《设计原本》，以及Jolt大奖作品《基元设计模式》等。近年来，出版翻译作品近百万字。
书籍目录
第1章 概览
1
1.1 算法设计的若干通用策略
1
1.1.1 穷举搜索
2
1.1.2 回溯法
3
1.1.3 减而治之
6
1.1.4 分而治之
7
1.1.5 变而治之
8
1.1.6 贪心法
14
1.1.7 迭代改进
15
1.1.8 动态规划
18
1.2 分析技术
19
1.2.1 几个求和公式，兼论算法效率
20
1.2.2 非递归算法分析
21
1.2.3 递归算法分析
23
1.2.4 不变量
25
第2章 谜题
29
2.1 简单谜题
29
2.2 中等难度谜题
41
2.3 较难谜题
55
第3章 提示
67
第4章 答案
78
算法谜题列表
第1章 概览
1
第2章 谜题
29
1．狼羊菜过河
29
2．手套选择
29
3．矩形切割
29
4．士兵摆渡
29
5．行列变换
30
6．数数的手指
30
7．夜过吊桥
30
8．拼图问题
30
9．心算求和
30
10．硬币中的假币
31
11．假币堆问题
31
12．平铺多米诺问题
31
13．被堵塞的路径
31
14．复原国际象棋棋盘
31
15．三格骨牌平铺问题
32
16．煎饼制作
32
17．国王的走位
32
18．骑士的征途
32
19．页码计数
32
20．寻找最大和
33
21．正方形的拆分
33
22．球队排名
33
23．波兰国旗问题
33
24．国际象棋棋盘着色问题
33
25．科学家在世的最好时代
34
26．寻找图灵
34
27．Icosian游戏
35
28．一笔画
35
29．重温幻方
35
30．棍子切割
35
31．三堆牌魔术
35
32．单淘汰赛
36
33．真伪幻方
36
34．星星的硬币
36
35．三个水壶
37
36．有限的差异
37
37．2n筹码问题
37
38．四格骨牌平铺问题
37
39．方格遍历
38
40．四个调换的骑士
38
41．灯之圈
38
42．狼羊菜过河问题的另一个版本
39
43．数字填充
39
44．孰轻孰重
39
45．骑士的捷径
39
46．三色排列
39
47．展览规划
39
48．麦乐鸡数字
40
49．传教士与食人族
40
50．最后一个球
40
51．缺失的数字
41
52．数三角形
41
53．弹簧秤甄别假币
41
54．矩形切割
41
55．里程表之谜
42
56．新兵列队
42
57．斐波那契的兔子问题
42
58．二维排序
42
59．双色帽子
42
60．硬币三角形变正方形
43
61．对角线上的棋子
43
62．硬币收集
43
63．加减归零
43
64．构建八边形
43
65．猜密码
44
66．留下的数字
44
67．均分减少
44
68．数位求和
44
69．扇区上的筹码
44
70．跳跃成对I
44
71．标记方格I
45
72．标记方格II
45
73．逮公鸡
45
74．地点选择
46
75．加油站检查问题
46
76．高效的车
46
77．模式搜索
47
78．直三格板平铺
47
79．储物柜门
47
80．王子之旅
47
81．再论名人问题
47
82．头像朝上
48
83．受限的汉诺塔
48
84．煎饼排序
48
85．散布谣言I
49
86．散布谣言II
49
87．倒置的玻璃杯
49
88．蟾蜍和青蛙
49
89．纸牌交换
49
90．座位重排
50
91．水平的和垂直的多米诺骨牌
50
92．梯形平铺
50
93．击中战舰
51
94．搜索排好序的表
51
95．最大-最小称重
51
96．平铺楼梯区域
51
97．Topswops游戏
51
98．回文计数
52
99．倒序排列
52
100．骑士的走位
52
101．房间喷漆
52
102．猴子和椰子
52
103．跳到另一边
53
104．堆分割
53
105．MU问题
53
106．开灯
54
107．狐狸和野兔
54
108．最长路径
54
109．双n多米诺骨牌
54
110．变色龙
55
111．反转硬币三角形阵
55
112．再次讨论多米诺平铺问题
55
113．拿走硬币
55
114．划线过点
56
115．Bachet的砝码
56
116．轮空计数
56
117．一维跳棋
57
118．六骑士
57
119．有色三格板平铺
57
120．硬币分发机
57
121．超级蛋测试
58
122．议会和解
58
123．荷兰国旗问题
58
124．切割链条
58
125．对5个物品称重7次来排序
58
126．公平切分蛋糕
58
127．骑士之旅
58
128．安全开关
59
129．Reve之谜
59
130．毒酒
59
131．Tait筹码谜题
59
132．跳棋军队
60
133．生命的游戏
60
134．点着色
61
135．不同的配对
61
136．抓捕间谍
61
137．跳跃成对Ⅱ
62
138．糖果分享
62
139．亚瑟国王的圆桌
62
140．重温n皇后问题
62
141．约瑟夫问题
63
142．12枚硬币
63
143．被感染的棋盘
63
144．拆除方格
63
145．十五谜题
63
146．击中移动目标
64
147．编号的帽子
64
148．自由硬币
64
149．卵石扩张
65
150．保加利亚接龙
66
第3章 提示
67
1．狼羊菜过河
67
2．手套选择
67
3．矩形切割
67
4．士兵摆渡
67
5．行列变换
67
6．数数的手指
67
7．夜过吊桥
67
8．拼图问题
67
9．心算求和
67
10．硬币中的假币
67
11．假币堆问题
67
12．平铺多米诺问题
67
13．被堵塞的路径
67
14．复原国际象棋棋盘
68
15．三格骨牌平铺问题
68
16．煎饼制作
68
17．国王的走位
68
18．骑士的征途
68
19．页码计数
68
20．寻找最大和
68
21．正方形的拆分
68
22．球队排名
68
23．波兰国旗问题
68
24．国际象棋棋盘着色问题
68
25．科学家在世的最好时代
68
26．寻找图灵
68
27．Icosian游戏
68
28．一笔画
68
29．重温幻方
68
30．棍子切割
68
31．三堆牌魔术
69
32．单淘汰赛
69
33．真伪幻方
69
34．星星的硬币
69
35．三个水壶
69
36．有限的差异
69
37．2n筹码问题
69
38．四格骨牌
69
39．方格遍历
69
40．四个调换的骑士
69
41．灯之圈
69
42．狼羊菜过河问题的另一个版本
69
43．数字填充
69
44．孰轻孰重
69
45．骑士的捷径
69
46．三色排列
69
47．展览规划
69
48．麦乐鸡数字
70
49．传教士与食人族
70
50．最后一个球
70
51．缺失的数字
70
52．数三角形
70
53．弹簧秤甄别假币
70
54．矩形切割
70
55．里程表之谜
70
56．新兵列队
70
57．斐波那契的兔子问题
70
58．二维排序
70
59．双色帽子
70
60．硬币三角形变矩形
70
61．对角线上的棋子
70
62．硬币收集
71
63．加减归零
71
64．构建八边形
71
65．猜密码
71
66．留下的数字
71
67．均分减少
71
68．数位求和
71
69．扇区上的筹码
71
70．跳跃成对I
71
71．标记方格I
71
72．标记方格II
71
73．逮公鸡
71
74．地点选择
71
75．加油站检查问题
71
76．高效的车
71
77．模式搜索
71
78．直三格板平铺
72
79．储物柜门
72
80．王子之旅
72
81．再论名人问题
72
82．头像朝上
72
83．受限的汉诺塔
72
84．煎饼排序
72
85．散布谣言I
72
86．散布谣言II
72
87．倒置的玻璃杯
72
88．蟾蜍和青蛙
72
89．纸牌交换
72
90．座位重排
72
91．水平的和垂直的多米诺骨牌
72
92．梯形平铺
72
93．击中战舰
73
94．搜索排好序的列表
73
95．最大-最小称重
73
96．平铺楼梯区域
73
97．Topswops游戏
73
98．回文计数
73
99．倒序排列
73
100．骑士的走位
73
101．房间喷漆
73
102．猴子和椰子
73
103．跳到另一边
73
104．堆分割
73
105．MU问题
73
106．开灯
73
107．狐狸和野兔
73
108．最长路径
73
109．双n多米诺骨牌
73
110．变色龙
73
111．反转硬币三角形阵
74
112．再次讨论多米诺平铺问题
74
113．拿走硬币
74
114．划线过点
74
115．Bachet的砝码
74
116．轮空计数
74
117．一维跳棋
74
118．六骑士
74
119．有色三格板平铺
74
120．硬币分发机
74
121．超级蛋测试
74
122．议会和解
74
123．荷兰国旗问题
74
124．切割链条
75
125．对5个物品称重7次来排序
75
126．公平切分蛋糕
75
127．骑士之旅
75
128．安全开关
75
129．Reve之谜
75
130．毒酒
75
131．Tait筹码谜题
75
132．跳棋军队
75
133．生命的游戏
75
134．点着色
75
135．不同的配对
76
136．抓捕间谍
76
137．跳跃成对Ⅱ76
138．糖果分享
76
139．亚瑟国王的圆桌
76
140．重温n皇后问题
76
141．约瑟夫问题
76
142．12枚硬币
76
143．被感染的棋盘
76
144．拆除方格
76
145．十五谜题
76
146．击中移动目标
76
147．编号的帽子
76
148．自由硬币
77
149．卵石扩张
77
150．保加利亚接龙
77
第4章 答案
78
1．狼羊菜过河
78
2．手套选择
79
3．矩形切割
79
4．士兵摆渡
80
5．行列变换
80
6．数数的手指
81
7．夜过吊桥
82
8．拼图问题
83
9．心算求和
83
10．硬币中的假币
84
11．假币堆问题
85
12．平铺多米诺问题
85
13．被堵塞的路径
86
14．复原国际象棋棋盘
86
15．三格骨牌平铺问题
87
16．煎饼制作
88
17．国王的走位
88
18．骑士的征途
89
19．页码计数
90
20．寻找最大和
90
21．正方形的拆分
91
22．球队排名
92
23．波兰国旗问题
92
24．国际象棋棋盘着色问题
93
25．科学家在世的最好时代
94
26．寻找图灵
94
27．Icosian游戏
95
28．一笔画
95
29．重温幻方
97
30．棍子切割
99
31．三堆牌魔术
99
32．单淘汰赛
100
33．真伪幻方
101
34．星星的硬币
102
35．三个水壶
103
36．有限的差异
104
37．2n筹码问题
105
38．四格骨牌平铺问题
106
39．方格遍历
108
40．四个调换的骑士
108
41．灯之圈
109
42．狼羊菜过河问题的
另一个版本
110
43．数字填充
111
44．孰轻孰重
111
45．骑士的捷径
112
46．三色排列
112
47．展览规划
113
48．麦乐鸡数字
114
49．传教士与食人族
115
50．最后一个球
116
51．缺失的数字
116
52．数三角形
117
53．弹簧秤甄别假币
118
54．矩形切割
118
55．里程表之谜
119
56．新兵列队
120
57．斐波那契的兔子问题
120
58．二维排序
121
59．双色帽子
122
60．硬币三角形变正方形
123
61．对角线上的棋子
125
62．硬币收集
126
63．加减归零
127
64．构建八边形
128
65．猜密码
129
66．留下的数字
130
67．均分减少
130
68．数位求和
131
69．扇区上的筹码
132
70．跳跃成对I
133
71．标记方格I
133
72．标记方格II
134
73．逮公鸡
135
74．地点选择
137
75．加油站检查问题
138
76．高效的车
139
77．模式搜索
140
78．直三格板平铺
141
79．储物柜门
141
80．王子之旅
142
81．再论名人问题
143
82．头像朝上
144
83．受限的汉诺塔
144
84．煎饼排序
147
85．散布谣言I
148
86．散布谣言II
149
87．倒置的玻璃杯
150
88．蟾蜍和青蛙
150
89．纸牌交换
152
90．座位重排
153
91．水平的和垂直的多米诺骨牌
153
92．梯形平铺
154
93．击中战舰
157
94．搜索排好序的表
157
95．最大-最小称重
158
96．平铺楼梯区域
159
97．Topswops游戏
161
98．回文计数
162
99．倒序排列
163
100．骑士的走位
164
101．房间喷漆
165
102．猴子和椰子
166
103．跳到另一边
167
104．堆分割
167
105．MU谜题
169
106．开灯
169
107．狐狸和野兔
171
108．最长路径
172
109．双n多米诺骨牌
173
110．变色龙
174
111．反转硬币三角形阵
174
112．再次讨论多米诺平铺问题
177
113．拿走硬币
178
114．划线过点
179
115．Bachet的砝码
179
116．轮空计数
182
117．一维跳棋
183
第4118．六骑士
184
119．有色三格板平铺
186
120．硬币分配机
187
121．超级蛋测试
188
122．议会和解
189
123．荷兰国旗问题
190
124．切割链条
191
125．对5个物品称重7次来排序
192
126．公平切分蛋糕
194
127．骑士之旅
194
128．安全开关
196
129．Reve之谜
197
130．毒酒
199
131．Tait筹码谜题
200
132．跳棋军队
202
133．生命的游戏
204
134．点着色
205
135．不同的配对
206
136．抓捕间谍
207
137．跳跃成对Ⅱ
209
138．糖果分享
210
139．亚瑟国王的圆桌
211
140．重温n皇后问题
212
141．约瑟夫问题
214
142．12枚硬币
215
143．被感染的棋盘
217
144．拆除方格
218
145．十五谜题
220
146．击中移动目标
221
147．编号的帽子
223
148．自由硬币
223
149．卵石扩张
226
150．保加利亚接龙
228
作者简介
算法是计算机科学领域最重要的基石之一。算法谜题，就是能够直接或间接地采用算法来加以解决的谜题。求解算法谜题是培养和锻炼算法思维能力一种最有效和最有乐趣的途径。
本书是一本经典算法谜题的合集。本书包括了一些古已有之的谜题，数学和计算机科学有一部分知识就发源于此。本书中还有一些较新的谜题，其中有一部分谜题被用作知名IT企业的面试题。全书可分为4个部分，分别是概览、谜题、提示和答案。概览介绍了算法设计的通用策略和算法分析的技术，还附带有不少的实例。谜题部分将谜题按照简单、中等难度和较难三个层级分别列出。提示部分依次给出谜题提示，帮助读者找到正确的解题方向，同时仍然为读者留下了独立求解的空间。答案部分则给出了谜题的详细解答。
本书可以为对算法感兴趣的广大读者提供系统丰富而实用的资料，能够帮助读者提升高阶算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及在准备面试的应聘者和面试官阅读参考。
发布书评
精彩书评 (总计1条)
-
##2. 手套选择具体思想就是，**化繁为简**。先考虑我们有2双灰色手套，那么要保证挑出的手套至少是一对灰色的，显然需要挑**2+1=3次**（如果只挑两次的话，运气不佳，刚好挑到了2个左手，那就不能满足条件）。现在将条件扩大，一共十双手套（忽略颜色，只考虑左右手），那么如果运气不好，只挑10次刚好是10个左手，显然不能满足要求(a)至少挑出一双颜色匹配的手套。因此，至少要挑10+1次。至于要求(b)所有颜色的手套都至少挑出一双匹配的，仍然考虑最糟糕的情况，假设调了16次，这16次恰好是5双黑色加3双棕色，少了灰色手套不满足要求，从前面的分析知道，为了挑出一对灰色的手套，需要再挑3次，因此至少要挑19次。##3. 矩形切割用2进制表示n##4. 士兵摆渡先考虑让1名士兵过河##5. 行列变换第一想法时,求行列式;)求行列式的算法太复杂,显然原书的答案更快,check每行(列),该行(列)是否在原来的矩阵中出现过.##6. 数数的手指显然,是个循环的问题,1000%8=0(abcdecb...)因此,是手指b(即食指)##7. 夜过吊桥我表示这题没想出来,当然,看答案后感觉不够通俗易懂,所以这里用自己的方式来讲解下.首先,我们把问题泛化一点,这样理解起来更容易些:假设桥的一边有4个人,其中有两个**大哥(A,B)**,过桥时间分别为10min和10min,另外有两个**小弟(c,d)**过桥时间分别为1min和1min,其他条件相同.显然直觉告诉我们,两个大哥一起过桥,然后两个小弟一起过桥这样最省时间,但问题是,只有一个手电筒,两个大哥先过桥后,手电筒还得要一位大哥送回来,送回来后这位大哥还得再过桥,这样时间都浪费在这位大哥身上了.至此我们发现,来回路上送手电筒的人很关键,所以典型的贪心算法就是每次都让跑得快的小弟**来回**送手电筒,所以c陪着A过桥(10min),再回来(1min),再陪着B过桥(10min),再回来(1min),再陪着d过桥(1min)一共23min.如图所示:这样的方案显然不够让人满意,因为两个大哥是分开过桥,假设现在不是两个大哥,而是十个大哥,那岂不是要分成十次过桥!这样子一想,还是觉得让两个大哥同时过桥效率更高.但是这又会遇到前面说过的问题,等于是绕回来了.等等,前面的问题是什么来着?两个大哥如果先过桥,得让其中一个大哥把手电筒送回去,这样时间都浪费在这位大哥上了.那有没有可能让小弟送回去呢?问题是对岸没有小弟啊!!!那能不能先派个小弟过去呢?当然可以!所以就得到了下图(方案2):这样效率高多了,假设有很多大哥,那么根据问题4(士兵摆渡)中的思想,先运送两个大哥,再运送两个大哥......OK,将我们的方案抽象出来描述就是,先派一个跑得快的小弟到对岸等着,然后跑的慢的两位大哥一起过,再让对岸的那个小弟把手电筒送回来,周而复始.那么再想一个问题,方案2是否一定比方案1快?显然,如果小弟跑的只比大哥稍稍快一点点,那么这样子先派小弟过去所浪费的时间也就太多了.通过分析可以发现,两种方案都可以将问题化解为送一对大哥到对岸的子问题.假设两个小弟过桥时间为$m_1, m_2, m_1 < m_2$两个大哥过桥时间为$n_1, n_2, n_1 \lt n_2, n_1 \ge m_2$,那么方案1解决该子问题所需时间为$t_1=n_2+m_1+n_1+m_1$注意小弟还得把手电筒送回来下一轮才能开始;方案2解决该子问题所需时间为$t_2=m_2+m_1+n_2+m_2$. 那么$t_2 < t_1$的条件是$2m_2 < m_1+n_1$回到题干中给出的条件,对应的,$m_1=1, m_2=2,n_1=5,n_2=10$, 那么左右两式相等，满足$2m_2< m_1+n_1$的约束，如果将条件$m_2=2$改为$m_2=3$，可以验证，两种方案所花的时间时相同的。##8. 拼图问题类似问题4,降低问题规模,如果不是500,而是3片,4片,5片呢?##9. 对称，转成上（下）三角矩阵，再等差求和##10. 联想到猜数字的问题：给定一个1-8之间的数，每猜一次会被告知大了还是小了或者猜对了。问猜至少几次？每猜一次，我们得到2个信息，是在A中，还是在B中。但是，如果换到天平称重的问题上，实际上我们可以得到3个信息，A中，B中，还是C中。因此，至少需要log3(x)次##13.被堵塞的路径其实是一个经典的组合问题.从A到B的最短路径是7步,可能的步数是C(7,3),即7步之中任选3步向下走.然后挑出经过P点的路径. $C(4,2) × C(3,1)$, 所以结果时, $C(7,3) - C(4,2) × C(3,1)$##14. 答案写错了吧???##15. 不变量的思想比较有意思,如果一个n*n的面板可以用一个由k个方格子组成的骨牌密铺的话,那么首先应当满足n*n 能被k整除##16. 3分钟可以煎3个饼!3分钟可以煎3个饼!3分钟可以煎3个饼!ok,搞清楚这个就行了##17. 吐槽下,题目的错别字很坑...应该时可能到达的方格的个数##18. 神奇的不变量##20. 没有更快的办法了么？##30. 题目有些没说清的地方，应该指出，有一把尺子，可以切出任意长度的棍子##36.题目的解答有点意思，就是可以看做一个队列，然后入队和出队后可以得到一个有限状态机。##40.该题的解题思想灰常重要。将棋盘上骑士的可移动位置映射到环形的状态空间中去，脱离了原始的马走日限制，利于分析。##43.每次数据规模减一，问题不变，从而解决n的问题##44.注意区分奇偶充分利用真币居多，假币只有一枚这一特性。##45.引申到A*算法，曼哈顿距离作为代价函数##46.同样采用减一和穷举的方法来考虑。##48.经典的动态规划问题
精彩短评 (总计15条)
-
不错的算法题集 -
只是题... -
挺可以的书,不过好多题都是类似. -
赞！ -
无聊时思考一两个题打发时间。。 -
值得买一本，放在床头慢慢看。 -
书是好书，放在枕边没事翻着玩。另外！！！不是只有题，答案在后面，后面！！！ -
智力题。 -
书是好书，可惜没有源码。 -
不知道给高分的人都是什么心态？这本所谓的书只是收集了200多个各种类型的貌似有趣的算法题。分3部分，1就是题，2是所谓分析，3是答案。来看看所谓的分析：第22题三角形路径权值最大和的分析就几个字：使用动态规划。再看答案：一个图，一个圆圈标出三角形中一个数的最大和，没有代码，没有算法。我只想对作者说：艹你大爷 -
还是挺好玩的 -
未做完。 -
给这本书加“算法与数据结构”标签的真是够了，这里哪有数据结构？算法还沾点边，但题型其实也不多，而且更偏向数学类。真要巩固算法的还是去acm网站多写写代码吧，这本书当空闲时间活跃思维的小书看看就好。别太当真。 -
算法谜题的思考，解题不够详细有趣 -
这是智力题集锦么。。。表示，好想回到了小学奥数时代，不过还是挺有意思的~~