組合博弈取石子游戲綜述

1、博弈問(wèn)題分析一一取石子游戲?qū)嵗獯?lt;1>小紅是個(gè)游戲迷，他和小藍(lán)一起玩拿石子游戲。游戲規(guī)則為2個(gè)人輪流拿石子。 一次可以拿1顆或3顆，規(guī)定誰(shuí)取到最后一顆石子誰(shuí)就勝出。最后決定由小紅先取。兩人都是 游戲高手，該贏的絕不會(huì)輸（表示不會(huì)失誤）。問(wèn)在知道石子總數(shù)的情況下，怎樣快速預(yù)測(cè)誰(shuí)將會(huì)勝出。分析：小紅和小藍(lán)各取一次共有三種情況：共取走2顆石子（1,1）共取走4顆石子（1,3）共取走6顆石子（3,3）設(shè)方案取了 N1次，方案取了 N2次，方案取了 N3次后，還剩下K （k<6,否則 可以再取幾輪，導(dǎo)致剩余量<6 ）個(gè)石子。最后 K的取值有三種情況：0, 1, 3。這個(gè)要解釋一

2、下：剩下的石子個(gè)數(shù)總共有 0,1,2,3,4,5幾種可能，2可以再取一輪（1,1） 剩下0, 4可以再取一輪（1,3）或者兩次（1,1）剩下0, 5可以再?。?,1）、（1,3）等的組 合剩下1或3個(gè)，所以綜合是最終會(huì)剩下 0、1、3三種可能。設(shè)有石子 S.則 S=2*N1+4*N2+6*N3+K. 其中 2*N1+4*N2+6*N3=（1 + 1 ） *N1 +（1+3 ） *N2+ （3+3 ） *N3 ,說(shuō)明取的過(guò)程為偶數(shù)次，所以剩下K時(shí)該最先取石子的人取。K=1 , 3 則先取方勝。反之，另一方勝。又 2*N1+4*N2+6*N3=2*（ N1+2*N2+3*N3）為偶數(shù)，所以S的奇偶

3、性取決于 K,當(dāng)K為偶數(shù)時(shí)，后取方勝，反之，先取方勝?？偨Y(jié)：計(jì)算時(shí)可以先對(duì) 6取余，如果余數(shù)為 0、2、4,則K為0 （偶數(shù)，后取者勝）， 如果余數(shù)為1、3、5則K為1或3 （奇數(shù)，先取者剩）。<2>有一種很有意思的游戲，就是有物體若干堆，可以是火柴棍或是圍棋子等等均可。兩個(gè)人輪流從堆中取物體若干，規(guī)定最后取光物體者取勝。這是我國(guó)民間很古老的一個(gè)游戲，別看這游戲極其簡(jiǎn)單，卻蘊(yùn)含著深刻的數(shù)學(xué)原理。下面我們來(lái)分析一下要如何才能夠取勝。（一）巴什博奕（Bash Game ）:只有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取物，規(guī)定每次至少取一個(gè)，最多取m個(gè)。最后取光者得勝。顯然，如果n=m+1

4、 ,那么由于一次最多只能取 m個(gè)，所以，無(wú)論先取者拿走多少個(gè)，后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：如果n=（m+1 ） * r+s , （r為任意自然數(shù)，s<m ）,那么先取者要拿走 s個(gè)物品，如果后取者拿走k （kwm）個(gè)，那么先取者再拿走m+1-k個(gè)，結(jié)果剩下（m+1 ） （r-1 ）個(gè)，以后保持這樣的取法，那么先取者肯定獲勝?？傊?，要保持給對(duì)手留下（m+1 ）的倍數(shù)，就能最后獲勝。這個(gè)游戲還可以有一種變相的玩法：兩個(gè)人輪流報(bào)數(shù)，每次至少報(bào)一個(gè)，最多報(bào)十個(gè)，誰(shuí)能報(bào)到100者勝?？偨Y(jié)：通過(guò)分析可知，設(shè) n=（m+1）*r+s（s<=m）, 如果

