提升程式設計師的面試力 - Ch6 - 數學和邏輯謎題

機率

A 和 B 的機率

$$
P(A \cap B)=P(同時發生 A 及 B 的機率) \
=P(發生 A 的情況下，發生 B 的機率)=P(B \mid A)P(A) \
=P(發生 B 的情況下，發生 A 的機率)=P(A \mid B)P(B) \
$$

由上可以得知

$$
P(A \mid B)=\frac{P(B \mid A)P(A)}{P(B)}
$$

這個式子為 貝氏定理(Baye’s Therem) 的特例表示

A 或 B 的機率

$$
P(A \cup B)=P(A)+P(B)-P(A \cap B)
$$

獨立(Independent)

A 與 B 互為獨立事件表示

發生 A 的機率與 B 無關
發生 B 的機率與 A 無關

所以

$$
P(B \mid A) = P(B) \
P(A \mid B) = P(A)\
$$

則由 $P(A \cap B)$ 的列式我們可以得知

$$
P(A \cap B) \
=P(B \mid A)P(A)=P(B)P(A) \
=P(A \mid B)P(B)=P(A)P(B) \
$$

互斥(Mutually Exclusive)

A 與 B 互為互斥事件表示

只要發生 A ，就不會發生 B
只要發生 B ，就不會發生 A

意思就是說

$$
P(A \cap B) = 0
$$

則由 $P(A \cup B)$ 的列式我們可以得知

$$
P(A \cup B) \
=P(A)+P(B)-P(A \cap B) \
=P(A)+P(B)
$$

例題 6.6 ~ 6.10

6.6

題目

有一群人住在一個島上，有一個訪客帶著奇怪的命令來到島上：所有藍眼睛的人都必須盡快離開這個島，每天晚上八點就一班班機起飛。每個人都能看到別人眼睛的顏色，但他們不知道自己眼睛的顏色（別人也不能告訴他們）。此外，他們不知道總共多少人有藍眼睛，但他們知道至少有一人有藍眼睛。這些藍眼睛的人需要多少天才能離開？

6.7

題目

大災難後的時代，統治世界的女王非常關心出生率。因此，他下令所有家庭都必須要有一個女兒，否則他們將面臨巨額罰款。如果所有家庭都遵守此一政策，也就是說直到他們有一個女兒前，都必須繼續生孩子，再生出女兒的那一刻就立即停止再生孩子，那麼新一代的性別比例會是多少？（假設生男女的幾率相等）請用邏輯解決這個問題，並用程式模擬

6.8

題目

有一座 100 層樓的建築，如果雞蛋從地 N 層或以上掉下來它會破掉。如果他從下面的任何一層掉下來，都不會破。而我們只有兩個雞蛋，請求出 N ，同時最小化最壞情況下的雞蛋落下次數

6.9

題目

在走廊有 100 個關閉的儲物櫃。有一個人從打開全部 100 個儲物櫃開始。下一輪，他會每隔兩個儲物櫃關閉櫃門。然後再下一輪，他會每隔三個儲物櫃切換一次開關狀態，這個過程會持續 100 次。這樣，在第 i 輪的時候，這個人會每隔 i 個儲物櫃切換櫃們的狀態。當他在走廊上做到第 100 次時，他只會切換 100 號儲物櫃的門，請問還有多少儲物櫃是開著的？

6.10

題目

您有 1000 瓶汽水，但其中只有一瓶是有毒的。您有十個可以用來檢測毒藥的試紙，一滴毒藥就會使試紙永久呈現陽性。您可以一次在是紙上放置任意數量的液滴，並且您可以根據需要，多次重複使用試紙（只要測試結果是無毒的）。但是，您每天只能執行一次測試，而且每次測試需要七天反應時間才能得知結果。請問如何在最短的時間內找出有毒的瓶子呢？