• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2012年11月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678

            統(tǒng)計(jì)

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            Hat-Check problem 帽子保管問題

            這個(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!}

            SLE[7}IS3_~VFKO3}MB71JL

            然后對于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)!}

             

            U~HZ[AVXP)X2TC`4}(3J[XV
            可以證明這個(gè)等式等于1
            所以答案是1

            posted on 2010-10-17 15:21 Sosi 閱讀(1632) 評論(0)  編輯 收藏 引用 所屬分類: Courses

            統(tǒng)計(jì)系統(tǒng)
            色婷婷综合久久久久中文一区二区 | 中文字幕久久精品无码| 久久综合亚洲鲁鲁五月天| 久久天天躁狠狠躁夜夜躁2014| 一本一本久久a久久综合精品蜜桃| 精品久久久久久久无码| 久久人妻少妇嫩草AV无码蜜桃| 欧美精品乱码99久久蜜桃| 狠狠狠色丁香婷婷综合久久五月| 久久久久黑人强伦姧人妻| 麻豆成人久久精品二区三区免费| 久久99久久无码毛片一区二区| 久久精品青青草原伊人| 免费观看成人久久网免费观看| 伊人热热久久原色播放www| 日本久久久精品中文字幕| 久久久精品人妻一区二区三区蜜桃| 中文字幕一区二区三区久久网站| 亚洲精品无码久久久久去q| 国内精品久久久久久久影视麻豆 | 国产精品久久99| 久久久久久国产精品美女| 日本精品一区二区久久久| 亚洲国产精品久久66| 亚洲国产一成人久久精品| 香蕉久久夜色精品国产2020 | 无码精品久久久久久人妻中字| 国产精品免费久久| 国产精品成人99久久久久91gav| 亚洲欧美成人综合久久久| 久久精品成人一区二区三区| 亚洲乱亚洲乱淫久久| 99久久www免费人成精品| 国产91久久综合| 久久久久国产精品麻豆AR影院| 国产成人精品久久| 精品99久久aaa一级毛片| 国产国产成人久久精品| 久久精品亚洲福利| 一本色道久久综合狠狠躁篇| 欧美伊人久久大香线蕉综合|