5、s等于0,則后取者獲勝！如果 s不等于0,則先取者勝利?。ǘ┩舴虿┺龋╓ythoff Game ）：有兩堆各若干個(gè)物品，兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品，規(guī)定每次至少取一個(gè)，多者不限，最后取光者得勝。這種情況下是頗為復(fù)雜的。我們用（ ak, bk ） （ak < bk , k=0 , 1 , 2, ,n）表示兩堆物品的數(shù)量并稱其為局勢(shì)，如果甲面對(duì)（0,0）,那么甲已經(jīng)輸了，這種局勢(shì)我們稱為奇異局勢(shì)。前幾個(gè)奇異局勢(shì)是：（0, 0）、（1, 2）、（3, 5）、（4, 7）、（6, 10）、（8, 13）、（9, 15 ）、（11 , 18 ）、（12, 20）。我們可以知

6、道，后面的奇異局勢(shì)可以通過(guò)一輪特殊的取法變?yōu)楦偷钠娈惥謩?shì)！可以看出，a0=b0=0 , ak是未在前面出現(xiàn)過(guò)的最小自然數(shù)，而 bk= ak + k ,奇異局勢(shì)有如下三條性質(zhì):1 .任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢(shì)中。由于ak是未在前面出現(xiàn)過(guò)的最小自然數(shù)，所以有 ak > ak-1 ,而bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 .所以性質(zhì) 1.成立。2 .任意操作都可將奇異局勢(shì)變?yōu)榉瞧娈惥謩?shì)。事實(shí)上，若只改變奇異局勢(shì)(ak, bk)的某一個(gè)分量，那么另一個(gè)分量不可能在其他奇異局勢(shì)中，所以必然是非奇異局勢(shì)。如果使( ak, bk)的兩個(gè)

7、分量同時(shí)減少，則由于其差不 變，且不可能是其他奇異局勢(shì)的差，因此也是非奇異局勢(shì)。3 .采用適當(dāng)?shù)姆椒ǎ梢詫⒎瞧娈惥謩?shì)變?yōu)槠娈惥謩?shì)。假設(shè)面對(duì)的局勢(shì)是(a, b),若b = a,則同時(shí)從兩堆中取走a個(gè)物體，就變?yōu)榱似娈惥謩?shì)(0, 0);如果a = ak , b > bk ,那么，取走b - bk個(gè)物體，即變?yōu)槠娈惥謩?shì)；如果 a =ak , b < bk ,則同時(shí)從兩堆中拿走 ak - ab - ak 個(gè)物體，變?yōu)槠娈惥謩?shì)( ab - a k , ab - a k+ b - a k)；如果a > ak , b= ak + k ,則從第一堆中拿走多余的數(shù)量a - ak 即可；如果a

8、 < ak , b= ak + k ,分兩種情況，第一種，a=aj (j < k ),從第二堆里面拿走b - bj即可；第二種，a=bj (j < k ),從第二堆里面拿走b - aj即可。從如上性質(zhì)可知，兩個(gè)人如果都采用正確操作，那么面對(duì)非奇異局勢(shì)，先拿者必勝；反之，則后拿者取勝。那么任給一個(gè)局勢(shì)(a, b),怎樣判斷它是不是奇異局勢(shì)呢？我們有如下公式：ak =k* (1+ v5) /2 , bk= ak + k(k=0 ,1,2,，n 方括號(hào)表示取整函數(shù))奇妙的是其中出現(xiàn)了黃金分割數(shù)(1+V5) /2 = 1.618，因此，由ak, bk組成的矩 形近似為黃金矩形，由于

