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

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

FeedBack:
# re: 三個入門博弈
2015-04-02 21:55 | siempre
15804604950@163.com  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            合欧美一区二区三区| 国产欧美精品xxxx另类| 亚洲狠狠婷婷| 久久夜色精品国产欧美乱| 欧美中文字幕不卡| 久久米奇亚洲| 欧美成人一区二免费视频软件| 美女诱惑黄网站一区| 欧美刺激午夜性久久久久久久| 欧美黑人多人双交| 亚洲美女性视频| 欧美一区二区黄| 欧美v日韩v国产v| 欧美三级视频在线| 国产日韩在线一区| 亚洲国产一区视频| 亚洲资源av| 久久亚洲免费| 亚洲免费成人av电影| 午夜国产精品视频| 美国成人直播| 国产精品女主播一区二区三区| 国产亚洲精品高潮| 一区二区精品国产| 久久噜噜亚洲综合| 亚洲欧洲视频在线| 久久久国产视频91| 国产精品国产一区二区| 亚洲福利视频在线| 久久激情综合网| 日韩视频免费在线观看| 久久精品国产91精品亚洲| 欧美精品在线视频观看| 在线观看欧美黄色| 久久精品国亚洲| 宅男噜噜噜66一区二区| 欧美成人激情在线| 影视先锋久久| 欧美18av| 国产在线不卡视频| 在线成人av| 欧美国产一区二区在线观看| 夜夜嗨av一区二区三区中文字幕| 午夜精品一区二区在线观看 | 国产色综合网| 亚洲视频在线一区观看| 欧美高清在线观看| 久久久久久穴| 国内精品伊人久久久久av一坑| 亚洲午夜精品久久久久久app| 免播放器亚洲一区| 久久精品国产久精国产思思| 国产精品入口福利| 亚洲欧美国产77777| 亚洲精品影视| 欧美日韩精品欧美日韩精品| 亚洲区第一页| 欧美激情一区二区三区四区| 久久久久久69| 亚洲激情影院| 亚洲欧洲中文日韩久久av乱码| 欧美成人四级电影| 99热这里只有成人精品国产| 亚洲国产日韩综合一区| 欧美激情精品久久久久久大尺度| 亚洲精品四区| 亚洲精品中文字幕女同| 欧美亚洲免费高清在线观看| 狼狼综合久久久久综合网| 好吊视频一区二区三区四区| 久久九九99视频| 久久精品免费看| 影音先锋久久| 国产亚洲福利一区| 久久亚洲精品一区二区| 浪潮色综合久久天堂| 亚洲国产另类久久久精品极度| 欧美激情第五页| 欧美精品九九99久久| 亚洲调教视频在线观看| 一本久道久久综合中文字幕| 国产精品欧美风情| 久久免费国产精品| 欧美搞黄网站| 欧美亚洲在线观看| 久久琪琪电影院| 这里只有视频精品| 欧美在线播放一区二区| 亚洲肉体裸体xxxx137| 91久久综合| 国产欧美日韩麻豆91| 欧美大胆成人| 国产精品视频1区| 亚洲第一区在线观看| 欧美视频一区在线观看| 久久久久网址| 欧美揉bbbbb揉bbbbb| 久久综合久久综合这里只有精品 | 亚洲在线成人| 久久国产精品久久久久久电车| 亚洲高清在线播放| 亚洲视频自拍偷拍| 亚洲欧洲精品一区二区三区波多野1战4| 亚洲另类一区二区| 韩国在线一区| 亚洲日产国产精品| 亚洲在线一区二区三区| 亚洲激情在线播放| 欧美与欧洲交xxxx免费观看| 亚洲精品在线视频观看| 欧美一区二区三区婷婷月色 | 久久综合久久综合这里只有精品 | 久久中文字幕导航| 性做久久久久久久免费看| 欧美aⅴ一区二区三区视频| 欧美在线观看视频在线| 欧美视频在线播放| 亚洲激情av在线| 亚洲电影在线免费观看| 亚洲免费视频在线观看| 在线一区二区三区四区| 久久亚洲综合网| 欧美一区二视频在线免费观看| 欧美女人交a| 亚洲第一色在线| 亚洲二区三区四区| 久久久亚洲欧洲日产国码αv | 国产欧美精品国产国产专区| 亚洲精品一区二区三区婷婷月| 亚洲国产三级在线| 久久青草福利网站| 蜜臀av一级做a爰片久久| 国产在线观看精品一区二区三区| 亚洲综合国产激情另类一区| 日韩视频不卡中文| 欧美激情亚洲综合一区| 亚洲国产精品一区二区第一页| 樱桃成人精品视频在线播放| 久久久精品国产免大香伊 | 免费成人性网站| 在线精品高清中文字幕| 久久久欧美一区二区| 久久尤物视频| 亚洲国产精品视频一区| 蘑菇福利视频一区播放| 亚洲国产精品传媒在线观看 | 国产精品久久久久久久久久久久| 亚洲精品一区二区三| av不卡在线看| 欧美日韩国产一区二区三区地区 | 黄网动漫久久久| 一区二区久久| 欧美性猛交xxxx免费看久久久| 一区二区精品在线| 先锋亚洲精品| 国模精品一区二区三区| 久久午夜国产精品| 亚洲精品国产精品国自产观看| 一本色道久久综合亚洲精品高清| 欧美日韩精品在线| 亚洲欧美国产日韩中文字幕| 久久在线免费观看| 日韩一二三在线视频播| 国产精品二区三区四区| 欧美一区二区三区在线免费观看| 久热精品在线| 在线午夜精品自拍| 国产亚洲一区在线播放| 欧美大片免费久久精品三p| 夜夜嗨av一区二区三区网页| 国产精品电影在线观看| 亚洲精品中文在线| 久久国产精品亚洲va麻豆| 亚洲国产精品99久久久久久久久| 欧美日韩另类在线| 久久久成人网| 亚洲视频在线观看免费| 另类欧美日韩国产在线| 中文一区二区在线观看| 狠狠色综合日日| 国产精品videosex极品| 久久亚洲欧美| 亚洲午夜久久久久久久久电影院 | 久久综合给合久久狠狠色 | 小辣椒精品导航| 91久久精品日日躁夜夜躁欧美| 国产精品扒开腿做爽爽爽软件 | 国产精品扒开腿做爽爽爽视频| 久久精品系列| 亚洲午夜精品17c| 欧美电影美腿模特1979在线看| 亚洲女性喷水在线观看一区| 亚洲国内精品| 精品成人在线| 国产视频在线观看一区二区三区| 欧美精品一区二区久久婷婷| 久久久久欧美| 欧美中在线观看| 亚洲欧美另类久久久精品2019| 亚洲欧洲精品成人久久奇米网|