本文關(guān)鍵詞：算法謎題，由筆耕文化傳播整理發(fā)布。

內(nèi)容概要

算法是計(jì)算機(jī)科學(xué)領(lǐng)域最重要的基石之一。算法謎題，就是能夠直接或間接地采用算法來(lái)加以解決的謎題。求解算法謎題是培養(yǎng)和鍛煉算法思維能力一種最有效和最有樂(lè)趣的途徑。
本書是一本經(jīng)典算法謎題的合集。本書包括了一些古已有之的謎題，數(shù)學(xué)和計(jì)算機(jī)科學(xué)有一部分知識(shí)就發(fā)源于此。本書中還有一些較新的謎題，其中有一部分謎題被用作知名IT企業(yè)的面試題。全書可分為4個(gè)部分，分別是概覽、謎題、提示和答案。概覽介紹了算法設(shè)計(jì)的通用策略和算法分析的技術(shù)，還附帶有不少的實(shí)例。謎題部分將謎題按照簡(jiǎn)單、中等難度和較難三個(gè)層級(jí)分別列出。提示部分依次給出謎題提示，幫助讀者找到正確的解題方向，，同時(shí)仍然為讀者留下了獨(dú)立求解的空間。答案部分則給出了謎題的詳細(xì)解答。
本書可以為對(duì)算法感興趣的廣大讀者提供系統(tǒng)豐富而實(shí)用的資料，能夠幫助讀者提升高階算法思維能力。本書適合計(jì)算機(jī)專業(yè)的高校教師和學(xué)生，想要培養(yǎng)和訓(xùn)練算法思維和計(jì)算思維的IT專業(yè)人士，以及在準(zhǔn)備面試的應(yīng)聘者和面試官閱讀參考。

作者簡(jiǎn)介

作者簡(jiǎn)介
Anany Levitin，美國(guó)Villanova大學(xué)計(jì)算科學(xué)教授。他是一本算法設(shè)計(jì)和分析名著的作者，該書被譯為中文、希臘文等多國(guó)語(yǔ)言。他還在數(shù)學(xué)最優(yōu)化算法、軟件工程、數(shù)據(jù)管理、算法設(shè)計(jì)和計(jì)算機(jī)科學(xué)教育等領(lǐng)域發(fā)表過(guò)多篇論文。
Maria Levitin，獨(dú)立咨詢師。她在大型軟件公司有多年的商業(yè)應(yīng)用軟件開發(fā)經(jīng)驗(yàn)，現(xiàn)在她專注于Web應(yīng)用和無(wú)線計(jì)算領(lǐng)域。
譯者簡(jiǎn)介
趙勇，電子科技大學(xué)教授，極限網(wǎng)絡(luò)計(jì)算與服務(wù)實(shí)驗(yàn)室主任，中國(guó)計(jì)算機(jī)學(xué)會(huì)大數(shù)據(jù)專家委員會(huì)委員。美國(guó)芝加哥大學(xué)博士，師從世界網(wǎng)格之父Ian Foster教授，其間在美國(guó)IBM研發(fā)中心、美國(guó)Argonne國(guó)家實(shí)驗(yàn)室實(shí)習(xí)。博士畢業(yè)后任職美國(guó)微軟公司搜索與廣告部，從事云平臺(tái)上的大型廣告系統(tǒng)開發(fā)，獲微軟杰出員工獎(jiǎng)。
徐章寧，1984年生，畢業(yè)于上海交通大學(xué)。在EMC中國(guó)卓越研發(fā)集團(tuán)任高級(jí)系統(tǒng)管理工程師，鐘愛(ài)開源軟件，從事軟件運(yùn)維工作多年。對(duì)各類知識(shí)有廣泛興趣，平日喜愛(ài)參與問(wèn)答網(wǎng)站討論，熱愛(ài)讀書攝影和寫作。
高博，1983年生，畢業(yè)于上海交通大學(xué)。目前在EMC中國(guó)卓越研發(fā)集團(tuán)任首席工程師，在信息科學(xué)和工程領(lǐng)域有近15年實(shí)踐和研究經(jīng)驗(yàn)�？釔�(ài)讀書和寫作，業(yè)余研究興趣涉獵廣泛。譯著包括圖靈獎(jiǎng)作者高德納的《研究之美》和布魯克斯的《設(shè)計(jì)原本》，以及Jolt大獎(jiǎng)作品《基元設(shè)計(jì)模式》等。近年來(lái)，出版翻譯作品近百萬(wàn)字。