9、2/ (1+a/5) = (V5-1 ) /2 ,可以先求出j=a (V5-1 ) /2,若a= j* (1+ v5) /2,那么 a = aj ,bj = aj + j ,若不等于，那么 a = aj+1bj+1 = aj+1 + j + 1,若都不是，那么就不是奇異局勢(shì)。然后再按照上述法則進(jìn)行，一定會(huì)遇到奇異局勢(shì)?？偨Y(jié)：分析到此已經(jīng)很明顯，判斷誰(shuí)個(gè)能夠勝利看是否是奇異矩陣就行了，如果是奇異矩陣，則后取者勝利，如果是非奇異矩陣，則先取者得勝！在判斷是不是咸佐夫博弈的奇異 局勢(shì)的時(shí)候，比如兩個(gè)數(shù) a,b ,則可以首先交換是 a<b,然后記i=b-a,如果是奇異局勢(shì)，則必有m=floor(

10、i*(1+sqrt(5.0)/2), 并且b=m+i,否則比不是奇異局勢(shì)！(三)尼姆博奕(Nimm Game ):有三堆各若干個(gè)物品，兩個(gè)人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個(gè)，多者不限，最后取光者得勝。這種情況最有意思，它與二進(jìn)制有密切關(guān)系，我們用( a, b, c)表示某種局勢(shì)，首先 (0, 0, 0)顯然是奇異局勢(shì)，無(wú)論誰(shuí)面對(duì)奇異局勢(shì)，都必然失敗。第二種奇異局勢(shì)是(0, n, n),只要與對(duì)手拿走一樣多的物品，最后都將導(dǎo)致(0, 0, 0)。仔細(xì)分析一下，(1, 2, 3)也是奇異局勢(shì)，無(wú)論對(duì)手如何拿，接下來(lái)都可以變?yōu)?0, n, n)的情形。計(jì)算機(jī)算法里面有一種叫做按位模 2

11、力口，也叫做異或的運(yùn)算，我們用符號(hào)( +)表示這 種運(yùn)算。這種運(yùn)算和一般加法不同的一點(diǎn)是1+1=0。先看(1, 2, 3)的按位模2加的結(jié)果：1 =二進(jìn)制012 =二進(jìn)制103 =二進(jìn)制11(+ )0 =二進(jìn)制00 (注意不進(jìn)位)對(duì)于奇異局勢(shì)(0, n , n)也一樣，結(jié)果也是 0。任何奇異局勢(shì)(a, b , c)都有a ( + ) b (+) c =0。如果我們面對(duì)的是一個(gè)非奇異局勢(shì)(a, b, c),要如何變?yōu)槠娈惥謩?shì)呢？假設(shè)a < b< c ,我們只要將c變?yōu)閍 (+) b,即可，因?yàn)橛腥缦碌倪\(yùn)算結(jié)果：a (+) b (+) (a (+) b)=(a ( + ) a) (+)

12、 (b (+) b) =0 (+) 0=0 。要將 c 變?yōu)?a (+) b ,只要從 c 中減去 c- ( a (+ ) b)即可。總結(jié)：面對(duì)奇異局勢(shì)，先取者必定輸，如果是非奇異局勢(shì)，則先取者贏！如果一個(gè)局勢(shì)(a,b,c)有a(+)b(+)c=0,則是奇異局勢(shì)，如果不是，則不是奇異局勢(shì)!三堆石子的結(jié)論同樣也適用于n堆石子的情況!取火柴的游戲題目1 ：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。題目2：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，可將一堆全取走，但不可不取，最后取完者為負(fù)，求必勝的

13、方法。嘿嘿，這個(gè)游戲我早就見(jiàn)識(shí)過(guò)了。 小時(shí)候用珠算玩這個(gè)游戲： 第一檔撥一個(gè)，第二檔撥兩個(gè)，依次直到第五檔撥五個(gè)。然后兩個(gè)人就輪流再把棋子撥下來(lái)，誰(shuí)要是最后一個(gè)撥誰(shuí)就贏。有一次暑假看見(jiàn)兩個(gè)小孩子在玩這個(gè)游戲，我就在想有沒(méi)有一個(gè)定論呢。 下面就來(lái)試著證明一下吧先解決第一個(gè)問(wèn)題吧。定義：若所有火柴數(shù)異或?yàn)?0,則該狀態(tài)被稱為利他態(tài)，用字母 T表示；否則，為利己態(tài)，用S表不。定理1:對(duì)于任何一個(gè) S態(tài)，總能從一堆火柴中取出若干個(gè)使之成為T(mén)態(tài)。證明:若有n堆火柴，每堆火柴有A(i)根火柴數(shù)，那么既然現(xiàn)在處于 S態(tài)，c = A(1) xor A(2) xor xor A(n) > 0;把c表示成二

