青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
(一)巴什博奕(Bash Game):只有一堆n個(gè)物品,兩個(gè)人輪流從這堆物品中取物,規(guī)定每次至少取一個(gè),最多取m個(gè)。最后取光者得勝。
顯然,如果n=m+1,那么由于一次最多只能取m個(gè),所以,無論先取者拿走多少個(gè),后取者都能夠一次拿走剩余的物品,后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則:如果n=(m+1)r+s,(r為任意自然數(shù),s≤m),那么先取者要拿走s個(gè)物品,如果后取者拿走k(≤m)個(gè),那么先取者再拿走m+1-k個(gè),結(jié)果剩下(m+1)(r-1)個(gè),以后保持這樣的取法,那么先取者肯定獲勝。總之,要保持給對手留下(m+1)的倍數(shù),就能最后獲勝。
即,若n=k*(m+1),則后取著勝,反之,存在先取者獲勝的取法。
n%(m+1)==0. 先取者必?cái) ?/storng>
(二)威佐夫博奕(Wythoff Game):有兩堆各若干個(gè)物品,兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝。
這種情況下是頗為復(fù)雜的。我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數(shù)量并稱其為局勢,如果甲面對(0,0),那么甲已經(jīng)輸了,這種局勢我們稱為奇異局勢。前幾個(gè)奇異局勢是:(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ù)都包含在一個(gè)且僅有一個(gè)奇異局勢中。
由于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)的某一個(gè)分量,那么另一個(gè)分量不可能在其他奇異局勢中,所以必然是非奇異局勢。如果使(ak,bk)的兩個(gè)分量同時(shí)減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢。
3。采用適當(dāng)?shù)姆椒ǎ梢詫⒎瞧娈惥謩葑優(yōu)槠娈惥謩荨?
假設(shè)面對的局勢是(a,b),若 b = a,則同時(shí)從兩堆中取走 a 個(gè)物體,就變?yōu)榱似娈惥謩荩?,0);如果a = ak ,b > bk,那么,取走b - bk個(gè)物體,即變?yōu)槠娈惥謩荩蝗绻?a = ak , b < bk ,則同時(shí)從兩堆中拿走 ak - ab - ak個(gè)物體,變?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ì)可知,兩個(gè)人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝;反之,則后拿者取勝。
那么任給一個(gè)局勢(a,b),怎樣判斷它是不是奇異局勢呢?我們有如下公式:
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...,n 方括號(hào)表示取整函數(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)行,一定會(huì)遇到奇異局勢。
(三)尼姆博奕(Nimm Game):有三堆各若干個(gè)物品,兩個(gè)人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝。
這種情況最有意思,它與二進(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ì)算機(jī)算法里面有一種叫做按位模2加,也叫做異或的運(yùn)算,我們用符號(hào)(^)表示這種運(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。
如果我們面對的是一個(gè)非奇異局勢(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,先取者必?cái)。?/strong>無獲勝方法。后取者獲勝;
結(jié)果不為0,先取者有獲勝的取法。
拓展: 任給N堆石子,兩人輪流從任一堆中任取(每次只能取自一堆),取最后一顆石子的人獲勝,問先取的人如何獲勝?
根據(jù)上面所述,N個(gè)數(shù)異或即可。如果開始的時(shí)候T=0,那么先取者必?cái)。绻_始的時(shí)候T>0,那么只要每次取出石子使得T=0,即先取者有獲勝的方法。
posted on 2015-03-04 11:16 JulyRina 閱讀(321) 評(píng)論(1)  編輯 收藏 引用 所屬分類: 算法專題

