謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（puzzle）就是一種最棒的實際應用，它的優勢在於易於描述和引人注目。後者如今尤為重要。讓我們看一下今天推薦的這本算法書。
編程的樂趣：用Python解算法謎題
謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（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 美國達人秀
本謎題涵蓋的編程結構與算法範型：通過列表表示二維表格。
你決定舉辦一檔叫作“誰是達人”的電視節目[1]
，春季假期後有很多選手報名，而你將主持節目的海選。每位選手都有自己的絕活（如插花、跳舞、滑板等），而你在海選中檢驗他們的表現。多數選手的表現都不能令你滿意，但是有一部分選手能做到。現在你有一組選手，他們會每人向你表演至少一項絕活。
在你的節目中，你希望能突出表現多種多樣的絕活。如果每週全都是各種插花表演，對收視率是沒有幫助的。你拿出選手列表，整理出他們的絕活列表。然後你去找製作人，讓他答應在節目中覆蓋這些絕活。你的製作人會削減這張列表（例如，他們認為觀眾不喜歡重複的節目），交由你選出最終的列表。他們也告訴你，要控制成本。
你明白最好的控制成本、提高收視率的方法是聯繫儘量少的選手，同時提供儘量多的節目種類。因此你想在最終的列表中選出最少的選手，而他們能演出所有的絕活。
假設你最後選出了表9-1所示的選手與絕活。
表9-1
謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（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 美國達人秀
本謎題涵蓋的編程結構與算法範型：通過列表表示二維表格。
你決定舉辦一檔叫作“誰是達人”的電視節目[1]
，春季假期後有很多選手報名，而你將主持節目的海選。每位選手都有自己的絕活（如插花、跳舞、滑板等），而你在海選中檢驗他們的表現。多數選手的表現都不能令你滿意，但是有一部分選手能做到。現在你有一組選手，他們會每人向你表演至少一項絕活。
在你的節目中，你希望能突出表現多種多樣的絕活。如果每週全都是各種插花表演，對收視率是沒有幫助的。你拿出選手列表，整理出他們的絕活列表。然後你去找製作人，讓他答應在節目中覆蓋這些絕活。你的製作人會削減這張列表（例如，他們認為觀眾不喜歡重複的節目），交由你選出最終的列表。他們也告訴你，要控制成本。
你明白最好的控制成本、提高收視率的方法是聯繫儘量少的選手，同時提供儘量多的節目種類。因此你想在最終的列表中選出最少的選手，而他們能演出所有的絕活。
假設你最後選出了表9-1所示的選手與絕活。
表9-1
在上面的例子中，你可以選擇Aly、Bob、Don和Eve，從而覆蓋所有絕活。Aly會柔術和代碼，Bob會跳舞和魔術，Don會跳舞和唱歌，Eve會跳舞、動作和代碼。他們總共有6種絕活。
你能用盡量少的人覆蓋所有的絕活嗎？更一般地說，你怎樣選擇最少的選手（行），做到能夠覆蓋表格中所有的絕活（列）？表9-2中展示另一個例子。
表9-2
謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（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 美國達人秀
本謎題涵蓋的編程結構與算法範型：通過列表表示二維表格。
你決定舉辦一檔叫作“誰是達人”的電視節目[1]
，春季假期後有很多選手報名，而你將主持節目的海選。每位選手都有自己的絕活（如插花、跳舞、滑板等），而你在海選中檢驗他們的表現。多數選手的表現都不能令你滿意，但是有一部分選手能做到。現在你有一組選手，他們會每人向你表演至少一項絕活。
在你的節目中，你希望能突出表現多種多樣的絕活。如果每週全都是各種插花表演，對收視率是沒有幫助的。你拿出選手列表，整理出他們的絕活列表。然後你去找製作人，讓他答應在節目中覆蓋這些絕活。你的製作人會削減這張列表（例如，他們認為觀眾不喜歡重複的節目），交由你選出最終的列表。他們也告訴你，要控制成本。
你明白最好的控制成本、提高收視率的方法是聯繫儘量少的選手，同時提供儘量多的節目種類。因此你想在最終的列表中選出最少的選手，而他們能演出所有的絕活。
假設你最後選出了表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. def Hire4Show(candList, candTalents, talentList):
2. n =len(candList)
3. hire = candList[:]
4. for i inrange(2**n):
5. Combination = []
6. num = i
7. for jinrange(n):
8. if (num % 2 == 1):
9. Combination = [candList[n-1-j]] + Combination
10． num = num // 2
11． ifGood(Combination, candList, candTalents, talentList):
12． iflen(hire) > len(Combination):
13． hire = Combination
14． print('Optimum Solution:', hire)
第4～10行生成值num = i對應的組合。第11行調用函數Good——這會在後面詳述——用於檢查給定的選手組合是否覆蓋所有絕活。如果是，則與當前已知最優的選手組合比較，如果選手人數少於最優組合，則更新最優組合（第12～13行）。
第3行與謎題8的對應行的invite = []不同。在謎題8中，我們希望最大化能邀請的客人數量，因此將一個空列表作為最初的最優組合。在這裡，我們想最小化聘請的選手數量，因此將完整的選手列表作為最初的最優組合。我們假定完整的選手組合能夠滿足覆蓋所有絕活的要求。如果不能滿足，可以重新考量絕活的列表。
9.2 確定缺少一門絕活的組合
我們調用函數Hire4Show來確定一個給定的選手組合是否包含所有絕活。我們要做的這項檢查與謎題8有很大不同，這一點會在下面展示。
1. def Good(Comb, candList, candTalents, AllTalents):
2. for tal in AllTalents:
3. cover = False
4. for cand inComb:
5. candTal = candTalents[candList.index(cand)]
6. if tal in candTal:
7. cover = True
8. ifnot cover:
9. returnFalse
10． returnTrue
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
謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（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 美國達人秀
本謎題涵蓋的編程結構與算法範型：通過列表表示二維表格。
你決定舉辦一檔叫作“誰是達人”的電視節目[1]
，春季假期後有很多選手報名，而你將主持節目的海選。每位選手都有自己的絕活（如插花、跳舞、滑板等），而你在海選中檢驗他們的表現。多數選手的表現都不能令你滿意，但是有一部分選手能做到。現在你有一組選手，他們會每人向你表演至少一項絕活。
在你的節目中，你希望能突出表現多種多樣的絕活。如果每週全都是各種插花表演，對收視率是沒有幫助的。你拿出選手列表，整理出他們的絕活列表。然後你去找製作人，讓他答應在節目中覆蓋這些絕活。你的製作人會削減這張列表（例如，他們認為觀眾不喜歡重複的節目），交由你選出最終的列表。他們也告訴你，要控制成本。
你明白最好的控制成本、提高收視率的方法是聯繫儘量少的選手，同時提供儘量多的節目種類。因此你想在最終的列表中選出最少的選手，而他們能演出所有的絕活。
假設你最後選出了表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. def Hire4Show(candList, candTalents, talentList):
2. n =len(candList)
3. hire = candList[:]
4. for i inrange(2**n):
5. Combination = []
6. num = i
7. for jinrange(n):
8. if (num % 2 == 1):
9. Combination = [candList[n-1-j]] + Combination
10． num = num // 2
11． ifGood(Combination, candList, candTalents, talentList):
12． iflen(hire) > len(Combination):
13． hire = Combination
14． print('Optimum Solution:', hire)
第4～10行生成值num = i對應的組合。第11行調用函數Good——這會在後面詳述——用於檢查給定的選手組合是否覆蓋所有絕活。如果是，則與當前已知最優的選手組合比較，如果選手人數少於最優組合，則更新最優組合（第12～13行）。
第3行與謎題8的對應行的invite = []不同。在謎題8中，我們希望最大化能邀請的客人數量，因此將一個空列表作為最初的最優組合。在這裡，我們想最小化聘請的選手數量，因此將完整的選手列表作為最初的最優組合。我們假定完整的選手組合能夠滿足覆蓋所有絕活的要求。如果不能滿足，可以重新考量絕活的列表。
9.2 確定缺少一門絕活的組合
我們調用函數Hire4Show來確定一個給定的選手組合是否包含所有絕活。我們要做的這項檢查與謎題8有很大不同，這一點會在下面展示。
1. def Good(Comb, candList, candTalents, AllTalents):
2. for tal in AllTalents:
3. cover = False
4. for cand inComb:
5. candTal = candTalents[candList.index(cand)]
6. if tal in candTal:
7. cover = True
8. ifnot cover:
9. returnFalse
10． returnTrue
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
謎題趣味非凡。頂級謎題的解可沒那麼淺顯易得，需要靈光一閃才能發現。算法謎題是指謎題的解法就是算法，解題的步驟可以被機器自動執行。算法可以用英文或者其他任何自然語言來描述，但是為了更加精確，往往會用偽代碼進行描述。之所以稱為“偽代碼”，是因為它尚未細化到足以在計算機上運行的程度，與用編程語言編寫的代碼不大一樣。
當今世界有越來越多的人以計算機編程為業。為了學習編程，我們首先要通過簡單的例子學習基本的編程結構，例如賦值語句和控制循環之類，而編程習題往往涉及將算法的偽代碼轉譯為用所學編程語言編寫的代碼。程序員同樣能從求解謎題所需的分析技能中獲益。無論是將規格說明轉換為編程結構，還是定位早期代碼中的錯誤（也就是調試過程），這些分析技能都不可或缺。
謎題（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 美國達人秀
本謎題涵蓋的編程結構與算法範型：通過列表表示二維表格。
你決定舉辦一檔叫作“誰是達人”的電視節目[1]
，春季假期後有很多選手報名，而你將主持節目的海選。每位選手都有自己的絕活（如插花、跳舞、滑板等），而你在海選中檢驗他們的表現。多數選手的表現都不能令你滿意，但是有一部分選手能做到。現在你有一組選手，他們會每人向你表演至少一項絕活。
在你的節目中，你希望能突出表現多種多樣的絕活。如果每週全都是各種插花表演，對收視率是沒有幫助的。你拿出選手列表，整理出他們的絕活列表。然後你去找製作人，讓他答應在節目中覆蓋這些絕活。你的製作人會削減這張列表（例如，他們認為觀眾不喜歡重複的節目），交由你選出最終的列表。他們也告訴你，要控制成本。
你明白最好的控制成本、提高收視率的方法是聯繫儘量少的選手，同時提供儘量多的節目種類。因此你想在最終的列表中選出最少的選手，而他們能演出所有的絕活。
假設你最後選出了表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. def Hire4Show(candList, candTalents, talentList):
2. n =len(candList)
3. hire = candList[:]
4. for i inrange(2**n):
5. Combination = []
6. num = i
7. for jinrange(n):
8. if (num % 2 == 1):
9. Combination = [candList[n-1-j]] + Combination
10． num = num // 2
11． ifGood(Combination, candList, candTalents, talentList):
12． iflen(hire) > len(Combination):
13． hire = Combination
14． print('Optimum Solution:', hire)
第4～10行生成值num = i對應的組合。第11行調用函數Good——這會在後面詳述——用於檢查給定的選手組合是否覆蓋所有絕活。如果是，則與當前已知最優的選手組合比較，如果選手人數少於最優組合，則更新最優組合（第12～13行）。
第3行與謎題8的對應行的invite = []不同。在謎題8中，我們希望最大化能邀請的客人數量，因此將一個空列表作為最初的最優組合。在這裡，我們想最小化聘請的選手數量，因此將完整的選手列表作為最初的最優組合。我們假定完整的選手組合能夠滿足覆蓋所有絕活的要求。如果不能滿足，可以重新考量絕活的列表。
9.2 確定缺少一門絕活的組合
我們調用函數Hire4Show來確定一個給定的選手組合是否包含所有絕活。我們要做的這項檢查與謎題8有很大不同，這一點會在下面展示。
1. def Good(Comb, candList, candTalents, AllTalents):
2. for tal in AllTalents:
3. cover = False
4. for cand inComb:
5. candTal = candTalents[candList.index(cand)]
6. if tal in candTal:
7. cover = True
8. ifnot cover:
9. returnFalse
10． returnTrue
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用於選擇最小權重選手集合的代碼中。
[1]這道謎題的標題取自NBC的Talent Show（2006—）。