14、進(jìn)制，記它的二進(jìn)制數(shù)的最高位為第p位，則必然存在一個(gè) A(t),它二進(jìn)制的第p位也是1。(否則，若所有的 A(i)的第p位都是0,這與c的第p位就也為0矛盾)。那么我們把x = A(t) xor c,則得到x < A(t).這是因?yàn)榧热?A(t)的第p位與c的第p位同為1,那么x的第p位變?yōu)?,而高于p的位并沒(méi)有改變。所以 x < A(t).而A(1) xor A(2) xor xor x xor xor A(n)=A(1) xor A(2) xor xor A(t) xor c xor xor A(n)=A(1) xor A(2) xor xor A(n) xor A(1) xo

15、r A(2) xor xor A(n)=0這就是說(shuō)從A(t)堆中取出A(t) x根火柴后狀態(tài)就會(huì)從S態(tài)變?yōu)門(mén)態(tài)。證畢定理2: T態(tài)，取任何一堆的若干根，都將成為S態(tài)。證明：用反證法試試。若c = A(1) xor A(2) xor xor A(i) xor xor A(n) = 0 ;c' = A(1) xor A(2) xor xor A(i ' xor c xor xor A(n) = 0;則有c xor c' = A(1) xor A(2) xor xor A(i) xor xor A(n) xor A(1) xor A(2) xor xor A(i ')

16、xor c xor xor A(n) = A(i) xor A(i ' =0進(jìn)而推出A(i) = A(i '),這與已知矛盾。所以命題得證。定理3 : S態(tài)，只要方法正確，必贏。最終勝利即由S態(tài)轉(zhuǎn)變?yōu)門(mén)態(tài)，任何一個(gè) S態(tài)，只要把它變?yōu)?T態(tài)，(由定理1,可以把它變成T態(tài)。）對(duì)方只能把T態(tài)轉(zhuǎn)變?yōu)镾態(tài)（定理2）。這樣，所有S態(tài)向T態(tài)的轉(zhuǎn)變都可以有己方控制，對(duì)方只能被動(dòng)地實(shí)現(xiàn)由T態(tài)轉(zhuǎn)變?yōu)镾態(tài)。故S態(tài)必贏。定理4 : T態(tài)，只要對(duì)方法正確，必?cái)　Ｓ啥ɡ?易得。總結(jié)：如果先手遇到 s態(tài)，則先手必贏，如果遇到 T態(tài)，必?cái)?！接著?lái)解決第二個(gè)問(wèn)題。定義：若一堆中僅有 1根火柴，則被稱為孤單堆。

17、若大于 1根，則稱為充裕堆。定義：我們?cè)O(shè)只有一根火柴的堆為單根堆，否則為充裕堆，充裕堆=2的T用T2表示,全是單根堆的T用T0表示（沒(méi)有T1這種狀態(tài)，分析可知）同樣的充裕堆=2的S態(tài)用S2表示，全為孤單堆的 S （可知堆數(shù)必為奇數(shù)） 態(tài)用S0表示,只有一堆充裕堆的用 S1表示孤單堆的根數(shù)異或只會(huì)影響二進(jìn)制的最后一位，但充裕堆會(huì)影響高位（非最后一位）。一個(gè)充裕堆，高位必有一位不為 0,則所有根數(shù)異或不為 0。故不會(huì)是T態(tài)。定理5 : S0態(tài)，即僅有奇數(shù)個(gè)孤單堆（沒(méi)有充裕堆），必?cái)　0態(tài)必勝。證明：S0態(tài)，其實(shí)就是每次只能取一根。每次第奇數(shù)根都由己取，第偶數(shù)根都由對(duì)方取，所以最后一根必己取。敗。