FeedBack:
# re: 三個(gè)入門博弈
2015-04-02 21:55 | siempre
15804604950@163.com  回復(fù)  更多評(píng)論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
              国产欧美日韩精品专区| 欧美无乱码久久久免费午夜一区| 亚洲精品乱码久久久久久蜜桃91 | 亚洲三级影院| 亚洲精品综合| 日韩亚洲综合在线| 亚洲精品人人| 亚洲专区欧美专区| 欧美一级成年大片在线观看| 欧美一区二区日韩| 久久这里有精品15一区二区三区| 久久亚洲综合网| 亚洲风情亚aⅴ在线发布| 一区二区免费在线播放| 制服丝袜亚洲播放| 久久精品日韩| 噜噜噜躁狠狠躁狠狠精品视频 | 久久精品在这里| 欧美大片免费久久精品三p| 欧美第一黄色网| 久久精品国产欧美亚洲人人爽| 亚洲精选久久| 午夜宅男欧美| 欧美激情精品久久久久久免费印度| 亚洲精选在线观看| 性欧美大战久久久久久久免费观看 | 欧美一区二区三区播放老司机| 狠狠色狠狠色综合人人| 国产精品白丝jk黑袜喷水| 欧美午夜在线| 国产一区二区中文字幕免费看| 国模精品一区二区三区| 欧美成人精品激情在线观看| 国产亚洲视频在线观看| 亚洲免费在线电影| 一本久道久久综合狠狠爱| 欧美色欧美亚洲另类二区| 国产精品你懂的| 一本久久知道综合久久| 99在线热播精品免费99热| 久久精视频免费在线久久完整在线看| 欧美成年视频| 亚洲日本aⅴ片在线观看香蕉| 亚洲日本欧美日韩高观看| 亚洲免费av网站| 亚洲中午字幕| 亚洲视频中文| 久久国产精品99国产| 亚洲在线观看| 亚洲黄色成人网| 日韩写真在线| 亚洲国产婷婷香蕉久久久久久99| 亚洲人久久久| 亚洲伊人一本大道中文字幕| 久久五月激情| 欧美一级艳片视频免费观看| 久久亚洲视频| 亚洲免费电影在线| 欧美伊人精品成人久久综合97| 亚洲三级免费观看| 久久一区二区视频| 亚洲国产精品成人va在线观看| 欧美在线亚洲综合一区| 亚洲欧美日韩精品久久亚洲区 | 欧美日韩一区二区三区在线看| 99天天综合性| 久久夜色撩人精品| 久久久国产一区二区| 欧美精品自拍| 久久国产色av| 久久久91精品国产一区二区三区| 国产亚洲精品久久久| av不卡在线看| 亚洲欧美怡红院| 亚洲国产视频直播| 久久这里只有| 久久人人超碰| 免费观看在线综合| 国产精品第一区| 尤物在线观看一区| 美日韩精品免费观看视频| 在线综合视频| 国产精品99一区二区| 韩日欧美一区| 欧美va亚洲va日韩∨a综合色| 999在线观看精品免费不卡网站| 久久免费偷拍视频| 亚洲电影第1页| 欧美一区二区精品在线| 欧美激情黄色片| 亚洲精品黄色| 亚洲小视频在线观看| 国产精品一卡二| 久久久久久久精| 久久精品99无色码中文字幕| 国产欧美短视频| 久久久99爱| 欧美一区免费| 欧美高清在线播放| 亚洲国产老妈| 香蕉成人伊视频在线观看 | 狠狠色狠狠色综合日日五| 美日韩丰满少妇在线观看| 久久亚洲精品伦理| 美女精品自拍一二三四| 亚洲一级免费视频| 久久久青草婷婷精品综合日韩| 99精品久久| 久久国产黑丝| 一本色道久久88综合亚洲精品ⅰ | 免费在线成人av| 国产精品扒开腿爽爽爽视频 | 一区二区三区在线观看国产| 亚洲盗摄视频| 国产精品亚洲综合久久| 亚洲人成亚洲人成在线观看| 国产一区二区高清视频| 日韩网站免费观看| 亚洲国产精品成人| 久久av老司机精品网站导航| 亚洲图片欧美日产| 欧美精品一区二区三区高清aⅴ| 久久精品国语| 欧美性久久久| 亚洲蜜桃精久久久久久久| 亚洲欧洲日本国产| 久久久久久伊人| 久久精品一区四区| 国产精品伊人日日| 亚洲天堂网站在线观看视频| 一个人看的www久久| 乱中年女人伦av一区二区| 久久福利一区| 国产欧美日韩亚洲精品| 亚洲一级黄色av| 亚洲欧美精品中文字幕在线| 欧美日韩精品一二三区| 亚洲精品一区二区三区婷婷月 | 亚洲国产精品一区二区www在线| 国产亚洲免费的视频看| 亚洲欧美日韩一区在线观看| 亚洲男女毛片无遮挡| 欧美性一二三区| 在线视频精品| 欧美在线视频一区二区三区| 国产精品久久久久久久久久三级 | 91久久久国产精品| 亚洲美女黄色片| 欧美日本三区| 在线综合亚洲欧美在线视频| 中日韩美女免费视频网址在线观看| 国产精品一区2区| 男同欧美伦乱| 亚洲青涩在线| 欧美午夜精品久久久久久浪潮| 一区二区激情小说| 亚洲欧美日韩另类| 国产噜噜噜噜噜久久久久久久久| 日韩系列欧美系列| 久久av资源网| 亚洲国产乱码最新视频| 欧美精品三区| 亚洲欧美经典视频| 国产视频久久| 久久高清一区| 亚洲观看高清完整版在线观看| 亚洲精品一区二| 欧美天天综合网| 久久国产66| 亚洲美女视频在线免费观看| 亚洲尤物视频网| 国产欧美日韩激情| 嫩草影视亚洲| 亚洲尤物视频在线| 美女成人午夜| 在线亚洲免费| 国产在线播放一区二区三区| 蘑菇福利视频一区播放| 亚洲香蕉在线观看| 开心色5月久久精品| 一区二区三区四区精品| 国产一区美女| 欧美日韩麻豆| 久久久久久电影| 亚洲一区在线直播| 欧美好吊妞视频| 欧美一区二区三区在线观看视频| 亚洲第一精品久久忘忧草社区| 国产精品国产三级国产专播品爱网| 久久久夜夜夜| 午夜精品久久| 亚洲精品人人| 欧美国产精品人人做人人爱| 亚洲欧美日本国产专区一区| 在线观看日韩欧美| 国产日韩精品在线观看| 欧美日韩国产一区二区三区地区| 欧美一区二区三区电影在线观看| 日韩一级黄色片| 久久亚洲高清|