《計算思維與Python程式設計》是我們早期的Mathematics for the Digital Age and Programming in Python一書的 “更早講Python”的版本。在本書中，我們更早地介紹了Python特性，為讀者提供了必要的工具，使讀者可以更快地以更加“Python式（pythonic）”的慣用方式，開始編寫Python代碼。在本書中，我們增加了兩章（“第9章 海龜繪圖”和“第14章 向量和矩陣”），以及介紹斐波那契數列的一節（“第10章 序列與和”的10.5節）；更新了許多示例、練習和解答；更改了标題，進而更好地比對這一系列主題和快速變化的技術環境與詞彙。
但《計算思維與Python程式設計》的主要理念仍然沒有改變：介紹離散數學概念和思維，我們認為這些概念是所有有基礎的程式設計人員的基本知識。這種數學知識很容易學習，但美國大多數中國小數學課程還沒有包括離散數學的内容。本書的數學部分包括許多動手程式設計練習，這些練習可以強化學生對程式設計和數學的認識。
“那麼，這是一本數學書還是一本計算機程式設計書？”這可能是心急的讀者心中的第一個問題。但為什麼必須選擇呢？這是圖書管理者的困境：“它是屬于數學類還是計算機類？”有一個簡單的解決方案：在每類書架上各放一本。
本書的目的是教授一種特定的思維方式——精确思維，以及如何解決需要這種思維方式的問題。數學和計算機程式設計都能培養精确思維的能力，并解決那些需要精确解的問題。
數學教會我們欣賞嚴謹論證的美。從長遠來看，這比解決目前實際問題的課程更有價值。數學并不是存在于真空中的——它的抽象植根于幾個世紀以來積累的實踐知識。數學教學借鑒了我們周圍世界的例子和類比，至少它應該如此。然而，我們周圍的世界變化得越來越快。在過去的五六十年間，我們的世界變得數字化了。這種變化如此深刻，以至于人們有時難以完全了解。我們的中國小數學課程在很大程度上忽略了這種變化，這是否就是人們難以了解這種變化的原因？
如果我們能夠造出“時間機器”，讓歐幾裡得穿越時空來到現代化的世界，他會覺得很欣慰，因為在現代技術的浪潮中，他熟悉的幾何學仍然在學校裡教授。“老對手”牛頓和萊布尼茨都會感到非常滿意，因為成千上萬的美國高二和高三學生正在學習如何求導和使用積分。但是，離現在不遠的喬治·布爾（George Boole），盡管他的名字在每一種現代計算機程式設計語言中都是不朽的，但他仍然需要搜尋幾十本教材才能找到他提出的代數。至于約翰·馮·諾依曼（John von Neumann），這位才華橫溢的數學家，也是計算機技術的先驅之一……好吧，按照他一貫的樂觀态度，他會預測在20年左右的時間裡，每個國小生都會學習與門、或門和非門。但是，為什麼事實不是如此呢？
在《計算思維與Python程式設計》中，我們彙集了一些與數字世界相關的更容易了解的數學主題。其中許多主題，通常在大學新生課程中以“離散數學”之名講授。離散數學已成為所有基礎數學的代名詞，但在标準的國中和高中代數、微積分初步和微積分課程中，這種數學都被忽略了。在20世紀70年代，唐納德·克努特（Donald Knuth）和他在斯坦福大學的同僚創造了“具體數學”這一名詞（融合了連續數學和離散數學，并且也很具體，不是太抽象），來描述克努特在斯坦福大學教授的課程。後來，“具體數學”成為了他們的一本閱讀起來很愉快的書的标題[1]。正如他們在序言中解釋的那樣，克努特“發現他的技能中缺少一些數學工具，他需要一些數學工具，以便對計算機程式有徹底的、充分的了解，這些數學工具與他在大學裡作為數學專業學生所學的東西完全不同”。
是以，如果你對計算機程式設計感興趣，我們希望本書能讓你成為更好的計算機程式員。如果你對數學更感興趣，你将有充分的機會解決有趣的問題，并在計算機程式中，對其中的一些問題進行模組化。你将熟悉通常國中生和高中生不會接觸到的有趣的數學；你将學會解決真實問題（即你事先并不知道如何解決的問題）；你将感受到數學推理和證明的力量。作為獎勵，你将獲得Python（一種流行的經濟有效的程式設計語言）程式設計的實用技能。
我們選擇Python有幾個原因。首先，Python讓你有機會在互動式環境中，通過即時回報來體驗該語言。其次，Python的文法并不太複雜。再次，Python具有簡單但強大的功能，可用于處理清單和“字典”（映射）。最後，Python易于安裝和使用，它是免費的。當然，還有其他程式設計語言具有類似的屬性，可以滿足我們的需求。歸根結底，重要的不是特定的程式設計語言，而是能夠精确地思考數學知識和計算機程式。
- 這本書在美國高中和大學的相關課程中都獲得了巨大成功；
- 本書文字優美、引人入勝；
教授基本的Python程式設計技能，并提高讀者的計算思維能力和數學水準。
我曾經這樣告訴校長："通常，我們很難去誇獎教材，但這本書的确是一本出色的教材"。
——Michel Paul，美國比佛利山莊高中
我一般不會寫評論，但是這本書值得！實際上，閱讀這本書，你可以學習數學和Python程式設計的方方面面，這在學習更高水準的Python程式設計時将非常有用。我是一名新手程式員，迫切需要這樣一本書！
——Willis Cook，讀者
這是一本精彩的圖書，闡釋了包括數論在内的豐富的數學知識。高中生就能夠了解這些内容，并完成書中的程式設計示例和問題。
——Earl J. Strassberger，美國芝加哥公立學校
樣章試讀：第13章 機率
13.1 引言
當我們擲一對骰子時，得到11點的可能性是多少？7點或11點，哪個更有可能？如果我們擲一對骰子100次，我們大概會得到多少次11點？機率論可以幫助回答這些問題。
事件的機率是介于0和1之間的數字，用于描述當我們多次重複實驗時發生該事件的可能性。0意味着事件永遠不會發生，1表示事件總是發生，0.5表示事件大約在一半情況下發生。
要詢問和回答有關機率的問題，我們首先需要正式描述事件是什麼，然後我們可以找出一種計算事件機率的方法。
假設我們有一個實驗産生一些結果（一個數字、一個事物或一個特定的事物組合）。所有可能結果的集合稱為實驗的“機率空間”。在本書中，我們僅處理具有有限數量的可能結果的實驗。換句話說，機率空間是有限集。例如，當我們擲出表面上有1、2、3、4、5和6點的骰子時，有6種可能的結果，是以機率空間是一組6個元素的集合，{1, 2, 3, 4 , 5, 6}。
“事件”被定義為機率空間的子集，它由滿足特定标準的所有“有利”結果組成。我們可以定義以下事件：骰子上的點數為3或更大。此事件可以描述為集合{3, 4, 5, 6}。事件的其他例子：骰子上的點數是偶數，{2, 4, 6}；點數是6，{6}。在後一個例子中，事件是僅有一個元素的機率空間的子集。
13.2 通過計數計算機率
如果機率空間中的所有結果可能性相等，事件的機率被定義為有利結果的數量與所有可能結果的數量的比值。
例1
當我們擲出表面上有1、2、3、4、5和6點的骰子時，獲得3點或更大點的機率是多少？
解
有6種可能的結果，6種結果的可能性都是相等的。其中4種結果點數為3或以上，即{3, 4, 5, 6}。是以，獲得3點或更大點的機率是
=
。
✦ ✦ ✦
當我們擲一對骰子時，情況稍微複雜一些。這種情況下我們如何定義機率空間？第一個骰子和第二個骰子上的任何點組合都是不同的結果。那麼機率空間将由36個元素組成（見圖13-1）。同樣，36種不同結果中的每一種的可能性都是相等的。
圖13-1 擲出兩個骰子的可能結果的機率空間有36個元素，第一個和第二個骰子上所有可能的點的組合
例2
當我們擲一對骰子時，骰子上的點總和是11的機率是多少？總和是7的機率是多少？
解
得到11的機率可以計算為2/36 = 1/18，因為正好有2個可能的結果産生總和11點，即5 + 6和6 + 5。得到7的機率是6/36 = 1/6，因為有6個可能的結果得到總和7點1 + 6、2 + 5、3 + 4、4 + 3、5 + 2和6 + 1（見圖13-2）。
✦ ✦ ✦
當整個機率空間被分成幾個非重疊事件時，這些事件的機率和總是1。
圖13-2展示了一個例子。
圖13-2 在一對骰子上獲得一定點數的機率
你可能想知道：如果我們對兩個骰子上的點數之和感興趣，為什麼不選擇一個隻包含11個元素的簡單機率空間，可能的總和為2,3,…,12？從技術上講，我們可以這麼做，但這樣的機率空間不會非常有用。因為正如我們所看到的，這個機率空間中的不同結果具有不同的機率。這個機率空間無助于我們計算每個結果的機率，也無法計算各種其他事件的機率。
當我們為問題構造機率空間時，總是嘗試選擇一個所有結果具有相同機率的空間。
在所有結果具有相同機率的空間中，每個結果的機率是1/n，其中n是所有可能結果的數量。然後，我們可以簡單地計數滿足事件标準的結果數量，并将該計數除以n，進而求出事件的機率。
✦ ✦ ✦
有時我們可以針對相同的情況，以不同的方式定義機率空間，但對于相同僚件的機率，我們應該得到相同的結果。
例3
如果我們從52張牌中随機抽出2張牌，抽到2張A的機率是多少？
解
我們可以将機率空間定義為所有牌對的集合（忽略牌對中兩張牌的順序）。有
種方法可以從52張牌中選擇一對牌。有
種方法可以從4個A中選擇一對A（有利的結果）。答案是
。
另解：我們可以将機率空間定義為所有有序牌對的集合。這個空間中的元素數量是
，有序的A對的數量是
。我們得到了同樣的答案：
。
例4
如果我們抛3次硬币，那麼出現剛好2次正面朝上的機率是多少？
解
這裡的機率空間是{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}，期望的結果是{HHT, HTH, THH}。答案是3/8。
第13.2節練習
1．如果随機猜測5個答案選項的多項選擇題，猜中正确答案的機率是多少？ ✔
2．如果你擲2個骰子，那麼點數的總和大于7的機率是多少？
3．你必須在36個方格的網格上标記正确的6個方格。你标記正确的機率是多少？✔
4．如果你抛硬币5次，出現至少4次反面的機率是多少？
5．輪盤中有36個槽的編号為1～36，另有2個槽，标記為0，表示對于獲勝。36個槽18個紅色和18個黑色交替，0是綠色。如果你選擇17号槽，獲勝的機率是多少？如果你選擇“紅色”，獲勝的機率是多少（如果球擊中任何紅色位置你就赢了）？ ✔
6．從前50個正整數中随機選擇的數字，被3整除的機率是多少？
7．随機選擇兩位正整數（即10到99之間的整數），兩個數字相同的機率是多少？
8．■編寫一個Python程式，計算在擲3個骰子時獲得不同點數總和（3～18）的機率。什麼點數總和出現機率最高？ »提示：初始化一個計數清單，全部設定為0，然後在三個骰子上生成所有可能的點組合，并為每個組合增加适當的計數。«
13.3 更多通過計數的機率
我們知道，要計算事件的機率，必須計算所有“有利”結果的數量，并将它除以所有可能結果的數量。當我們進行計數時，可以回顧在第12章的組合學問題中學到的所有技巧。
例1
如果5張牌是從52張牌中随機發出的，獲得“兩對”的機率是多少（即一對牌有一樣的牌面數字，另一對牌有一樣的牌面數字，剩下那張牌有不一樣的牌面數字）？
解
發5張牌的方法總數是
。為了形成“兩對”，讓我們首先從13種牌面大小中選擇2種作為對子，有
種辦法。對于每一種牌面數字，有6種方法可以從4張牌中選擇2張。最後有44種方法可以選擇剩下的牌（從剩下的11種牌面數字選擇）。答案是
。
例2
袋中有60個果凍豆，其中，15個是紅色，15個是藍色，15個是綠色，15個是黃色。丹尼已經拿出1個紅色的果凍豆和1個藍色的果凍豆，袋子裡還剩58個果凍豆。如果丹尼随機再拿出3個果凍豆，他最終得到3個顔色相同的果凍豆的機率是多少？
解
我們将使用計數的加法和乘法規則。對于有利的結果，有4種互相排斥的可能性：丹尼最終會得到3個紅色、3個藍色、3個綠色或3個黃色的果凍豆。要得到3個紅色的果凍豆，他需要選擇袋子裡剩下的14個紅色果凍豆中的2個，有
種辦法。然後他需要再選擇一個不是紅色的果凍豆，有
種辦法。是以，有
種方法拿5個果凍豆，其中3個是紅色。拿出3個藍色果凍豆的方法總數相同。要獲得3個綠色果凍豆，丹尼需要在15個綠色果凍豆中選擇3個，有
種方法。同樣，有455種方法可以選擇3個黃色果凍豆。有利結果的總數是4004 + 4004 + 455 + 455 = 8918。所有可能結果的總數是從58個果凍豆中選擇3個果凍豆的方法的數量，即
。獲得3個相同顔色的果凍豆的機率是
。
✦ ✦ ✦
當我們将機率計算為有利結果的數量與所有可能結果的數量的比率時，機率空間中的所有可能結果具有相等的機率是非常重要的。如果不是這樣，那麼簡單比率方法将導緻答案錯誤。
例3
考慮兩個玩家之間的遊戲。每個玩家最多擲3次硬币，誰先獲得正面誰勝。如果他們第一次得到硬币的同一面，就會進行一個決勝局；如果再次得到相同的一面，他們會進行另一個決勝局。第一個玩家獲勝的機率是多少？
解
在一個不成熟的方法中，我們會考慮所有可能的遊戲過程：
有7種可能的方式玩家A會赢，有7種可能的方式玩家B會赢。遊戲有8種可能的方式以平局結束。
似乎玩家A獲勝的機率是
。答案錯誤！上面列出的22種可能的遊戲過程，不是等可能的。為了看到這一點，讓我們允許每個玩家擲3次，無論發生何種情況，最後才決定勝利者。
這裡*是一個通配符，可以代表硬币的任何一面。這個新的機率空間定義恰當，所有結果都是等可能的，舊的機率空間沒有這個屬性。正如我們現在所看到的，H/T遊戲的獲勝機率實際上是HH/HT的遊戲的4倍，是HHH/HHT遊戲的16倍。
新機率空間可能的結果總數是
，正确的答案是
。
在這個例子中，我們不必計算所有獲勝組合數。根據玩家的對稱性，有一個快捷方法：結果總數是
，平局遊戲結果的數量是
，是以玩家A獲勝的結果數量是
。
第13.3節練習
1．在一副牌（52張）中獲得“4張同點”撲克牌的機率是多少（同一牌面大小的4張牌加上任意第五張牌）？✔
2．■“皇家同花順”是最好的牌，即同一花色的A、K、Q、J和10。當你從一套标準的52張牌中随機發出5張牌時，獲得皇家同花順的機率是多少？✔
3．■在“十點”基諾遊戲中，你在一張有80個數字的卡片上标記10個“點”（數字），然後對手随機挑選20個數字。要赢得勝利，你需要讓10個數字全被對手數字“擊中”。赢得勝利的機率是多少？（基諾遊戲給玩家帶來了所有遊戲中最小的獲勝機率。）✔
4．■一個袋子中有3個紅色大理石和5個藍色大理石。如果你随機抽出4個，得到2個紅色和2個藍色的機率是多少？
5．◆ 從52張牌中抽牌，直到得到2張牌面數字相同的牌。不超過3張牌就結束的機率是多少？✔
6．◆ 書中的頁面編号為1到96。我們剪下所有頁碼并将它們剪成單獨的數字，從中随機選擇兩個數字，它們的和為10的機率是多少？
7．◆ 将16個撞球随機放入6個口袋中。（假設一個口袋可以容納任意數量的球。）東北角口袋少于3個球的機率是多少？ ✔
8．◆ 随機的21點的3張牌，值為21點的機率是多少？在21點中，每張數字牌按由2到10的面值計數；A算作1或11，你可以選擇一種；其他“圖檔”牌（J、Q或K）計為10。 ✔
13.4 乘法、加法和減法
還記得我們如何使用乘法、加法和減法來計數嗎？當然，在計算“有利”結果和實驗的所有可能結果的數量時，我們可以應用這些方法。但有一條捷徑：我們可以直接對機率應用乘法、加法和減法運算。讓我們從乘法開始。
假設我們有兩個互相獨立的實驗。假設事件A可以在第一個實驗中發生，事件B可以在第二個實驗中發生。A和B在各自實驗中發生的機率是A的機率乘以B的機率。
例1
如果我們連續擲兩次骰子，獲得兩個6的機率是多少？
解
第一次擲骰子得到6的機率是
，第二次得到6的機率是
。連續獲得兩個6的機率是
。注意，擲兩次骰子與同時擲兩個一樣的骰子相同。
例2
我有3個信封。其中兩個有1美元，第3個是空的。你可以帶走任意兩個信封。你最終得到兩美元的機率是多少？
解
拿第一個信封時，獲得1美元的機率是
。如果你得到第一個1美元，從剩下的兩個信封獲得第二個1美元的機率是
。獲得2美元的機率是
。如果我們假設第一個實驗在第二個實驗之前是成功的，乘法規則仍然有效。這類似于計數組合而沒有重複，正如我們在12.3節中讨論的那樣。
✦ ✦ ✦
機率可以在兩種情況下相乘：當事件彼此獨立時，如上面的例1所示；當基于第一事件已經發生的假設成立計算第二事件的機率時 ，如上面的例2所示。
例3
在加勒比海的尼維斯島上，平均每年降雨45天。連續兩天下雨的機率是多少？
解
這是一個棘手的問題。你可能想應用乘法規則，并說機率是
或
。但是，乘法規則要求事件彼此獨立地發生，天氣情況不是這樣，在尼維斯島，雨季是9月和10月，在這兩個月裡連續兩天降雨很有可能。為了論證這一問題，假設在某個神秘島上，45個雨天總是在9月1日到10月15日之間，并且在一年中的其餘時間裡根本不會下雨。那麼，如果我們随機選擇一年中連續兩天，則兩天都會下雨的機率是
。如果沒有關于全年雨天分布的更多資訊，我們無法回答最初關于尼維斯島的問題。
✦ ✦ ✦
當我們需要找到可以分成兩個無重疊事件的事件機率時，使用加法。
例4
在擲骰子的遊戲中，你擲兩個骰子。如果你擲到7或11，你就赢了；如果你擲到2、3或12，就輸了；其他情況遊戲繼續。在第一次擲骰子上赢或輸的機率是多少？
解
在第一次擲骰子時獲勝的機率是
（見圖13-2）；在第一次擲骰子時失敗的機率是
。（但這不是遊戲的結束，獲勝規則是這樣的：最終在遊戲中赢得超過一半的比賽。）
例5
在“随機行走”中，你可以随機選擇下一步行走的方向（前進、後退、左或右），它們具有相同的機率。兩步後傳回起始位置的機率是多少？
解
有以下4個序列在兩步後可傳回起始位置，{前,後}、{後,前}、{左,右}和{右,左}。每個序列發生的機率是
。4個序列中的任何一個發生的機率是
。
✦ ✦ ✦
如果事件發生的機率為p，則不發生同一事件的機率為1−p。
例6
戴夫擊出本壘打的機率是0.13。戴夫不會擊出本壘打的機率是多少？
解
例7
艾米莉平均每15次用飛镖擊中“靶心”1次。艾米莉在3次嘗試中至少會擊中靶心1次的機率是多少？
解
假設艾米莉擊中靶心的機率為p，錯過靶心的機率是
。則艾米莉連續3次錯過靶心的機率是
，3次嘗試中至少1次擊中靶心的機率是
。這裡
。答案是
。
第13.4節練習
1．連續3次擲骰子都得到3的機率是多少？ ✔
2．在Scrabble中，有98個寫有字母的方塊。有2個B、9個A和6個T。如果你從盒子中随機拿出3個方塊，每次将方塊放回到盒子中，按順序獲得B、A、T的機率是多少？
3．擲3次骰子而從未得到6的機率是多少？至少得到一次6的機率是多少？ ✔
4．■ 如例5所述，在随機行走時，你在4步後傳回起始位置的機率是多少？
5．■在壁球比賽中，一連串連續的擊球被稱為1個回合。當你發球時，要得分，你需要赢得該回合。如果你的對手發球，赢得1個回合隻是給你下一個發球的權利。如果艾莉在她發球時，平均赢得10個回合中的4個；在她的對手發球時，赢得10個回合中的3個。那麼從對手發球開始，2回合後，艾莉得一分（一球一分）的機率是多少？ ✔
6．◆ 練習題5描述了壁球得分的規則。不管是誰發球，蘇珊平均在3個回合中有2個回合擊敗吉米。如果蘇珊開始發球，她在3個回合中赢得下一分的機率是多少？在5個回合中蘇珊最終會赢得下一分的機率是多少？ »提示：在情況下，我們得到一個無窮極數，但我們已經知道如何處理它……« ✔
7．◆ 如果選手發球，并且選手的對手和選手水準相當（也就是說，每個選手赢得一個回合的機率是0.5，無論誰發球），那麼選手在壁球中赢得下一分的機率是多少（參見練習題6）？
8．◆ 一個飛镖靶有20個外部扇區，20個内部扇區和一個叫“靶心”的中心。如果平均而言，在30次嘗試中擊中靶心一次，内部扇區5次（在它們中間等可能），外部扇區20次，完全錯過了4次。那麼連續兩次擊中同一扇區（或靶心）的機率是多少？✔
9．◆ 在某抽獎活動中，你可以從42個數字中選擇6個數字。如果你的數字與計算機抽出的數字相比對，那麼你将獲得累積獎金。計算機還抽出第七個“鼓勵”數字。如果你沒有中獎，但是你的6個數字與電腦抽取的7個數字（包括鼓勵數字）中的任意6個數字相比對，你将獲得10000美元的安慰鼓勵獎。還有其他獎品，但它們相對較小。隻有當你的“平均赢額”（中獎機率乘獎金的大小，加上安慰鼓勵獎的機率乘以鼓勵獎金的大小）超過票價時，你才決定玩遊戲。如果一張票的價格為1.00美元，那麼累積獎金達到多少才值得你玩？
10．◆ 一個棋子從棋盤左下角的黑色方格開始移動。在每次移動中，棋子以相同的機率向上或向右移動一個方格，它到達右邊或頂邊時停止。棋子最後在黑色方格上的機率是多少？ »提示：擴充棋盤，使它形成一個等邊直角三角形，直角在左下角，并将所有路徑延伸到它的斜邊，使所有路徑的長度相等。«
13.5 僞随機數
計算機應該是可預測的，從相同的位置開始，執行相同的步驟，你應該得到相同的結果。但有時我們希望計算機随機行動。例如，在遊戲和随機過程的計算機模拟中，随機行動是有用的。
典型的程式設計語言具有生成“随機”數字的庫函數。這些數字是利用某種算法在軟體中生成的，是以它們并非真正随機，但它們近似于随機行為。這些數字稱為“僞随機數”。
Python庫有一個random子產品，它有許多生成和傳回随機數的函數。要擷取随機整數r，a
r
b，請将函數randint導入random子產品，并調用randint(a, b)。例如：
>>> from random import randint
>>> randint(1,3)
2
>>> randint(1,3)
3
>>> randint(1,3)
3
>>> randint(1,3)
1
>>> randint(1,3)
2
（你的顯示可能會有所不同，因為randint會傳回僞随機數。）
來自同一子產品的random函數傳回一個浮點型數x，0.0
x＜1.0。例如：
>>> from random import random
>>> random()
0.21503763019111777
>>> random()
0.80958843480468412
另一個choice函數從字元串（或元組、清單或任何其他“序列”中的元素）中選擇随機字元并傳回。例如：
>>> from random import choice
>>> choice('ABC')
'B'
>>> choice('ABC')
'A'
>>> choice('ABC')
'A'
shuffle函數以随機順序重新排列清單的元素。例如：
>>> from random import shuffle
>>> lst = [1, 2, 3, 4, 5]
>>> shuffle(lst)
>>> lst
[5, 2, 3, 1, 4]
✦ ✦ ✦
有時，理論上的解決方案為我們提供了一個公式，但數字可能太大或難以計算。于是，計算機可以提供幫助，通過計算或對随機過程模組化并觀察結果。這種模型被稱為“蒙特卡羅模拟”。
例
在25人中，更有可能的是有兩個人同一天生日，還是每個人的生日在不同的一天？
解
我們假設一個生日可以是365天中的任何一天（忽略閏年）。一種方法是通過程式設計進行蒙特卡羅模拟，生成一組随機的25個生日，并檢查是否有兩個生日在同一天。比方說，重複10,000次，并計數有多少組有兩人同一天生日，有多少組沒有。這個程式留給你作為練習（見練習題6）。
解決生日問題的另一種方法是使用我們學到的知識，在理論上計算機率。第一個人的生日可以是365天中的任意一天，第二個人也是，依此類推。利用乘法規則，我們發現有36525種生日的可能排列。利用沒有重複的乘法規則，我們得出結論，當所有25個人生日都不同時，有
種排列。是以，所有人生日不同的機率是
，而至少兩個人生日相同的機率是
。
現在讓我們針對n個人的情況解決同樣的問題。不需額外的工作，我們就能夠得到“交叉點”：當機率大于1/2時的人數。請嘗試猜測這個數字，這隻是為了檢查一下你的直覺！
似乎我們必須處理分子和分母非常大的數字。例如，36525有65位數字。（我們用Python發現了這個數字。）Python支援大整數，其中一個數字可以有任意長度，僅受計算機記憶體大小的限制。當正常的4位元組int值超出範圍時，Python會自動切換到使用更長的值。是以在Python中，我們可以直接計算分數的分子和分母，取其比值并完成。然而，在其他語言中，處理非常大的數字可能涉及更多工作。幸運的是，我們可以更簡便地處理這個問題，不用大整數。請注意，我們可以将比率分成單個分數的乘積：
。這樣很容易将每個分數計算為一個浮點型資料。在練習題5中，你将完成這個程式。
第13.5節練習
1．編寫并測試一個Python函數，該函數從52張牌中随機選擇5張牌。每張牌由一對資料（一個元組）描述，儲存牌的花色（“S”“H”“D”“C”表示黑桃、紅桃、方塊、草花）和牌面數字（1到13）。 ✔
2．假設你有一個Python函數random_letter，它傳回字母表的一個随機字母（26個字母的機率大緻相等）。random_letter連續傳回3個元音字母（AEIOU）的機率是多少？ ✔
3．編寫一個Python函數random_letter，如練習題2所述。運作3次以檢視是否得到連續3個元音。重複100,000次，統計連續3個元音的次數，并估計這種事件發生的機率。将你的結果與你在練習題2中獲得的理論機率進行比較。
4．編寫一個使用蒙特卡羅方法估算 的程式。将一百萬個随機（虛拟）點“投擲”到一個機關正方形中，并計數它們與原點的距離小于1的點的數量。
5．■ 使用本節中描述的理論方法，編寫一個程式，輸出n個人中至少有兩個人具有相同生日的機率，n取值為1到50，不使用太大的整數。這個程式隻有幾行代碼。輸出應如下所示：
1: 0.000
2: 0.003
3: 0.008
...
48: 0.961
49: 0.966
50: 0.970
注意“OBOBs”（off-by-one bugs，差1錯誤），當程式中的循環運作少一次或多一次時，我們就說發生了這種錯誤。根據輸出結果确定，機率大于0.5的n的值。
6．■編寫一個程式，實作蒙特卡羅模拟。編寫一個生成n個随機生日清單的函數（數字從1到365），如果清單中的所有數字都不同，則傳回True。盡量多地調用此函數，以計算n中至少有兩個人具有相同生日的機率。将你的結果與練習題5中獲得的理論結果進行比較。 »提示：找出生成的數字是否有重複的簡單方法是，配置設定365個計數變量，并針對每個随機數遞增适當的計數變量，然後檢查是否有任何計數變量大于1。«
7．■在海龜繪圖中，繪制一個以原點為中心的半徑為100的圓，然後将海龜歸回原點（到原點）。模拟随機行走，在每次移動中，将海龜的方向設定為0度、90度、180度或270度，以相等的機率随機選擇，然後向前移動20。保持筆落下以檢視海龜的路徑，計算并報告海龜離開圓圈所需的步數。 »提示：turtle的函數distance (x,y)傳回從目前海龜位置到點(x, y)的距離。«
8．■下面的函數從序列s中傳回一個随機的正數：
def positive_choice(s):
lst = [x for x in s if x > 0]
if len(lst) > 0:
return choice(lst)
清單中的每個正數有相同的機率被選中。重寫此函數，不從s建立任何臨時正數清單或集合，也不提前計算它們的數量。 »提示：假設r儲存從s的前k個正數中随機選擇的一個正數，從k = 0和r = None開始。當你取得下一個正數x時，你可以保持r不變或用x替換r。用x替換r的機率應該是多少？（你永遠不會知道：x可能是s中的最後一個正數。你需要給它一個公平的機會……）«
在(−1, 1, 2, 0, 3, −2, 4, 5, −6)上運作你的positive_choice函數，比方說10000次，進而測試它，并計算每個數字1、2、3、4、5的傳回次數。所有數字的傳回次數應該在2000左右，計數與2000的差距不大于120。 ✔
9．■本題探讨将多個随機數加在一起時會發生什麼。寫一個簡短的程式，幫助你做到這一點。建立一個包含100個計數器的清單：counters = 100*[0]。運作以下程式：取100個随機數r，0
r＜1（由random函數傳回）的總和，将和截斷為整數，得到i，并遞增計數器counters[i]。重複這些步驟，比如重複2000次。然後在計數器中将值顯示為海龜繪圖中的垂直線段（一種簡單的條形圖）。生成的圖是什麼樣的？
»提示：
for i in range(100):
x = x_offset + x_scale*i
y = y_scale*counters[i]
...
使用合理的偏移量和縮放比：
x_offset, y_offset = -200, -100
x_scale, y_scale = 5, 1
使用goto(x, y)繪制。
13.6 複習
本章介紹的術語。
機率
機率空間
獨立事件
機率的乘法規則
機率的加法和減法規則
蒙特卡羅模拟
随機行走
本章介紹的一些Python特性。
from random import randint, random, choice, shuffle
randint(m, n)
random()
choice(s)
shuffle(lst)