18、同理，T0態(tài)必勝#定理6 : S1態(tài)，只要方法正確，必勝。證明：若此時(shí)孤單堆堆數(shù)為奇數(shù)，把充裕堆取完；否則，取成只剩下一根（此時(shí)變成S0態(tài)，但是自己是后手）。這樣，就變成奇數(shù)個(gè)孤單堆，由對(duì)方取。由定理 5,對(duì)方必輸。己必勝。#定理7 : S2態(tài)不可轉(zhuǎn)一次變?yōu)?T0態(tài)。證明: 充裕堆數(shù)不可能一次由 2變?yōu)?。得證。#定理8 : S2態(tài)可一次轉(zhuǎn)變?yōu)?T2態(tài)。證明：由定理1, S態(tài)可轉(zhuǎn)變?yōu)?T態(tài)，又由定理 7, S2態(tài)不可轉(zhuǎn)一次變?yōu)?T0態(tài)，所以轉(zhuǎn)變的 T態(tài)為T(mén)2態(tài)。#定理9 : T2態(tài)，只能轉(zhuǎn)變?yōu)?S2態(tài)或S1態(tài)。證明：由定理2, T態(tài)必然變?yōu)镾態(tài)。由于充裕堆數(shù)不可能一次由2變?yōu)?,所以此時(shí)的S態(tài)

19、不可能為S0態(tài)。命題得證。定理10 : S2態(tài)，只要方法正確，必勝 .證明：方法如下：1 ） S2態(tài)，就把它變?yōu)?T2態(tài)。（由定理8）2 ） 對(duì)方只能T2轉(zhuǎn)變成S2態(tài)或S1態(tài)（定理9）若轉(zhuǎn)變?yōu)镾2,轉(zhuǎn)向1 ）若轉(zhuǎn)變?yōu)镾1,這己必勝。（定理5）定理11 : T2態(tài)必輸。證明：同10?？偨Y(jié)，必輸態(tài)有： T2,S0必勝態(tài)： S2,S1,T0.兩題比較:第一題的全過(guò)程其實(shí)如下:S2->T2->S2->T2->->T2->S1->T0->S0->T0-> ->S0->T0（ 全 0）第二題的全過(guò)程其實(shí)如下：S2->T2->

20、;S2->T2->->T2->S1->S0->T0->S0-> ->S0->T0（ 全 0）下劃線表示勝利一方的取法。是否發(fā)現(xiàn)了他們的驚人相似之處。我們不又t發(fā)現(xiàn)（見(jiàn)加黑部分），S1態(tài)可以轉(zhuǎn)變?yōu)镾0態(tài)（第二題做法），也可以轉(zhuǎn)變?yōu)門(mén)0 （第一題做法）。哪一方控制了 S1態(tài)，他即可以有辦法使自己得到最后一根（轉(zhuǎn)變?yōu)門(mén)0）,也可以使對(duì)方得到最后一根（轉(zhuǎn)變?yōu)?S0）。所以，搶奪S1是制勝的關(guān)鍵！為此，始終把T2態(tài)讓給對(duì)方，將使對(duì)方處于被動(dòng)狀態(tài)，他早晚將把狀態(tài)變?yōu)镾1.推薦HDOJ題目http:http:看完上面的結(jié)論，就能順利解決上面2道了S

21、-Nimhttp: http: 博弈算法入門(mén)小節(jié) 1536 1517 1907小子最近迷途于博弈之中。感觸頗深。為了讓大家能夠在學(xué)習(xí)博弈的時(shí)候少走彎路，最重要的也是為了加深自己的影響，溫故而知新，特發(fā)此貼與大家共勉。學(xué)博弈先從概念開(kāi)始：特別推薦LCY老師的課件：博弈入門(mén)。下載地址：http:這個(gè)課件個(gè)人認(rèn)為從博弈的基本思想，一直到解博弈的中心算法做了很好的詮釋。但是特別要注意的是。課件后面一部分英語(yǔ)寫(xiě)的講義是重中之重。小子英語(yǔ)很弱，在這困擾很久?，F(xiàn)在為大家大概介紹一下。主要是后繼點(diǎn)和 SG值的問(wèn)題：SG值：一個(gè)點(diǎn)的SG值就是一個(gè)不等于它的后繼點(diǎn)的SG的且大于等于零的最小整數(shù)。后繼點(diǎn)：也就是按照

