• <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>

            公告

            記錄我的生活和工作。。。
            <2011年10月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統(tǒng)計(jì)

            • 隨筆 - 182
            • 文章 - 1
            • 評(píng)論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(lèi)(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            最佳約會(huì)策略(在線(xiàn)算法)

            問(wèn)題: 有n個(gè)數(shù)字,要求你在線(xiàn)的選擇其中一個(gè)最大的,在選擇第i個(gè)之前,你知道前i-1次的數(shù)字是什么,但是無(wú)法知道你將要選擇的數(shù)字和以后待選的數(shù)字的大小。

             

            一個(gè)很自然的策略是選定一個(gè)K,先看一下前k個(gè)的大小,不做任何選擇,然后繼續(xù)看,知道遇到一個(gè)比這之前的k個(gè)人還好。可以證明k= n/e 的時(shí)候,能夠獲得最好的選擇,能夠選擇到最大的那個(gè)。證明其實(shí)是比較簡(jiǎn)單的。假設(shè)在我們的某次選擇中,選擇第i個(gè)是最優(yōu)選擇,那么很顯然第i個(gè)必須是這n個(gè)數(shù)中最大的,那么此時(shí)的概率是1/n,第二個(gè)要求是前k個(gè)數(shù)中存在這i個(gè)數(shù)中次大的數(shù),否則是不會(huì)選擇第i個(gè)的。此時(shí)的概率是k/i-1,所以把第k個(gè)到第n個(gè)累加起來(lái)就OK了,然后取得次數(shù)的最大數(shù),可以計(jì)算獲得k=n/e。

             

            很顯然這個(gè)問(wèn)題是一個(gè)在線(xiàn)算法的問(wèn)題,無(wú)法預(yù)知之后的情況,邊輸入邊進(jìn)行處理。而離線(xiàn)算法是要求當(dāng)輸入完成之后,然后進(jìn)行輸出。 在線(xiàn)算法的目的就是能夠達(dá)到離線(xiàn)算法的一樣好的效果。


            題目來(lái)源:

            http://zhiqiang.org/blog/science/tcs-classroom-notes-the-best-dating-strategy.html
            http://www.cnblogs.com/fll/archive/2008/06/01/1211569.html

            posted on 2011-10-26 21:44 Sosi 閱讀(596) 評(píng)論(0)  編輯 收藏 引用


            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            統(tǒng)計(jì)系統(tǒng)
            亚洲精品美女久久777777| 久久久久久无码国产精品中文字幕| 久久久久女教师免费一区| 蜜桃麻豆www久久国产精品| 久久久国产99久久国产一| 狠狠色综合网站久久久久久久高清 | 狠狠色婷婷综合天天久久丁香| 国产精品久久亚洲不卡动漫| 狠狠色伊人久久精品综合网| 久久精品国产99国产精品导航 | 精品人妻伦九区久久AAA片69| 久久婷婷五月综合色奶水99啪| 亚洲国产精品无码久久久秋霞2 | 国产午夜电影久久| 久久人做人爽一区二区三区 | 久久精品一区二区| 国产毛片欧美毛片久久久| 久久久中文字幕| 午夜不卡久久精品无码免费| 国产成人精品久久亚洲高清不卡 | 蜜桃麻豆WWW久久囤产精品| 国内精品久久久久久麻豆| 久久精品国产男包| 无码乱码观看精品久久| 久久国产视屏| 99久久99久久精品国产片果冻| 久久国产欧美日韩精品| 欧美成人免费观看久久| 精品久久综合1区2区3区激情| 国产亚洲精品自在久久| 久久综合狠狠综合久久综合88| 久久精品国产欧美日韩| 久久国产精品免费| 久久久中文字幕| 久久国产一区二区| 久久久中文字幕| 久久午夜电影网| 国产韩国精品一区二区三区久久| 人妻精品久久无码专区精东影业| 亚洲午夜福利精品久久| 青青久久精品国产免费看|