第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
· · · · · · (收起)