22、題目要求的走法（比如取石子可以取的數(shù)量，方法）能夠走一步達(dá)到的那個(gè)點(diǎn)。具體的有關(guān)SG值是怎么運(yùn)用的希望大家自己多想想。課件后面有一個(gè)1536的代碼?？梢苑旁诤竺孀鲎隹吹竭@里推薦大家做幾道題：1846 （最簡(jiǎn)單的博弈水題）1847 （求 SG 值）有了上面的知識(shí)接下來(lái)我們來(lái)看看組合博弈（n堆石子）推薦大家看個(gè)資料： 博弈-取石子游戲（推薦等級(jí)五星級(jí)）http: 這里提出了一個(gè)奇異狀態(tài)的問(wèn)題?？戳诉@篇文章你會(huì)發(fā)現(xiàn)異或運(yùn)算在博弈中使用的妙處。當(dāng)然這里指出的只是組合博弈中一種特殊情況。王道還是對(duì)SG值的求解，但是知道這么一種思路無(wú)疑對(duì)思維的廣度和深度擴(kuò)展是很有幫助的。ZZ博弈http:這里介紹了組和博

23、弈的兩種大的類型，一種是最后取的是 N狀態(tài)一種是最后取的是 P狀態(tài)，兩個(gè)狀態(tài)的解題方法能看懂很有幫助。當(dāng)然，能夠把推導(dǎo)過(guò)程理解，吃透無(wú)疑是大牛級(jí)的做法小子也佩服的緊1536題推薦做做這題，這題前面提醒大家是一個(gè)求SG值的題目，題目前面是對(duì)異或運(yùn)算運(yùn)用在組合博弈問(wèn)題中的很好的解釋。當(dāng)然題目本身是有所不同的。因?yàn)樵谶@里面對(duì)取法有所要求。那么這樣就回歸到了解決博弈問(wèn)題的王道算法一一求SG值上。有關(guān)運(yùn)用求SG值的博弈題目有：1850 （也可基于奇異狀態(tài)異或）1848 （中和的大斐波那契數(shù)列的典型求SG值題）1517 （個(gè)人認(rèn)為有點(diǎn)猥瑣的題目。在此題上困擾很久。當(dāng)然搞出來(lái)很開(kāi)心。小子是用比較規(guī)矩的求SG

24、值的方法求出來(lái)的，但是論壇有人對(duì)其推出來(lái)了規(guī)律，這里佩服一下，大家可以學(xué)習(xí)一下）1079 （更猥瑣的題目，對(duì)新手要求較高，因?yàn)榘磦鹘y(tǒng)方法需要比較細(xì)致的模擬加對(duì)邊角狀態(tài)的考慮，同樣有人推出來(lái)了公式）當(dāng)你全部看完以上的東西。做完以上的題目的話。小子恭喜你你博弈入門(mén)了/Accepted 1536 578Ms 416K 904 B這里小子告訴大家。博弈很強(qiáng)大。學(xué)習(xí)要耐心謝謝Current System Time : 2008-12-11 19:16:03ACM課作業(yè)：1001 Brave Game1002 Good Luck in CET-4 Everybody!1003 Fibonacci agai

25、n and again1004 Rabbit and Grass1005 Being a Good Boy in Spring Festival1006 Public Sale1007悼念512汶川大地震遇難同胞一一選拔志愿者1008 kiki ' game1009 Calendar Game1010 A Multiplication Game1011 Digital Deletions1012 S-Nimhttp:1536的參考代碼本部分設(shè)定了隱藏，您已回復(fù)過(guò)了，以下是隱藏的內(nèi)容Copy code博弈-基于求SG值#include " iostream ” using na