書籍目錄

第1章 概覽 1
1.1 算法設(shè)計(jì)的若干通用策略 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 迭代改進(jìn) 15
1.1.8 動(dòng)態(tài)規(guī)劃 18
1.2 分析技術(shù) 19
1.2.1 幾個(gè)求和公式，兼論算法效率 20
1.2.2 非遞歸算法分析 21
1.2.3 遞歸算法分析 23
1.2.4 不變量 25
第2章 謎題 29
2.1 簡(jiǎn)單謎題 29
2.2 中等難度謎題 41
2.3 較難謎題 55
第3章 提示 67
第4章 答案 78
算法謎題列表
第1章　概覽 1
第2章　謎題 29
1．狼羊菜過(guò)河 29
2．手套選擇 29
3．矩形切割 29
4．士兵擺渡 29
5．行列變換 30
6．?dāng)?shù)數(shù)的手指 30
7．夜過(guò)吊橋 30
8．拼圖問(wèn)題 30
9．心算求和 30
10．硬幣中的假幣 31
11．假幣堆問(wèn)題 31
12．平鋪多米諾問(wèn)題 31
13．被堵塞的路徑 31
14．復(fù)原國(guó)際象棋棋盤 31
15．三格骨牌平鋪問(wèn)題 32
16．煎餅制作 32
17．國(guó)王的走位 32
18．騎士的征途 32
19．頁(yè)碼計(jì)數(shù) 32
20．尋找最大和 33
21．正方形的拆分 33
22．球隊(duì)排名 33
23．波蘭國(guó)旗問(wèn)題 33
24．國(guó)際象棋棋盤著色問(wèn)題 33
25．科學(xué)家在世的最好時(shí)代 34
26．尋找圖靈 34
27．Icosian游戲 35
28．一筆畫 35
29．重溫幻方 35
30．棍子切割 35
31．三堆牌魔術(shù) 35
32．單淘汰賽 36
33．真?zhèn)位梅?36
34．星星的硬幣 36
35．三個(gè)水壺 37
36．有限的差異 37
37．2n籌碼問(wèn)題 37
38．四格骨牌平鋪問(wèn)題 37
39．方格遍歷 38
40．四個(gè)調(diào)換的騎士 38
41．燈之圈 38
42．狼羊菜過(guò)河問(wèn)題的另一個(gè)版本 39
43．?dāng)?shù)字填充 39
44．孰輕孰重 39
45．騎士的捷徑 39
46．三色排列 39
47．展覽規(guī)劃 39
48．麥樂(lè)雞數(shù)字 40
49．傳教士與食人族 40
50．最后一個(gè)球 40
51．缺失的數(shù)字 41
52．?dāng)?shù)三角形 41
53．彈簧秤甄別假幣 41
54．矩形切割 41
55．里程表之謎 42
56．新兵列隊(duì) 42
57．斐波那契的兔子問(wèn)題 42
58．二維排序 42
59．雙色帽子 42
60．硬幣三角形變正方形 43
61．對(duì)角線上的棋子 43
62．硬幣收集 43
63．加減歸零 43
64．構(gòu)建八邊形 43
65．猜密碼 44
66．留下的數(shù)字 44
67．均分減少 44
68．?dāng)?shù)位求和 44
69．扇區(qū)上的籌碼 44
70．跳躍成對(duì)I 44
71．標(biāo)記方格I 45
72．標(biāo)記方格II 45
73．逮公雞 45
74．地點(diǎn)選擇 46
75．加油站檢查問(wèn)題 46
76．高效的車 46
77．模式搜索 47
78．直三格板平鋪 47
79．儲(chǔ)物柜門 47
80．王子之旅 47
81．再論名人問(wèn)題 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．擊中戰(zhàn)艦 51
94．搜索排好序的表 51
95．最大-最小稱重 51
96．平鋪樓梯區(qū)域 51
97．Topswops游戲 51
98．回文計(jì)數(shù) 52
99．倒序排列 52
100．騎士的走位 52
101．房間噴漆 52
102．猴子和椰子 52
103．跳到另一邊 53
104．堆分割 53
105．MU問(wèn)題 53
106．開燈 54
107．狐貍和野兔 54
108．最長(zhǎng)路徑 54
109．雙n多米諾骨牌 54
110．變色龍 55
111．反轉(zhuǎn)硬幣三角形陣 55
112．再次討論多米諾平鋪問(wèn)題 55
113．拿走硬幣 55
114．劃線過(guò)點(diǎn) 56
115．Bachet的砝碼 56
116．輪空計(jì)數(shù) 56
117．一維跳棋 57
118．六騎士 57
119．有色三格板平鋪 57
120．硬幣分發(fā)機(jī) 57
121．超級(jí)蛋測(cè)試 58
122．議會(huì)和解 58
123．荷蘭國(guó)旗問(wèn)題 58
124．切割鏈條 58
125．對(duì)5個(gè)物品稱重7次來(lái)排序 58
126．公平切分蛋糕 58
127．騎士之旅 58
128．安全開關(guān) 59
129．Reve之謎 59
130．毒酒 59
131．Tait籌碼謎題 59
132．跳棋軍隊(duì) 60
133．生命的游戲 60
134．點(diǎn)著色 61
135．不同的配對(duì) 61
136．抓捕間諜 61
137．跳躍成對(duì)Ⅱ 62
138．糖果分享 62
139．亞瑟國(guó)王的圓桌 62
140．重溫n皇后問(wèn)題 62
141．約瑟夫問(wèn)題 63
142．12枚硬幣 63
143．被感染的棋盤 63
144．拆除方格 63
145．十五謎題 63
146．擊中移動(dòng)目標(biāo) 64
147．編號(hào)的帽子 64
148．自由硬幣 64
149．卵石擴(kuò)張 65
150．保加利亞接龍 66
第3章 提示 67
1．狼羊菜過(guò)河 67
2．手套選擇 67
3．矩形切割 67
4．士兵擺渡 67
5．行列變換 67
6．?dāng)?shù)數(shù)的手指 67
7．夜過(guò)吊橋 67
8．拼圖問(wèn)題 67
9．心算求和 67
10．硬幣中的假幣 67
11．假幣堆問(wèn)題 67
12．平鋪多米諾問(wèn)題 67
13．被堵塞的路徑 67
14．復(fù)原國(guó)際象棋棋盤 68
15．三格骨牌平鋪問(wèn)題 68
16．煎餅制作 68
17．國(guó)王的走位 68
18．騎士的征途 68
19．頁(yè)碼計(jì)數(shù) 68
20．尋找最大和 68
21．正方形的拆分 68
22．球隊(duì)排名 68
23．波蘭國(guó)旗問(wèn)題 68
24．國(guó)際象棋棋盤著色問(wèn)題 68
25．科學(xué)家在世的最好時(shí)代 68
26．尋找圖靈 68
27．Icosian游戲 68
28．一筆畫 68
29．重溫幻方 68
30．棍子切割 68
31．三堆牌魔術(shù) 69
32．單淘汰賽 69
33．真?zhèn)位梅?69
34．星星的硬幣 69
35．三個(gè)水壺 69
36．有限的差異 69
37．2n籌碼問(wèn)題 69
38．四格骨牌 69
39．方格遍歷 69
40．四個(gè)調(diào)換的騎士 69
41．燈之圈 69
42．狼羊菜過(guò)河問(wèn)題的另一個(gè)版本 69
43．?dāng)?shù)字填充 69
44．孰輕孰重 69
45．騎士的捷徑 69
46．三色排列 69
47．展覽規(guī)劃 69
48．麥樂(lè)雞數(shù)字 70
49．傳教士與食人族 70
50．最后一個(gè)球 70
51．缺失的數(shù)字 70
52．?dāng)?shù)三角形 70
53．彈簧秤甄別假幣 70
54．矩形切割 70
55．里程表之謎 70
56．新兵列隊(duì) 70
57．斐波那契的兔子問(wèn)題 70
58．二維排序 70
59．雙色帽子 70
60．硬幣三角形變矩形 70
61．對(duì)角線上的棋子 70
62．硬幣收集 71
63．加減歸零 71
64．構(gòu)建八邊形 71
65．猜密碼 71
66．留下的數(shù)字 71
67．均分減少 71
68．?dāng)?shù)位求和 71
69．扇區(qū)上的籌碼 71
70．跳躍成對(duì)I 71
71．標(biāo)記方格I 71
72．標(biāo)記方格II 71
73．逮公雞 71
74．地點(diǎn)選擇 71
75．加油站檢查問(wèn)題 71
76．高效的車 71
77．模式搜索 71
78．直三格板平鋪 72
79．儲(chǔ)物柜門 72
80．王子之旅 72
81．再論名人問(wèn)題 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．擊中戰(zhàn)艦 73
94．搜索排好序的列表 73
95．最大-最小稱重 73
96．平鋪樓梯區(qū)域 73
97．Topswops游戲 73
98．回文計(jì)數(shù) 73
99．倒序排列 73
100．騎士的走位 73
101．房間噴漆 73
102．猴子和椰子 73
103．跳到另一邊 73
104．堆分割 73
105．MU問(wèn)題 73
106．開燈 73
107．狐貍和野兔 73
108．最長(zhǎng)路徑 73
109．雙n多米諾骨牌 73
110．變色龍 73
111．反轉(zhuǎn)硬幣三角形陣 74
112．再次討論多米諾平鋪問(wèn)題 74
113．拿走硬幣 74
114．劃線過(guò)點(diǎn) 74
115．Bachet的砝碼 74
116．輪空計(jì)數(shù) 74
117．一維跳棋 74
118．六騎士 74
119．有色三格板平鋪 74
120．硬幣分發(fā)機(jī) 74
121．超級(jí)蛋測(cè)試 74
122．議會(huì)和解 74
123．荷蘭國(guó)旗問(wèn)題 74
124．切割鏈條 75
125．對(duì)5個(gè)物品稱重7次來(lái)排序 75
126．公平切分蛋糕 75
127．騎士之旅 75
128．安全開關(guān) 75
129．Reve之謎 75
130．毒酒 75
131．Tait籌碼謎題 75
132．跳棋軍隊(duì) 75
133．生命的游戲 75
134．點(diǎn)著色 75
135．不同的配對(duì) 76
136．抓捕間諜 76
137．跳躍成對(duì)Ⅱ76
138．糖果分享 76
139．亞瑟國(guó)王的圓桌 76
140．重溫n皇后問(wèn)題 76
141．約瑟夫問(wèn)題 76
142．12枚硬幣 76
143．被感染的棋盤 76
144．拆除方格 76
145．十五謎題 76
146．擊中移動(dòng)目標(biāo) 76
147．編號(hào)的帽子 76
148．自由硬幣 77
149．卵石擴(kuò)張 77
150．保加利亞接龍 77
第4章 答案 78
1．狼羊菜過(guò)河 78
2．手套選擇 79
3．矩形切割 79
4．士兵擺渡 80
5．行列變換 80
6．?dāng)?shù)數(shù)的手指 81
7．夜過(guò)吊橋 82
8．拼圖問(wèn)題 83
9．心算求和 83
10．硬幣中的假幣 84
11．假幣堆問(wèn)題 85
12．平鋪多米諾問(wèn)題 85
13．被堵塞的路徑 86
14．復(fù)原國(guó)際象棋棋盤 86
15．三格骨牌平鋪問(wèn)題 87
16．煎餅制作 88
17．國(guó)王的走位 88
18．騎士的征途 89
19．頁(yè)碼計(jì)數(shù) 90
20．尋找最大和 90
21．正方形的拆分 91
22．球隊(duì)排名 92
23．波蘭國(guó)旗問(wèn)題 92
24．國(guó)際象棋棋盤著色問(wèn)題 93
25．科學(xué)家在世的最好時(shí)代 94
26．尋找圖靈 94
27．Icosian游戲 95
28．一筆畫 95
29．重溫幻方 97
30．棍子切割 99
31．三堆牌魔術(shù) 99
32．單淘汰賽 100
33．真?zhèn)位梅?101
34．星星的硬幣 102
35．三個(gè)水壺 103
36．有限的差異 104
37．2n籌碼問(wèn)題 105
38．四格骨牌平鋪問(wèn)題 106
39．方格遍歷 108
40．四個(gè)調(diào)換的騎士 108
41．燈之圈 109
42．狼羊菜過(guò)河問(wèn)題的
另一個(gè)版本 110
43．?dāng)?shù)字填充 111
44．孰輕孰重 111
45．騎士的捷徑 112
46．三色排列 112
47．展覽規(guī)劃 113
48．麥樂(lè)雞數(shù)字 114
49．傳教士與食人族 115
50．最后一個(gè)球 116
51．缺失的數(shù)字 116
52．?dāng)?shù)三角形 117
53．彈簧秤甄別假幣 118
54．矩形切割 118
55．里程表之謎 119
56．新兵列隊(duì) 120
57．斐波那契的兔子問(wèn)題 120
58．二維排序 121
59．雙色帽子 122
60．硬幣三角形變正方形 123
61．對(duì)角線上的棋子 125
62．硬幣收集 126
63．加減歸零 127
64．構(gòu)建八邊形 128
65．猜密碼 129
66．留下的數(shù)字 130
67．均分減少 130
68．?dāng)?shù)位求和 131
69．扇區(qū)上的籌碼 132
70．跳躍成對(duì)I 133
71．標(biāo)記方格I 133
72．標(biāo)記方格II 134
73．逮公雞 135
74．地點(diǎn)選擇 137
75．加油站檢查問(wèn)題 138
76．高效的車 139
77．模式搜索 140
78．直三格板平鋪 141
79．儲(chǔ)物柜門 141
80．王子之旅 142
81．再論名人問(wèn)題 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．擊中戰(zhàn)艦 157
94．搜索排好序的表 157
95．最大-最小稱重 158
96．平鋪樓梯區(qū)域 159
97．Topswops游戲 161
98．回文計(jì)數(shù) 162
99．倒序排列 163
100．騎士的走位 164
101．房間噴漆 165
102．猴子和椰子 166
103．跳到另一邊 167
104．堆分割 167
105．MU謎題 169
106．開燈 169
107．狐貍和野兔 171
108．最長(zhǎng)路徑 172
109．雙n多米諾骨牌 173
110．變色龍 174
111．反轉(zhuǎn)硬幣三角形陣 174
112．再次討論多米諾平鋪問(wèn)題 177
113．拿走硬幣 178
114．劃線過(guò)點(diǎn) 179
115．Bachet的砝碼 179
116．輪空計(jì)數(shù) 182
117．一維跳棋 183
第4118．六騎士 184
119．有色三格板平鋪 186
120．硬幣分配機(jī) 187
121．超級(jí)蛋測(cè)試 188
122．議會(huì)和解 189
123．荷蘭國(guó)旗問(wèn)題 190
124．切割鏈條 191
125．對(duì)5個(gè)物品稱重7次來(lái)排序 192
126．公平切分蛋糕 194
127．騎士之旅 194
128．安全開關(guān) 196
129．Reve之謎 197
130．毒酒 199
131．Tait籌碼謎題 200
132．跳棋軍隊(duì) 202
133．生命的游戲 204
134．點(diǎn)著色 205
135．不同的配對(duì) 206
136．抓捕間諜 207
137．跳躍成對(duì)Ⅱ 209
138．糖果分享 210
139．亞瑟國(guó)王的圓桌 211
140．重溫n皇后問(wèn)題 212
141．約瑟夫問(wèn)題 214
142．12枚硬幣 215
143．被感染的棋盤 217
144．拆除方格 218
145．十五謎題 220
146．擊中移動(dòng)目標(biāo) 221
147．編號(hào)的帽子 223
148．自由硬幣 223
149．卵石擴(kuò)張 226
150．保加利亞接龍 228

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

    算法謎題 PDF格式下載

  本文關(guān)鍵詞：算法謎題，由筆耕文化傳播整理發(fā)布。