• <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>
            JulyRina's blog
            welcome to July Rina's blog
            posts - 22,comments - 1,trackbacks - 0
            (一)巴什博奕(Bash Game):只有一堆n個物品,兩個人輪流從這堆物品中取物,規(guī)定每次至少取一個,最多取m個。最后取光者得勝。
            顯然,如果n=m+1,那么由于一次最多只能取m個,所以,無論先取者拿走多少個,后取者都能夠一次拿走剩余的物品,后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則:如果n=(m+1)r+s,(r為任意自然數(shù),s≤m),那么先取者要拿走s個物品,如果后取者拿走k(≤m)個,那么先取者再拿走m+1-k個,結(jié)果剩下(m+1)(r-1)個,以后保持這樣的取法,那么先取者肯定獲勝。總之,要保持給對手留下(m+1)的倍數(shù),就能最后獲勝。
            即,若n=k*(m+1),則后取著勝,反之,存在先取者獲勝的取法。
            n%(m+1)==0. 先取者必敗。
            (二)威佐夫博奕(Wythoff Game):有兩堆各若干個物品,兩個人輪流從某一堆或同時從兩堆中取同樣多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝。
            這種情況下是頗為復(fù)雜的。我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數(shù)量并稱其為局勢,如果甲面對(0,0),那么甲已經(jīng)輸了,這種局勢我們稱為奇異局勢。前幾個奇異局勢是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
            可以看出,a0=b0=0,ak是未在前面出現(xiàn)過的最小自然數(shù),而 bk= ak + k,奇異局勢有
            如下三條性質(zhì):
            1。任何自然數(shù)都包含在一個且僅有一個奇異局勢中。
            由于ak是未在前面出現(xiàn)過的最小自然數(shù),所以有ak > ak-1 ,而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性質(zhì)1。成立。
            2。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨?
            事實(shí)上,若只改變奇異局勢(ak,bk)的某一個分量,那么另一個分量不可能在其他奇異局勢中,所以必然是非奇異局勢。如果使(ak,bk)的兩個分量同時減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢。
            3。采用適當(dāng)?shù)姆椒ǎ梢詫⒎瞧娈惥謩葑優(yōu)槠娈惥謩荨?
            假設(shè)面對的局勢是(a,b),若 b = a,則同時從兩堆中取走 a 個物體,就變?yōu)榱似娈惥謩荩?,0);如果a = ak ,b > bk,那么,取走b - bk個物體,即變?yōu)槠娈惥謩荩蝗绻?a = ak , b < bk ,則同時從兩堆中拿走 ak - ab - ak個物體,變?yōu)槠娈惥謩荩?ab - ak , ab - ak+ b - ak);如果a > ak ,b= ak + k,則從第一堆中拿走多余的數(shù)量a - ak 即可;如果a < ak ,b= ak + k,分兩種情況,第一種,a=aj (j < k),從第二堆里面拿走 b - bj 即可;第二種,a=bj (j < k),從第二堆里面拿走 b - aj 即可。
            從如上性質(zhì)可知,兩個人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝;反之,則后拿者取勝。
            那么任給一個局勢(a,b),怎樣判斷它是不是奇異局勢呢?我們有如下公式:
            ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...,n 方括號表示取整函數(shù))
            奇妙的是其中出現(xiàn)了黃金分割數(shù)(1+√5)/2 = 1。618...,因此,由ak,bk組成的矩形近似為黃金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1+ j + 1,若都不是,那么就不是奇異局勢。然后再按照上述法則進(jìn)行,一定會遇到奇異局勢。
            (三)尼姆博奕(Nimm Game):有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個,多者不限,最后取光者得勝。
            這種情況最有意思,它與二進(jìn)制有密切關(guān)系,我們用(a,b,c)表示某種局勢,首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗。第二種奇異局勢是(0,n,n),只要與對手拿走一樣多的物品,最后都將導(dǎo)致(0,0,0)。仔細(xì)分析一下,(1,2,3)也是奇異局勢,無論對手如何拿,接下來都可以變?yōu)椋?,n,n)的情形。
            計算機(jī)算法里面有一種叫做按位模2加,也叫做異或的運(yùn)算,我們用符號(^)表示這種運(yùn)算。這種運(yùn)算和一般加法不同的一點(diǎn)是1^1=0。先看(1,2,3)的按位模2加的結(jié)果:
            1 =二進(jìn)制01
            2 =二進(jìn)制10
            3 =二進(jìn)制11 (^)
            ———————
            0 =二進(jìn)制00 (注意不進(jìn)位)
            對于奇異局勢(0,n,n)也一樣,結(jié)果也是0。
            任何奇異局勢(a,b,c)都有a(^)b(^)c =0。
            如果我們面對的是一個非奇異局勢(a,b,c),要如何變?yōu)槠娈惥謩菽兀考僭O(shè) a < b < c,我們只要將 c 變?yōu)?a(^)b,即可,因?yàn)橛腥缦碌倪\(yùn)算結(jié)果: a(^)b(^)(a(^)b)=(a(^)a)(^)(b(^)b)=0(^)0=0。要將c 變?yōu)閍(^)b,只要從 c中減去 c-(a(^)b)即可。
            獲勝情況對先取者進(jìn)行討論:
            異或結(jié)果為0,先取者必敗,無獲勝方法。后取者獲勝;
            結(jié)果不為0,先取者有獲勝的取法。
            拓展: 任給N堆石子,兩人輪流從任一堆中任取(每次只能取自一堆),取最后一顆石子的人獲勝,問先取的人如何獲勝?
            根據(jù)上面所述,N個數(shù)異或即可。如果開始的時候T=0,那么先取者必敗,如果開始的時候T>0,那么只要每次取出石子使得T=0,即先取者有獲勝的方法。
            posted on 2015-03-04 11:16 JulyRina 閱讀(296) 評論(1)  編輯 收藏 引用 所屬分類: 算法專題

            FeedBack:
            # re: 三個入門博弈
            2015-04-02 21:55 | siempre
            15804604950@163.com  回復(fù)  更多評論
              
            久久青青草原亚洲av无码app| 久久成人精品| 久久99国产乱子伦精品免费| 久久99热精品| 老男人久久青草av高清| 久久精品日日躁夜夜躁欧美| 久久丫精品国产亚洲av| 伊人久久大香线蕉精品| 久久笫一福利免费导航 | 久久精品国产99国产精品亚洲| 97久久婷婷五月综合色d啪蜜芽 | 久久久久久精品成人免费图片| 久久久久亚洲av无码专区喷水 | 97久久国产露脸精品国产| 青青青国产成人久久111网站| 欧美久久亚洲精品| 久久久九九有精品国产| 性做久久久久久久| 亚洲欧美精品一区久久中文字幕| 色88久久久久高潮综合影院 | 中文字幕久久精品无码| 国产综合免费精品久久久| 国内精品伊人久久久久AV影院| 天堂无码久久综合东京热| 亚洲欧美日韩精品久久| 狠狠色婷婷久久一区二区三区| 亚洲精品tv久久久久| …久久精品99久久香蕉国产| 99久久精品免费看国产一区二区三区 | 伊人久久综合无码成人网 | 久久无码专区国产精品发布| 久久综合视频网站| 久久国产视屏| 性做久久久久久久久老女人| 久久精品一区二区三区中文字幕 | 国产色综合久久无码有码| 久久亚洲日韩看片无码| 久久综合偷偷噜噜噜色| 精产国品久久一二三产区区别| 亚洲国产成人精品女人久久久| 要久久爱在线免费观看|