26、mespace std;int f101,sg10001,k;int mex(int b)int a101=0,i;for(i=0;i<k;i+)if(b-f <0)/b-f 后繼點(diǎn) break;if(sgb-f=-1)sgb-f=mex(b-f);asgb-f=1;for(i=0;i<k;i+)if(return i;int main()(int i,t,n,s,bead,j;while(cin >> k,k)(for(i=0;i<k;i+)(cin >> f;)memset(sg,-1,sizeof(sg);for(i=0;i<k;i+

27、)for(j=i+1;j<k;j+)if(f>fj)(f+=fj;fj=f-fj;f-=fj;)sg0=0;cin >> t;while(t -)cin >> n;s=0;while(n -)cin >> bead;/該堆的成員個(gè)數(shù)if(sgbead=-1)sgbead=mex(bead);s=sAsgbead;if(s=0)cout <<“ L ” ；elsecout <<“ W ；cout << endl;return 0;1517參考代碼本部分設(shè)定了隱藏，您已回復(fù)過(guò)了，以下是隱藏的內(nèi)容Copy code博

28、弈-基于求SG值/Accepted 1517 234Ms 0K 837 B#include " iostream ”using namespace std;int main()_int64 a7000=1,min,n;int p10,sg7000,i,j,k;for(i=2;i<10;p=0,i+);for(i=1;i<7000;i+)for(j=2,min=-1;j<10;j+)if(min=-1|apj*j<apmin*min) min=j;a=apmin*min;min=apmin*min;if(a>=5000000000)break;for(j=

29、2;j<10;j+)if(apj*j=min)pj+;/從小到大求出所有乘積while(scanf( " 164d "，&n)!=EOF)for(i=0;i<7000;i+)sg=0；if(a>=n)break;for(j=i-1;aj*9>=n&&j>=0;j-)sgj=1；while(j>=0)for(k=j+1;k<i&&aj*9>=ak;k+)if(ak%aj=0&&sgk=0)sgj=1;break;j彳puts(sg0? ” S/tiars. " :

30、" OWins.");return 0;這里感謝sh礎(chǔ)同學(xué)的一段代碼讓小子學(xué)會(huì)了 puts的妙用1907參考代碼本部分設(shè)定了隱藏，您已回復(fù)過(guò)了，以下是隱藏的內(nèi)容#include " iostream ”using namespace std;int main()int temp,t,n,s,x,i;cin >> t;while(t -)cin >> n;for(i=s=temp=0;i<n;i+)cin >> x;if(x>1) temp=1;sA=x;if(s&&temp)|(!s&&

31、;!temp)cout <<“ John " << endl;elsecout <<" Brother"<< endl;return 0;Sprague-Grundy Function- 簡(jiǎn)稱 sgNim游戲；比如說(shuō)：有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數(shù)顆，可以從第3堆及以后石子里取任意顆 這時(shí)看上去問(wèn)題復(fù)雜了很多，但相信你如果掌握了本節(jié)的內(nèi)容，類似的千變?nèi)f化的問(wèn)題都是不成問(wèn)題的。現(xiàn)在我們來(lái)研究一個(gè)看上去似乎更為一般的游戲：給定一個(gè)有向無(wú)環(huán)圖和一個(gè)起始頂點(diǎn)上 的一枚棋子，兩名

32、選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無(wú)法移動(dòng)者判負(fù)。事實(shí)上，這個(gè)游戲可以認(rèn)為是所有 Impartial Combinatorial Games（公正的組合游戲）的抽象模型。也就是說(shuō)，任何一個(gè)ICG都可以通過(guò)把每個(gè)局面（狀態(tài)、局勢(shì)）看成一個(gè)頂點(diǎn)，對(duì)每個(gè)局面和它的子局面連一條 有向邊來(lái)抽象成這個(gè)有向圖游戲”。下面我們就在有向無(wú)環(huán)圖的頂點(diǎn)上定義Sprague-Garundy函數(shù)。首先定義mex（minimal excludant）運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例如 mex0,1,2,4=3 、mex2,3,5=0、mex=0。對(duì)于一個(gè)給定的有向無(wú)環(huán)圖，定義關(guān)于

33、圖的每個(gè)頂點(diǎn)x的Sprague-Garundy 函數(shù)g如下：g（x）=mex g（y） | y 是 x 的后繼。來(lái)看一下SG函數(shù)的性質(zhì)。首先：所有的terminal position（末端位置）n所對(duì)應(yīng)的頂點(diǎn)，也就是沒(méi)有出邊的頂點(diǎn)，其 SG值為0, 因?yàn)樗暮罄^集合是空集。（所有終結(jié)點(diǎn)是必?cái)↑c(diǎn)（P點(diǎn)）然后對(duì)于一個(gè)g（x）=0的頂點(diǎn)x,它的所有后繼 y都滿足g（y）!=0。（無(wú)論如何操作，從必?cái)↑c(diǎn)（P點(diǎn)）都只能進(jìn)入必勝點(diǎn)（N點(diǎn)）對(duì)于一個(gè)g（x）!=0的頂點(diǎn)，必定存在一個(gè)后繼y滿足g（y）=0。（從任何必勝點(diǎn)（N點(diǎn)）操作，至少有一種方法可以進(jìn)入必?cái)↑c(diǎn)（ P點(diǎn)）以上這三句話表明，頂點(diǎn)x所代表的pos

