Problem 10491 Cows and Cars，牛與車

此題為機率題，找出其中公式就可解此題。舉幾個例子：

牛數量	車數量	開門數	門總數
2	1	1	3

以上資料來看，
先選牛的機率 2 / 3，換選車機率 1 / 1 (因為會開一個門是牛的門，規定又說一定要換門)，所以機率 2 / 3 * 1 = 2 / 3。
先選車機率 1 / 3，換選車機率 0 / 1 (一開始選車，再開一個是牛的門，規定一定要換門)，所以機率 1 / 3 * 0 = 0。
一定要換門的機率為 2 / 3 + 0 = 2 / 3。

牛數量	車數量	開門數	門總數
5	3	2	8

先選牛的機率 5 / 8，換選車機率 3 / 5，所以機率 5 / 8 * 3 / 5 = 15 / 40。
先選車機率 3 / 8，換選車機率 2 / 5 ，所以機率 3 / 8 * 2 / 5 = 6 / 40。
一定要換門的機率為 15 / 40 + 6 / 40 = 21 / 40。
最後推導公式：

牛數量	車數量	開門數	門總數
NCOWS	NCARS	NSHOW	DOORS (= NCOWS + NCARS)

先選牛的機率 NCOWS / DOORS，換選車機率 NCARS / (DOORS - NSHOW - 1)，所以機率 NCOWS * NCARS / (DOORS * (DOORS - NSHOW - 1))。
先選車機率 NCARS / DOORS，換選車機率 (NCARS - 1) / (DOORS - NSHOW - 1)，所以機率 NCARS * (NCARS - 1) / (DOORS * (DOORS - NSHOW - 1))。
一定要換門的機率為 (NCOWS + NCARS - 1) * NCARS / (DOORS * (DOORS - NSHOW - 1))。

By David.K

p10491題目連結
回ACM題庫目錄
回首頁