• <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)
            亚洲中文字幕无码久久2017| 国产精品岛国久久久久| 色偷偷88欧美精品久久久| 99久久这里只精品国产免费| 亚洲香蕉网久久综合影视 | 久久久久久久久波多野高潮| 久久久久免费精品国产| 久久99精品国产一区二区三区| 国产免费福利体检区久久| 伊人久久大香线蕉亚洲五月天| 秋霞久久国产精品电影院| 久久综合狠狠色综合伊人| 久久久久国产日韩精品网站| 日韩精品无码久久久久久| 久久黄视频| 热99re久久国超精品首页| 午夜欧美精品久久久久久久| 精品无码久久久久久久久久| 久久久久人妻一区精品色| 亚洲欧洲精品成人久久奇米网| 久久精品国产精品亜洲毛片| 国产毛片欧美毛片久久久| 久久精品亚洲乱码伦伦中文| av无码久久久久久不卡网站| 久久综合九色综合网站| 欧美大战日韩91综合一区婷婷久久青草| 久久99精品久久只有精品| 久久人妻AV中文字幕| 日本欧美国产精品第一页久久| 国产日韩欧美久久| 青青热久久综合网伊人| 69久久夜色精品国产69| 久久精品a亚洲国产v高清不卡| 99精品久久久久久久婷婷 | 精品国际久久久久999波多野| 亚洲精品国产综合久久一线| 国内精品久久久久影院网站| 久久久精品午夜免费不卡| 久久se精品一区二区| 亚洲国产天堂久久综合网站| AA级片免费看视频久久|