34、tion 是P-position 當(dāng)且僅當(dāng) g（x）=0 （跟P-positioin/N-position的定義的那三句話是完全對(duì)應(yīng)的）。我們通過(guò)計(jì)算有向無(wú)環(huán)圖的每個(gè)頂點(diǎn)的SG值，就可以對(duì)每種局面找到必勝策略了。但 SG函數(shù)的用途遠(yuǎn)沒(méi)有這樣簡(jiǎn)單。如果將有向圖游戲變復(fù)雜一點(diǎn)，比如說(shuō)，有向圖上并不是只有一枚棋子，而是有n枚棋子，每次可以任選一顆進(jìn)行移動(dòng)，這時(shí)，怎樣找到必勝策略呢？讓我們?cè)賮?lái)考慮一下頂點(diǎn)的SG值的意義。當(dāng)g(x)=k時(shí)，表明對(duì)于任意一個(gè) 0<=i<k ,都存在x的一個(gè)后繼y滿足g(y尸i (根據(jù)mex函數(shù)定義和g函數(shù)定義可知)。也就是說(shuō)，當(dāng)某枚棋子 的SG值是k時(shí)，我們可

35、以把它變成0、變成1、變成k-1 ,但絕對(duì)不能保持 k不變。不知道你能不能根據(jù)這個(gè)聯(lián)想到Nim游戲，Nim游戲的規(guī)則就是： 每次選擇一堆數(shù)量為 k的石子，可以把它變成 0、變成1、變成k-1 ,但絕對(duì)不能保持 k不變。這表明，如果將 n枚棋子 (圖上面有n枚棋子在移動(dòng)，相當(dāng)于 n個(gè)取石子的子游戲)所在的頂點(diǎn)的SG值看作n堆相應(yīng)數(shù)量的石子，那么這個(gè) Nim游戲的每個(gè)必勝策略都對(duì)應(yīng)于原來(lái)這n枚棋子的必勝策略！對(duì)于n個(gè)棋子，設(shè)它們對(duì)應(yīng)的頂點(diǎn)的 SG值分別為(a1,a2,an),再設(shè)局面(a1,a2,an) 時(shí)的Nim游戲的一種必勝策略是把 ai變成k,那么原游戲的一種必勝策略就是把第i枚棋子移動(dòng)到一個(gè)SG值為k的頂點(diǎn)。這聽(tīng)上去有點(diǎn)過(guò)于神奇 一一怎么繞了一圈又回到 Nim游戲上了。其實(shí)我們還是只要證明這種多棋