這個(gè)是算法導(dǎo)論習(xí)題5.2-4
n個(gè)顧客在進(jìn)酒店之前,都會把自己的帽子給前臺服務(wù)員保管。每個(gè)顧客在離開時(shí),前臺服務(wù)員又會隨機(jī)地挑選一個(gè)帽子給他。問:最終,能拿到自己帽子的顧客們期望數(shù)是多少
首先從簡單情況入手,對于n=2 n=3 很容易求出 結(jié)果res=1;
對于n>=4,我們嚴(yán)格的用概率方法來推導(dǎo)一下!
首先定義P(n)為伯努利放錯(cuò)信的問題的答案。
P_n=n!\sum_{i=2}^{n}\frac{(-1)^i}{i!}

然后對于n個(gè)人中i個(gè)人匹配正確這個(gè)事件的數(shù)目是C(n,i)P(i)
總共有n!中事件,2^n種情況,(可以把人看成是10串,拿到自己帽子的為1)
所以 答案就是
(n-i)*C(n,i)P(i) /n!求和
整理一下是
\sum_{i=2}^{n-1}\frac{n-i}{(n-i)!}\sum_{j=2}^{i}\frac{(-1)^j}{j!}+\frac{1}{(n-1)!}
可以證明這個(gè)等式等于1
所以答案是1