點(diǎn)擊打開鏈接

2 組合博弈游戲應(yīng)滿足以下性質(zhì)：

?

2 1. 有兩個游戲者。

?

2 2. 有一個可能的游戲狀態(tài)集。這個狀態(tài)集通常是有限的。

?

2 3. 游戲規(guī)則指定了在任何狀態(tài)下雙方的可能的走步和對應(yīng)的后繼狀態(tài)集。如果在任意狀態(tài)下雙方的走步集合是相同的，那么說游戲是公平的(impartial) ，否則是不公平的(partizan) 。象棋是不公平的，因?yàn)槊總€人只能移動自己的子。

?

2 4. 兩個游戲者輪流走步。

?

2 5. 當(dāng)?shù)竭_(dá)一個沒有后繼狀態(tài)的狀態(tài)后，游戲結(jié)束。在普通游戲規(guī)則(normal playrule) 下，最后一個走步的游戲者勝；在misμere游戲規(guī)則下，最后一個走步的游戲者輸。如果游戲無限進(jìn)行下去，我們認(rèn)為雙方打平，但通常我們會附加規(guī)定：

?

2 6. 不管雙方怎么走步，游戲總能在有限步后結(jié)束。

?

2 其他規(guī)則包括：不允許隨機(jī)走步（不能扔色子或者隨機(jī)洗牌），且必須信息完全的（如隱藏走步是不允許的），有限步結(jié)束時(shí)不能產(chǎn)生平局。在本節(jié)中，我們只考慮公平游戲，并且通常只考慮普通游戲規(guī)則（最后走步的勝）。

?

2 和一般的雙人零和博弈不同的是，這里的博弈游戲是特殊的：它們很好的數(shù)學(xué)特性，使得我們能夠找到可判定輸贏的數(shù)學(xué)策略，而不需要進(jìn)行狀態(tài)空間的搜索。

?

2 P狀態(tài)和N狀態(tài)：假設(shè)雙方都采取最明智的策略，則對于一些狀態(tài)，剛完成走步的游戲者(Previous Player) 一定勝利，而對于其他狀態(tài)，下一個走步的游戲者(NextPlayer) 一定勝利。把兩種狀態(tài)稱為P狀態(tài)(P position) 和N狀態(tài)(N position) ，且有以下關(guān)系：

?

2 1. 所有終止?fàn)顟B(tài)是P狀態(tài)

?

2 2. 能一步到達(dá)P狀態(tài)的狀態(tài)為N狀態(tài)

?

2 3. 每一步都將到達(dá)N狀態(tài)的狀態(tài)為P狀態(tài)

?

2 我們也可以把P狀態(tài)稱為必?cái)B(tài)，N狀態(tài)稱為必勝態(tài)，含義是直觀的。以上關(guān)系實(shí)際上給出了一個遞推計(jì)算所有狀態(tài)的P-N標(biāo)號的算法。只要狀態(tài)集構(gòu)成一個n個結(jié)點(diǎn)m條邊的有向無環(huán)圖(directed acyclic graph, DAG) ，則可以按照拓?fù)漤樞蛟贠(m)時(shí)間內(nèi)計(jì)算所有狀態(tài)的標(biāo)號。可問題在于這樣的狀態(tài)往往有很多，能否通過數(shù)學(xué)方法直接判斷一個狀態(tài)是P狀態(tài)還是N狀態(tài)呢？

?

2 常見的組合博弈模型，有若干種，但也有很多情況，不能套用這些模型，要具體情況具體分析。

?

2 博弈樹模型

?

2 假設(shè)甲乙雙方在進(jìn)行這種二人游戲，從唯一的一個初始局面開始，如果輪到甲方走棋，甲方有很多種著法，但只能選擇一個著法進(jìn)行走棋。甲方走棋后，局面發(fā)生了變化，輪到乙方走棋，乙方也有很多種著法，但也只能選擇一個著法。從初始局面開始，甲乙兩方交替走棋，局面的變化可以表示成一個樹形結(jié)構(gòu)，這就是博弈樹（game-tree）。一種井字棋的博弈樹，如圖所示。

?

2 每個局面可以用博弈樹的一個結(jié)點(diǎn)來表示，某方獲勝、失敗或雙方平局的結(jié)點(diǎn)構(gòu)成了葉子結(jié)點(diǎn)。甲乙雙方在選擇著法時(shí)，不僅要考慮己方每一種著法的好壞，同時(shí)也要考慮對方會針對自己的每一種著法采取怎樣的著法來應(yīng)對。顯然，博弈樹是一種特殊的與或樹，“或”結(jié)點(diǎn)和“與”結(jié)點(diǎn)是逐層交替出現(xiàn)的。己方擴(kuò)展的結(jié)點(diǎn)之間是“或”關(guān)系，對方擴(kuò)展的結(jié)點(diǎn)之間是“與”關(guān)系。

?

2?Bash’s Game（巴什博弈）

?

2 所謂巴什博弈，是ACM題中最簡單的組合游戲，大致上是這樣的：

?

2 只有一堆n個物品，兩個人輪流從這堆物品中取物，規(guī)定每次至少取1個，最多取m個，最后取光者得勝。

?

2 顯然，如果n = m + 1，那么由于一次最多只能取m個，所以，無論先取者拿走多少個，后取者都能夠一次拿走剩余的物品，后者取勝。因此我們發(fā)現(xiàn)了如何取勝的法則：

?

2 如果 n = (m + 1) * r + s ，(r為任意自然數(shù)，s≤m)，即n%(m+1) != 0，則先取者肯定獲勝。

?

2 巴什博弈還是很好理解的，以你是先手的角度考慮。你想把對手給弄垮，那么每一局，你都必須構(gòu)建一個局勢，這個局勢就是每次都留給對手m+1的倍數(shù)個物品。因?yàn)?#xff0c;如果n=(m+1)r + s，(r為任意自然數(shù)，s≤m),那么先取者要拿走s個物品，如果后取者拿走k(≤m)個，那么先取者再拿走m+1-k個，結(jié)果剩下(m+1)(r-1)個,以后保持這樣的取法，那么先取者肯定獲勝。總之，要保持給對手留下(m+1)的倍數(shù)，就能最后獲勝。

?

2 這個游戲還可以有一種變相的玩法：兩個人輪流報(bào)數(shù)，每次至少報(bào)1個，最多報(bào)10個，誰能報(bào)到100者勝。

?

2 好運(yùn)！該死的英語四級！

?

2 Problem Description
大學(xué)英語四級考試就要來臨了， Kiki和Cici 在緊張的復(fù)習(xí)之余喜歡打牌放松。“升級”？“斗地主”？那多俗啊！作為計(jì)算機(jī)學(xué)院的學(xué)生，Kiki和Cici打牌的時(shí)候可沒忘記專業(yè)，她們打牌的規(guī)則是這樣的：
1、 總共n張牌；
2、 雙方輪流抓牌；
3、 每人每次抓牌的個數(shù)只能是2的冪次（即：1，2，4，8，16…）
4、 抓完牌，勝負(fù)結(jié)果也出來了：最后抓完牌的人為勝者；
假設(shè)Kiki和Cici都是足夠聰明并且每次都是Kiki先抓牌，請問誰能贏呢？

?

2 Input
輸入數(shù)據(jù)包含多個測試用例，每個測試用例占一行，包含一個整數(shù)n（1<=n<=1000）。

?

Output
若Kiki能贏的話輸出“Kiki”，否則輸出“Cici”，每個實(shí)例的輸出占一行。

?

Sample Input
1
3

?

Sample Output
Kiki
Cici

?

2 如果你是先手，考慮你的必勝態(tài)。注意，因?yàn)槿魏握麛?shù)都能寫成若干個2的整數(shù)次方冪之和。由于規(guī)定只能取2的某個整數(shù)次方冪，只要你留給對手的牌數(shù)為3的倍數(shù)時(shí)，那么你就必贏，因?yàn)榱粝?的倍數(shù)時(shí)，對手有兩種情況：

?

2 1：如果輪到對方抓牌時(shí)只剩3張牌，對方要么取1張，要么取2張，剩下的你全取走，win！

?

2 2：如果輪到對方抓牌時(shí)還剩3*k張牌，對手不管取多少，剩下的牌數(shù)是3*x+1或者3*x+2。輪到你時(shí)，你又可以構(gòu)造一個3的倍數(shù)。 所以無論哪種情況，當(dāng)你留給對手為3*k的時(shí)候，你是必勝的。

?

2 題目說Kiki先抓牌，那么當(dāng)牌數(shù)為3的倍數(shù)時(shí)，Kiki就輸了。否則Kiki就能利用先手優(yōu)勢將留給對方的牌數(shù)變成3的倍數(shù)，就必勝。

?

2 #include <iostream>
using namespace std;
int main ()
{
int N;
while ( cin >> N )
{
puts ( N % 3 != 0 ? “Kiki” : “Cici” );
}
return 0;
}

?

2 土地拍賣

?

2 Problem Description

?

2 小雞同學(xué)和鵬程同學(xué)始終沒有逃過退學(xué)的命運(yùn)，因?yàn)樗麄儧]有在程序設(shè)計(jì)競賽中獲獎，還為了爭搶莎莎大打出手。現(xiàn)在等待他們的只能回家種田。要種田得有田才行，小雞聽說街上正在舉行一場拍賣會，拍賣的物品正好就是一塊田地。于是，小雞帶上他的全部積蓄，沖往拍賣會。后來發(fā)現(xiàn)，整個拍賣會只有小雞和他的死對頭鵬程。通過打聽，小雞知道這場拍賣的規(guī)則是這樣的：剛開始底價(jià)為0，兩個人輪流開始加價(jià)，不過每次加價(jià)的幅度要在1～N之間，當(dāng)價(jià)格大于或等于田地的成本價(jià)M時(shí)，就把這塊田地賣給這次叫價(jià)的人。小雞和鵬程雖然比賽不行，但是對拍賣卻十分精通，而且他們兩個人都十分想得到這塊田地。所以他們每次都是選對自己最有利的方式進(jìn)行加價(jià)。由于抽簽決定，所以每次都是由小雞先開始加價(jià)，請問，第一次加價(jià)的時(shí)候，小雞要出多少才能保證自己買得到這塊地呢？

?

2 Input

?

2 本題目包含多組測試，請?zhí)幚淼轿募Y(jié)束(EOF)。每組測試占一行。每組測試包含兩個整數(shù)M和N(含義見題目描述，0<N，M<1100)

?

2

?

2 Output

?

2 對于每組數(shù)據(jù)，在一行里按遞增的順序輸出小雞第一次可以加的價(jià)。兩個數(shù)據(jù)之間用空格隔開。如果小雞在第一次無論如何出價(jià)都無法買到這塊土地，就輸出”none”。

?

2

?

2 Sample Input

?

2 4 2

?

2 3 2

?

2 3 5

?

2

?

2 Sample Output

?

2 1

?

2 None

?

2 3 4 5

?

2 int main()
{
int n,m;
while(scanf(“%d%d”,&m,&n)!=EOF)
{
if(m%(n+1)==0)
{
printf(“none\n”);
continue;
}

?

2 ????????if(m<=n)
{
printf(“%d”,m);
for(int i=m+1; i<=n; i++) printf(” %d”,i);
printf(“\n”);
continue;
}
printf(“%d\n”,m%(n+1));
}
return 0;
}

?

2 減法博弈

?

2 巴什博弈有一種變形，叫做減法博弈。用s表示一個正整數(shù)構(gòu)成的集合，基于S所定義的減法游戲可以描述如下
：

?

2 有一個由n個石子組成的石子堆，兩名玩家輪流從中拿走石子，每次拿走石子的個數(shù)只能是集合S中的數(shù)。拿走最后一枚石子的玩家獲勝。

?

2 例：S = {1, 3, 4}，如果在游戲的開始有100枚石子，那么哪個玩家獲勝？

?

• 使用向后歸納的方法，可以計(jì)算出游戲的P位置和N位置如下：
• 通過觀察發(fā)現(xiàn)，該游戲中的P位置（必?cái)B(tài)）是那些能被7整除或者模7余2的位置，其他位置都是N位置（必勝態(tài)）。用數(shù)學(xué)歸納法可以證明這個結(jié)論是正確的。
• 事實(shí)上，如果k是P態(tài)（自己必?cái)?#xff09;，那么P+1、P+3、P+5能夠到達(dá)的位置，是N態(tài)（對方必?cái)?#xff09;，其他位置是P態(tài)。
• 游戲的起始位置100是P位置，所以先手輸。

?

2?Wythoff’s Game?（威佐夫博弈）

?

2 所謂威佐夫博弈，是ACM題中常見的組合游戲中的一種，大致上是這樣的：

?

2 有兩堆石子，不妨先認(rèn)為一堆有 10，另一堆有 15 個，雙方輪流取走一些石子，合法的取法有如下兩種：

?

2 1、在一堆石子中取走任意多顆；

?

2 2、在兩堆石子中取走相同多的任意顆；

?

2 約定取走最后一顆石子的人為贏家，求必勝策略。

?

2 兩堆石頭地位是一樣的，我們用余下的石子數(shù)(a,b)來表示狀態(tài)，并畫在平面直角坐標(biāo)系上。

?

2 和前面類似，(0,0)肯定是 P 態(tài)，又叫必?cái)B(tài)。(0,k),(k,0),(k,k)系列的節(jié)點(diǎn)肯定不是 P 態(tài)，而是必勝態(tài)，你面對這樣的局面一定會勝，只要按照規(guī)則取一次就可以了。再看 y = x 上方未被劃去的格點(diǎn)，(1,2)是 P 態(tài)。k > 2 時(shí)，(1,k)不是 P 態(tài)，比如你要是面對(1,3)的局面，你是有可能贏的。同理，(k,2)，(1 + k, 2 + k)也不是 P 態(tài)，劃去這些點(diǎn)以及它們的對稱點(diǎn)，然后再找出 y = x 上方剩余的點(diǎn)，你會發(fā)現(xiàn)(3,5)是一個 P 態(tài)，如此下去，如果我們只找出 a ≤ b 的 P 態(tài)，則它們是(0,0)，(1,2)，(3,5)，(4,7)，(6,10)……它們有什么規(guī)律嗎？

?

2 忽略(0,0)，很快會發(fā)現(xiàn)對于第 i 個 P 態(tài)的 a，a = i * (sqrt(5) + 1)/2 然后取整；而 b = a + i。居然和黃金分割點(diǎn)扯上了關(guān)系。

?

2 前幾個必?cái)↑c(diǎn)如下：(0,0)，(1,2)，(3,5)，(4,7)，(6,10)，(8,13)……可以發(fā)現(xiàn)，對于第k個必?cái)↑c(diǎn)(m(k),n(k))來說，m(k)是前面沒有出現(xiàn)過的最小自然數(shù)，n(k)=m(k)+k。

?

2 判斷一個點(diǎn)是不是必?cái)↑c(diǎn)的公式與黃金分割有關(guān)（我無法給出嚴(yán)格的數(shù)學(xué)證明，誰能給出嚴(yán)格的數(shù)學(xué)證明記得告訴我），為：

?

2 m(k) = k * (1 + sqrt(5))/2

?

2 n(k) = m(k) + k

?

2 一個必?cái)↑c(diǎn)有如下性質(zhì)：

?

2 性質(zhì)1：所有自然數(shù)都會出現(xiàn)在一個必?cái)↑c(diǎn)中，且僅會出現(xiàn)在一個必?cái)↑c(diǎn)中；

?

2 性質(zhì)2：規(guī)則允許的任意操作可將必?cái)↑c(diǎn)移動到必勝點(diǎn)；

?

2 性質(zhì)3：一定存在規(guī)則允許的某種操作可將必勝點(diǎn)移動到必?cái)↑c(diǎn)；

?

2 下面我們證明這3個性質(zhì)。

?

2 性質(zhì)1：所有自然數(shù)都會出現(xiàn)在一個必?cái)↑c(diǎn)中，且僅會出現(xiàn)在一個必?cái)↑c(diǎn)中；

?

2 證明：m(k)是前面沒有出現(xiàn)過的最小自然數(shù)，自然與前k-1個必?cái)↑c(diǎn)中的數(shù)字都不同；m(k)>m(k-1)，否則違背m(k-1)的選擇原則；n(k)=m(k)+k>m(k-1)+(k-1)=n(k-1)>m(k-1)，因此n(k)比以往出現(xiàn)的任何數(shù)都大，即也沒有出現(xiàn)過。又由于m(k)的選擇原則，所有自然數(shù)都會出現(xiàn)在某個必?cái)↑c(diǎn)中。性質(zhì)1證畢。

?

2 性質(zhì)2：規(guī)則允許的任意操作可將必?cái)↑c(diǎn)移動到必勝點(diǎn)；

?

2 證明：以必?cái)↑c(diǎn)(m(k),n(k))為例。若只改變兩個數(shù)中的一個，由于性質(zhì)1，則得到的點(diǎn)一定是必勝點(diǎn)；若同時(shí)增加兩個數(shù)，由于不能改變兩數(shù)之差，又有n(k)-m(k)=k，故得到的點(diǎn)也一定是必勝點(diǎn)。性質(zhì)2證畢。

?

2 性質(zhì)3：一定存在規(guī)則允許的某種操作可將必勝點(diǎn)移動到必?cái)↑c(diǎn)；

?

2 證明：以某個必勝點(diǎn)(i,j)為例，其中j>i。因?yàn)樗凶匀粩?shù)都會出現(xiàn)在某個必?cái)↑c(diǎn)中，故要么i等于m(k)，要么j等于n(k)。

?

2 若i=m(k)，j>n(k)，可從j中取走j-n(k)個石子到達(dá)必?cái)↑c(diǎn)；

?

2 若i=m(k)，j<n(k)，可從兩堆同時(shí)拿走m(k)-m(j-m(k))，注意此時(shí)j-m(k) < n(k)-m(k) < k，從而到達(dá)必?cái)↑c(diǎn)( m(j-m(k))，m(j-m(k))+j-m(k))；

?

2 若i>m(k)，j=n(k)，可從i中取走i-m(k)個石子到達(dá)必?cái)↑c(diǎn)；

?

2 若i<m(k)，j=n(k)，需要再分兩種情況，因?yàn)閕一定也出現(xiàn)在某個必?cái)↑c(diǎn)中，若i=m(l)，則從j中拿走j-n(l)，若i=n(l)，則從j中拿走j-m(l)，從而到達(dá)必?cái)↑c(diǎn)(m(l),n(l))。

?

2 性質(zhì)3證畢。

?

2 移動的皇后

?

2 Problem Description

?

2 一個n * n棋盤上有一個皇后。每個人可以把它往左或下或左下45度移動任意多步。把皇后移動至左下角的游戲者獲勝。現(xiàn)在給出皇后初始的X坐標(biāo)和Y坐標(biāo)，如果輪到你先走，假設(shè)雙方都采取最好的策略，問最后你是勝者還是敗者。

?

2 Input
輸入包含若干行，表示若干種皇后的初始情況，其中每一行包含兩個非負(fù)整數(shù)a和b，表示皇后的初始坐標(biāo)，a和b都不大于1,000,000,000。

?

2 Output
輸出對應(yīng)也有若干行，每行包含一個數(shù)字1或0，如果最后你是勝者，則為1，反之，則為0。

?

2 Sample Input

?

2 2 1
8 4
4 7

?

2 Sample Output

?

2 0
1
0

?

2 #include <iostream>

?

2 using namespace std;

?

2 int main()

?

2 {

?

2 ????int m,n;

?

2 ????while(cin>>m>>n)

?

2 ????{
if (m > n) { int temp; temp = m; m = n; n =temp; }

?

2 ?????????int k = n – m;

?

2 ?????????int data = floor(k*(1.0+sqrt(5.0))/2.0);

?

2 ?????????if (data == m) cout<<0<<endl;

?

2 ????}

?

2 }

?

2?Ferguson博弈（清空/分割游戲）

?

2?清空/分割游戲也叫做Ferguson博弈。進(jìn)行游戲需要用到兩個盒子。在游戲的開始，第一個盒子中有n枚石子，第二個盒子中有m個石子(n, m > 0)。參與游戲的兩名玩家輪流執(zhí)行這樣的操作：清空一個盒子中的石子，然后從另一個盒子中拿若干石子到被清空的盒子中，使得最后兩個盒子都不空。當(dāng)兩個盒子中都只有一枚石子時(shí)，游戲結(jié)束。最后成功執(zhí)行操作的玩家獲勝。找出游戲中所有的P位置。

?

2 對于一個位置(x, y)來說，如果x, y中有一個偶數(shù)，那么(x, y)是N（必勝）位置。如果x和y都是奇數(shù)，那么(x, y)是P位置（必?cái)?#xff09;。可以用數(shù)學(xué)歸納法證明。

?

2 證明（引自數(shù)學(xué)系唐思斯老師的證明）：

?

2 證明結(jié)論：(x,y)至少一偶時(shí)，先手勝；都為奇時(shí)，先手?jǐn)?/p>

?

2 證明：

?

2 (x,y)=(1,1)時(shí)是先手必?cái)B(tài)

?

2 下對max(x,y)>1進(jìn)行歸納

?

2 1、當(dāng)max(x,y)=2時(shí)，即(x,y)=(1,2)或（2,1）或（2,2），先手留下一個2分為（1,1），先手獲勝

?

2 即當(dāng)max(x,y)=2時(shí)結(jié)論成立。

?

2 2、假設(shè)max(x,y)<k時(shí)結(jié)論都成立，現(xiàn)證max(x,y)=k時(shí)結(jié)論成立

?

2 若（x,y)中有一個偶數(shù)(設(shè)為a)，先手將另一個清空，把偶數(shù)a分為兩個奇數(shù)b和c，由于b、c<a 小于等于 k，即max(b,c)<k,由假設(shè)，在（b,c)位置上后手作為新先手必?cái)?#xff0c;故先手勝

?

2 若(x,y)都為奇數(shù)，先手只能保留一個奇數(shù)并將其分解為一奇a一偶b,由于max(a,b)<max(x,y)=k,由假設(shè)，在（a,b)位置上后手作為新先手必勝，故先手?jǐn)?/p>

?

2 Chomp! 博弈（巧克力游戲）

?

2 情人節(jié)的時(shí)候，潘典安買了一塊長方形的棋盤巧克力，和他最愛的女友一起吃，巧克力由n*m塊格子組成。為了增加情人節(jié)的情趣，潘典安和她女友輪流選擇一個格子，并把這個格子右面，上面和右上方的巧克力全部取走。取到左下角格子的玩家輸，就要給對方一個熱烈的吻。假設(shè)每次都是潘典安先手，他是否存在必勝策略呢？

?

2 下圖可以看作是一個3*8的巧克力被拿掉(6,2)和(3,2)兩塊后剩下的形狀：

?

2 答案是除了1*1的棋盤，對于其他大小的棋盤，先手總能贏。有一個很巧妙的證明可以保證先手存在必勝策略，可惜這個證明不是構(gòu)造性的，也就是說沒有給出先手怎么下才能贏。證明如下：

?

2 如果后手能贏，也就是說后手有必勝策略，使得無論先手第一次取哪個石子，后手都能獲得最后的勝利。那么現(xiàn)在假設(shè)先手取最右上角的石子(n,m)，接下來后手通過某種取法使得自己進(jìn)入必勝的局面。但事實(shí)上，先手在第一次取的時(shí)候就可以和后手這次取的一樣，進(jìn)入必勝局面了，與假設(shè)矛盾。

?

2?Fibonacci’s Game?（斐波那契博弈）

?

2 斐波那契博弈模型，是ACM題中常見的組合游戲中的一種，大致上是這樣的：

?

2 有一堆個數(shù)為 n 的石子，游戲雙方輪流取石子，滿足：

?

2 1. 先手不能在第一次把所有的石子取完；

?

2 2. 之后每次可以取的石子數(shù)介于 1 到對手剛?cè)〉氖訑?shù)的 2 倍之間（包含 1 和對手剛?cè)〉氖訑?shù)的 2 倍）。

?

2 約定取走最后一個石子的人為贏家，求必?cái)B(tài)。

?

2 這個和之前的威佐夫博弈和取石子游戲有一個很大的不同點(diǎn)，就是游戲規(guī)則的動態(tài)化。之前的規(guī)則中，每次可以取的石子的策略集合是基本固定的，但是這次有規(guī)則2：一方每次可以取的石子數(shù)依賴于對手剛才取的石子數(shù)。

?

2 這個游戲叫做Fibonacci Nim，肯定和Fibonacci數(shù)列f[n]：1,2,3,5,8,13,21,34,55,89,… 有密切的關(guān)系。如果試驗(yàn)一番之后，可以猜測：先手勝當(dāng)且僅當(dāng)n不是Fibonacci數(shù)。換句話說，必?cái)B(tài)構(gòu)成Fibonacci數(shù)列。

?

2 下面簡單談?wù)劇跋仁謹(jǐn)‘?dāng)且僅當(dāng)n為Fibonacci數(shù)列”這一結(jié)論是怎么得來的。

?

2 這里要用到一個很有用的定理：任何正整數(shù)可以表示為若干個不連續(xù)的 Fibonacci 數(shù)之和。

?

2 這里定理涉及到數(shù)論，這里不做證明，想要知道證明過程的請找你們數(shù)學(xué)老師。下面只談如何把一個正整數(shù)表示為若干個不連續(xù)的 Fibonacci 數(shù)之和。

?

2 比如，我們要分解83，注意到83被夾在55和89之間，于是把83可以寫成83=55+28；然后再想辦法分解28，28被夾在21和34之間，于是28=21+7；依此類推 7=5+2，故83=55+21+5+2。

?

2 如果 n 是 Fibonacci 數(shù)，比如 n = 89。89前面的兩個Fibonacci 數(shù)是34和55。如果先手第一次取的石子不小于 34 顆，那么一定后手贏，因?yàn)?89 – 34 = 55 = 34 + 21 < 2*34，注意55是Fibonacci數(shù)。此時(shí)后手只要將剩下的全部取光即可，此時(shí)先手必?cái)　９手恍枰紤]先手第一次取得石子數(shù) < 34 即可，于是剩下的石子數(shù) x 介于 55 到 89 之間，它一定不是一個 Fibonacci 數(shù)。于是我們把 x 分解成 Fibonacci 數(shù)：x = 55 + f[i] + … + f[j]，其中55 > f[i] > … > f[j]，如果 f[j] ≤ 先手一開始所取石子數(shù) y 的兩倍，那么對后手就是面臨 x 局面的先手，所以根據(jù)之前的分析，后手只要先取 f[j] 個即可，以后再按之前的分析就可保證必勝。

?

2 下證：f[j] ≤ 2y

?

2 反證法：假設(shè)f[j]>2y，則 y < f[j]/2 = (f[j-1] + f[j-2])/2 < f[j-1]。而最初的石子數(shù)是個斐波那契數(shù)，即 n = f[k] = x + y < f[k-1] + f[i] + … + f[j] + f[j-1] ≤ f[k-1]+f[i]+f[i-1] ≤ f[k-1]+f[k-2] ≤ f[k] （注意第一個不等號是嚴(yán)格的），矛盾！f[j] ≤ 2y得證。

?

2 如果 n 不是 Fibonacci 數(shù)，比如n=83，我們看看這個分解有什么指導(dǎo)意義：假如先手取2顆，那么后手無法取5顆或更多，而5是一個Fibonacci數(shù)，如果猜測正確的話，（面臨這5顆的先手實(shí)際上是整個游戲的后手）那么一定是整個游戲的先手取走這5顆石子中的最后一顆，而這個我們可以通過第二類歸納法來繞過，同樣的道理，根據(jù)“先手?jǐn)‘?dāng)且僅當(dāng)n為Fibonacci數(shù)列”，接下去先手取走接下來的后21顆中的最后一顆，再取走后55顆中的最后一顆，那么先手贏。

?

2?尼姆博弈(Nimm’s Game)

?

2 尼姆博弈模型，是ACM題中常見的組合游戲中的一種，大致上是這樣的：

?

2 有3堆各若干個物品，兩個人輪流從某一堆取任意多的物品，規(guī)定每次至少取1個，多者不限，最后取光者得勝。

?

2 這種情況最有意思，它與二進(jìn)制有密切關(guān)系，我們用(a,b,c)表示某種局勢，首先(0,0,0)顯然是必?cái)B(tài)，無論誰面對(0,0,0) ，都必然失敗；第二種必?cái)B(tài)是(0,n,n)，自己在某一堆拿走k（k ≤ n）個物品，不論k為多少，對方只要在另一堆拿走k個物品，最后自己都將面臨(0,0,0)的局勢，必?cái)　Ｗ屑?xì)分析一下，(1,2,3)也是必?cái)B(tài)，無論自己如何拿，接下來對手都可以把局勢變?yōu)?0,n,n)的情形。

?

2 計(jì)算機(jī)算法里面有一種叫做按位模2加，叫做異或的運(yùn)算，我們用符號XOR表示這種運(yùn)算，這種運(yùn)算和一般加法不同的一點(diǎn)是1 XOR 1 = 0。先看(1,2,3)的按位模2加的結(jié)果：

?

2 1 = 二進(jìn)制01

?

2 2 = 二進(jìn)制10

?

2 3 = 二進(jìn)制11? XOR

?

2 ———————

?

2 0 = 二進(jìn)制00 (注意不進(jìn)位)

?

2

?

2 對于奇異局勢(0,n,n)也一樣，結(jié)果也是0。

?

2 任何奇異局勢(a,b,c)都有a XOR b XOR c = 0。

?

2 如果我們面對的是一個非必?cái)B(tài)(a,b,c)，要如何變?yōu)楸財(cái)B(tài)呢？假設(shè) a < b < c，我們只要將 c 變?yōu)閍 XOR b，即可。因?yàn)橛腥缦碌倪\(yùn)算結(jié)果：

?

2 a XOR b XOR (a XOR b)=(a XOR a) XOR (b XOR b) = 0 XOR 0 = 0。

?

2 要將c 變?yōu)閍 XOR b，只要對 c進(jìn)行 c-(a XOR b)這樣的運(yùn)算即可。

?

2 尼姆博弈模型可以推廣到：有n堆若干個物品，兩個人輪流從某一堆取任意多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。

?

2 這個游戲中的變量是堆數(shù)k和各堆的物品數(shù)N₁，N₂，……，N_k。對應(yīng)的組合問題是，確定先手獲勝還是后手獲勝以及兩個游戲人應(yīng)該如何取物品才能保證自己獲勝（獲勝策略）。

?

2 為了進(jìn)一步理解Nim取物品游戲，我們考查某些特殊情況。如果游戲開始時(shí)只有一堆物品，先手則通過取走所有的物品而獲勝。現(xiàn)在設(shè)有2堆物品，且物品數(shù)量分別為N₁和N₂。游戲者取得勝利并不在于N₁和N₂的值具體是多少，而是取決于它們是否相等。設(shè)N₁!=N₂，先手從大堆中取走的物品使得兩堆物品數(shù)量相等，后手再拿，于是，先手以后每次取子的數(shù)量與后手相等而最終獲勝。但是如果N₁= N₂，則：后手只要按著先手拿的數(shù)量在另一堆中取相等數(shù)量的物品，最終獲勝者將會是后手。這樣，兩堆的取子獲勝策略就已經(jīng)找到了。

?

2 現(xiàn)在我們?nèi)绾螐膬啥训娜∽硬呗詳U(kuò)展到任意堆數(shù)中呢？

?

2 首先來回憶一下，每個正整數(shù)都有對應(yīng)的一個二進(jìn)制數(shù)，例如：57_(10)?= 111001₍₂₎?，即：57₍₁₀₎=2⁵+2⁴+2³+2⁰。于是，我們可以認(rèn)為每一堆物品數(shù)由2的冪數(shù)的子堆組成。這樣，含有57枚物品大堆就能看成是分別由數(shù)量為2⁵、2⁴、2³、2⁰的各個子堆組成。

?

2 現(xiàn)在考慮各大堆大小分別為N₁，N₂，……N_k的一般的Nim博弈。將每一個數(shù)N_i表示為其二進(jìn)制數(shù)（數(shù)的位數(shù)相等，不等時(shí)在前面補(bǔ)0）：

?

2 N_1?= a_s…a₁a₀

?

2 N_2?= b_s…b₁b₀

?

2 ……

?

2 N_k?= m_s…m₁m₀

?

2 如果每一種大小的子堆的個數(shù)都是偶數(shù)，我們就稱Nim博弈是平衡的，而對應(yīng)位相加是偶數(shù)的稱為平衡位，否則稱為非平衡位。因此，Nim博弈是平衡的，當(dāng)且僅當(dāng)：

?

2 a_s?+b_s?+ … + m_s?是偶數(shù)，即a_s?XOR b_s?XOR … XOR m_s? = 0

?

2 ……

?

2 a_1?+b_1?+ … + m_1?是偶數(shù)，即a_1?XOR b₁?XOR … XOR m₁?= 0

?

2 a_0?+b₀?+ … + m₀是偶數(shù)，即a_0?XOR b₀?XOR … XOR m₀?= 0

?

2 于是，我們就能得出尼姆博弈中先手獲勝策略：

?

2?Bouton定理：先手能夠在非平衡尼姆博弈中取勝，而后手能夠在平衡的尼姆博弈中取勝。即，狀態(tài)(x₁, x₂, x₃, …, x_n)為P狀態(tài)當(dāng)且僅當(dāng)x₁?xor x₂?xor x₃?xor … xor x_n=0。這樣的操作也稱為Nim和(Nim Sum) 。

?

2 我們以一個兩堆物品的尼姆博弈作為試驗(yàn)。設(shè)游戲開始時(shí)游戲處于非平衡狀態(tài)。這樣，先手就能通過一種取子方式使得他取子后留給后手的是一個平衡狀態(tài)下的游戲，接著無論后手如何取子，再留給先手的一定是一個非平衡狀態(tài)游戲，如此反復(fù)進(jìn)行，當(dāng)后手在最后一次平衡狀態(tài)下取子后，先手便能一次性取走所有的物品而獲勝。而如果游戲開始時(shí)游戲牌平衡狀態(tài)，那根據(jù)上述方式取子，最終后手能獲勝。

?

2 下面應(yīng)用此獲勝策略來考慮4堆的Nim博弈。其中各堆的大小分別為7，9，12，15枚硬幣。用二進(jìn)制表示各數(shù)分別為：0111，1001，1100和1111。于是可得到如下一表：

?

2

?

2 由Nim博弈的平衡條件可知，此游戲是一個非平衡狀態(tài)的Nim博弈，因此，先手在按獲勝策略一定能夠取得最終的勝利。具體做法有多種，先手可以從大小為12的堆中取走11枚硬幣，使得游戲達(dá)到平衡（如下表），

?

2 之后，無論后手如何取子，先手在取子后仍使得游戲達(dá)到平衡。

?

2 同樣的道理，先手也可以選擇大小為9的堆并取走5枚硬幣而剩下4枚，或者，先手從大小為15的堆中取走13枚而留下2枚。

?

2 歸根結(jié)底， Nim博弈的關(guān)鍵在于游戲開始時(shí)游戲處于何種狀態(tài)（平衡或非平衡）和先手是否能夠按照取子游戲的獲勝策略來進(jìn)行游戲。

?

2 當(dāng)堆數(shù)大于2時(shí)，我們看出Bouton定理依舊適用，但還沒給出嚴(yán)格的證明，下面用數(shù)學(xué)歸納法證明。

?

2 證明：如果每堆都為0，顯然是P狀態(tài)（必?cái)?#xff09;。下面驗(yàn)證P狀態(tài)和N狀態(tài)的后兩個遞推關(guān)系：

?

2?一、每個N狀態(tài)都可以一步到達(dá)P狀態(tài)。

?

2 證明是構(gòu)造性的。檢查Nim和X的二進(jìn)制表示中最左邊一個1，則隨便挑一個該位為1的物品堆Y，根據(jù)Nim和進(jìn)行調(diào)整（0變1，1變0）即可。例如Nim和為100101011，而其中有一堆為101110001。為了讓Nim和變?yōu)?，只需要讓操作的物品數(shù)取操作前的物品數(shù)和Nim的異或即可。

?

2 顯然操作后物品數(shù)變小，因此和合法的。設(shè)操作前其他堆的Nim和為Z，則有Y xor Z = X。操作后的Nim和為X xor Y xor Z = X xor X = 0，是一個P狀態(tài)。

?

2?二、每個P狀態(tài)（必勝態(tài)）都不可以一步到達(dá)P狀態(tài)

?

2 由于只能改變一堆的物品，不管修改它的哪一位，Nim的對應(yīng)位一定不為0，不可能是P狀態(tài)。

?

2 這樣就證明了Bouton定理。

?

2 Nim博弈中如果規(guī)定最后取光者輸，情況是怎樣的？初看起來問題要復(fù)雜很多（因?yàn)椴荒苤鲃幽昧?#xff0c;而要“躲著”拿，以免拿到最后一個物品），事實(shí)上確實(shí)有很多游戲規(guī)則比普通規(guī)則要困難很多，但對于Nim游戲來說，幾乎是一樣的：

?

2 首先按照普通規(guī)則一樣的策略進(jìn)行，直到恰好有一個物品數(shù)大于1的堆x。在這樣的情況下，只需要把堆x中的物品拿得只剩1個物品或者拿完，讓對手面臨奇數(shù)堆物品，這奇數(shù)堆物品每堆恰好1個物品。這樣的狀態(tài)顯然是必?cái)〉摹Ｓ捎谀忝看尾僮骱笮枰ＷCNim和為0，因此不可能在你操作后首次出現(xiàn)“恰好有一個物品數(shù)大于1的堆”。新游戲得到了完美解決。

?

2?SG函數(shù)與SG定理

?

2 現(xiàn)在我們來研究一個看上去似乎更為一般的游戲：給定一個有向無環(huán)圖和一個起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動，無法移動者判負(fù)。事實(shí)上，這個游戲可以認(rèn)為是所有Impartial Combinatorial Games的抽象模型。也就是說，任何一個ICG都可以通過把每個局面看成一個頂點(diǎn)，對每個局面和它的子局面連一條有向邊來抽象成這個“有向圖游戲”。下面我們就在有向無環(huán)圖的頂點(diǎn)上定義Sprague-Garundy函數(shù)，簡稱SG函數(shù)。

?

2 首先定義mex(minimal excludant)運(yùn)算，這是施加于一個集合的運(yùn)算，表示最小的不屬于這個集合的非負(fù)整數(shù)。例如集合N={0,1,2,3,4,5,6}，則mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

?

2?Sprague-Grundy?函數(shù)是定義在組合游戲狀態(tài)上的函數(shù)，用g (X)表示X狀態(tài)的g函數(shù)值。它的定義如下：

?

2 g(x)=mex{ g(y) | y是x的后繼 }。

?

2 或者表示為：

?

2 g (X)= min{n| n∈N, n>=0,n≠ for y, y是x的后繼}

?

2 形象的說就是X的g函數(shù)值為X的后繼點(diǎn)的SG值中沒有出現(xiàn)過的最小值。

?

2 SG函數(shù)的性質(zhì)：

?

2 1、所有的終點(diǎn)（先手必?cái)B(tài)），也就是沒有出邊的頂點(diǎn)，其SG值為0，因?yàn)樗暮罄^集合是空集；

?

2 2、對于一個g(x)=0的頂點(diǎn)x，它的所有后繼y都滿足g(y)!=0；

?

2 3、對于一個g(x)!=0的頂點(diǎn)，必定存在一個后繼y滿足g(y)=0。

?

2 下面將引入Sprague-Grundy定理，簡稱SG定理，并給上述的SG函數(shù)的性質(zhì)進(jìn)行證明。

?

2 通過下面的定理可以建立SG函數(shù)與N局面和P局面的關(guān)系：

?

2?引理：對于任意的局面x，若g(x)=0則x是P局面（必?cái)B(tài)），否則x是N局面（必勝態(tài)）。

?

2 證明：我們對局面作數(shù)學(xué)歸納法：

?

2 1. 對于最終局面x，由定義x是P局面（必?cái)B(tài)），而此時(shí)g(x)=0， 引理成立。

?

2 2. 假設(shè)局面x的所有后繼局面都滿足引理。

?

3 若x的后繼局面中存在P局面（必?cái)B(tài)）y，則x是N局面（必勝態(tài)），同時(shí)g(y)=0，故g(x)不等于0；

?

3 若x的后繼局面y中不存在P局面，則顯然x是P局面；同時(shí)由于不存在g(y)=0，故g(x)=0。

?

2 由歸納假設(shè)，引理對于所有局面x成立。

?

2 我們通過計(jì)算有向無環(huán)圖的每個頂點(diǎn)的SG值，就可以對每種局面找到必勝策略了。

?

2 實(shí)際中，SG函數(shù)的用途遠(yuǎn)沒有這樣簡單。如果將有向圖游戲變復(fù)雜一點(diǎn)，比如說，有向圖上并不是只有一枚棋子，而是有n枚棋子，每次可以任選一顆進(jìn)行移動，這時(shí)，怎樣找到必勝策略呢？

?

2 再來考慮一下頂點(diǎn)的SG值的意義。當(dāng)g(x)=k時(shí)，表明對于任意一個0 ≤ i<k，都存在x的一個后繼y滿足g(y)=i。也就是說，當(dāng)某枚棋子的SG值是k時(shí)，我們可以把它變成0、變成1、……、變成k-1，但絕對不能保持k不變。不知道你能不能根據(jù)這個聯(lián)想到Nim游戲，Nim游戲的規(guī)則就是：每次選擇一堆數(shù)量為k的石子，可以把它變成0、變成1、……、變成k-1，但絕對不能保持k不變。這表明，如果將n枚棋子所在的頂點(diǎn)的SG值看作n堆相應(yīng)數(shù)量的石子，那么這個Nim游戲的每個必勝策略都對應(yīng)于原來這n枚棋子的必勝策略！

?

2 也就是說：游戲者可以通過一步走棋把圖的當(dāng)前狀態(tài)值任意的減小（當(dāng)然必須保證狀態(tài)值始終>=0）。

?

2 如果游戲者處在一個點(diǎn)x，g(x)=0。那么游戲者無論如何移動，下一個點(diǎn)的SG值都不等于0。

?

2 對于n個棋子，設(shè)它們對應(yīng)的頂點(diǎn)的SG值分別為(a₁,a₂,…,a_n)，再設(shè)局面(a₁,a₂,…,a_n)時(shí)的Nim游戲的一種必勝策略是把某個a_i變成k，那么原游戲的一種必勝策略就是把第i枚棋子移動到一個SG值為k的頂點(diǎn)。這聽上去有點(diǎn)過于神奇——怎么繞了一圈又回到Nim游戲上了。

?

2 可以用如下方式定義組合游戲的和：初始局面包含每個子游戲的初始局面，而每次每個游戲者可以任意選一個游戲，進(jìn)行一次合法走步，而讓其他游戲局面保持不變。

?

2 3堆火柴的Nim游戲可以作看是3個一堆火柴的Nim游戲之和。一堆Nim游戲是簡單的：直接把所有火柴拿掉即可；但3堆火柴卻復(fù)雜得多。看樣子，即使每個游戲都很簡單，它們的和也可能很復(fù)雜。

?

2 雖然看起來很復(fù)雜，但Sprague-Grundy定理提供了一個很好的方案解決這一問題：

?

2?Sprague-Grundy定理：游戲和的SG函數(shù)等于各子游戲SG函數(shù)的Nim和，即：設(shè)g_i(x)為G_i的SG函數(shù)(1 ≤ i ≤ n)，則G = G₁+ G₂+ … + G_n的SG函數(shù)g( x₁, x₂, …, x_n?) = g₁(x₁)⊕ g₂(x₂) ⊕ … ⊕ g_n(x_n)（其中⊕為異或運(yùn)算）。

?

2 證明：對于G的任意局面x ( x₁, x₂, …, x_n?}，設(shè)b = g₁(x₁)⊕ g₂(x₂) ⊕ … ⊕ g_n(x_n) ，對于任意一個非負(fù)整數(shù)a<b，如果我們能證明下面兩個事實(shí)：

?

2 （1）都存在x的一個后繼局面y，使得g(y)=a；

?

2 （2）不存在x的后繼局面y，使得g(y)=b；

?

2 則b就是滿足要求的x的SG函數(shù)值，命題也就隨之得證。

?

2 對于事實(shí)1，令d=a⊕b，設(shè)k是d的二進(jìn)制位的最高位，即2^k-1?≤ d < 2^k。 由于a<b，故a的第k位為0，b的第k位為1。故g₁(x₁)、 g₂(x₂) 、… 、g_n(x_n)中至少有一個二進(jìn)制位第k位為1，不妨設(shè)為g₁(x₁)，那么有d⊕g₁(x₁)< g₁(x₁)，根據(jù)SG函數(shù)g₁的定義，必存在x₁的一個后繼局面y₁，使得g₁(y₁)=d⊕g₁(x₁)。

?

2 故存在{x₁,x₂,…,x_n}的一個后繼局面{y₁,x₂,x₃,…,x_n}，它的SG函數(shù)值為：

?

2 g(y₁,x₂,x₃,…,x_n)=g₁(y₁)⊕g₂(x₂)⊕…⊕g_n(x_n)

?

2 ??????????????????????????= d⊕g₁(x₁)⊕g₂(x₂)⊕…⊕g_n(x_n) = d⊕b

?

2 ??????????????????????????= a⊕b⊕b = a

?

2 至此事實(shí)1成立

?

2 對于事實(shí)2，反設(shè)若存在這樣的后繼局面y，不妨設(shè)y={y₁,x₂,…,x_n}（y₁是x₁的后繼局面），?? 則有：

?

2 g₁(x₁)⊕g₂(x₂)⊕…⊕g_n(x_n) = g₁(y₁)⊕g₂(x₂)⊕…⊕g_n(x_n)

?

2 即：g₁(x₁)=g₁(y₁)，這與SG函數(shù)g₁的性質(zhì)矛盾。因此事實(shí)2成立。

?

2 由Sprague-Grundy定理可知，對于復(fù)雜的公平組合博弈，如果我們可以將它們分解成若干個子游戲的聯(lián)合，就可以通過求解子游戲的SG函數(shù)，方便地求得原游戲的SG函數(shù)，從而快速判斷勝負(fù)情況。

?

2 有了上面的公平組合博弈的理論為基礎(chǔ)，我們就可以來解決引言中提出的問題了。

?

2 保齡球游戲

?

2 在一行中有n個木瓶，你和你的朋友輪流用保齡球去打這些木瓶，由于你們都是高手，每一次都可以準(zhǔn)確的擊倒一個或相鄰的兩個木瓶，誰擊倒最后一個剩余的木瓶誰將獲得勝利。如果由你先打，請你分析，你應(yīng)該采取什么策略來確保贏得勝利？

?

2 分析：為了看清楚問題的本質(zhì)，用另一種方式來描述這個游戲。最開始有一堆石子（n個），每一次你可以進(jìn)行以下四種操作中的一種：

?

2 1. 從中取出一顆石子；

?

2 2. 從中取出兩顆石子；

?

2 3. 從一堆中取出一顆石子，并且將這一堆中余下的石子任意分成兩堆（每堆至少一顆）；

?

2 4. 從一堆中取出兩顆石子，并且將這一堆中余下的石子任意分成兩堆（每堆至少一顆）。

?

2 這四種操作，實(shí)際上就依次對應(yīng)于原來游戲中的以下四種擊倒法：

?

2 1. 擊倒一段連續(xù)的木瓶中最靠邊的一個；

?

2 2. 擊倒一段連續(xù)的木瓶中最靠邊的連續(xù)兩個；

?

2 3. 擊倒一段連續(xù)的木瓶中不靠邊的一個；

?

2 4. 擊倒一段連續(xù)的木瓶中不靠邊的連續(xù)兩個。

?

2 把局面看作頂點(diǎn)，游戲規(guī)則看作邊，這是一個典型的圖游戲。

?

2 如果當(dāng)前局面被分成了M堆，(A₁,A₂,…,A_m)，則SG(A₁,A₂,…,A_m) = SG(A₁)⊕SG(A₂)⊕…⊕SG(A_m)。對某一堆來說：

?

2 顯然，SG(0)=0。

?

2 剩余1個時(shí)，只能取到0個，而SG(0)=0，所以SG(1)=1。

?

2 剩余2個時(shí)，可以取到0或1，其中SG(0)=0，SG(1)=1，所以SG(2)=2。

?

2 剩余3個時(shí)，我們可以把局面變成1或2或兩堆均為1。

?

2 其中SG(1)=1，SG(2)=2，SG(1, 1)=SG(1) ⊕ SG(1)=0，所以SG(3)=3。

?

2 SG(4)可分解為{SG(2), SG(3),SG(2)⊕SG(1), SG(1)⊕SG(1)} ={2,3,3,0},所以SG(4)=1。

?

2 對于任意一種局面P，的SG值為SG(P)，為了贏得勝利，我們只需將他的局面變成Q，使得SG(Q)=0即可。

?

2 對于每一個N值，我們?yōu)榱饲蟪鏊腟G值，時(shí)間復(fù)雜度為O(N) ，如果只要求你求出你第一步應(yīng)該如何行動，那么這種普通的方法需要O(N²)的復(fù)雜度，顯然不能令我們滿意。

?

2 這個問題看似已經(jīng)解決，但我們可以進(jìn)行優(yōu)化。事實(shí)上，我們通過觀察較小的數(shù)的SG值，可以發(fā)現(xiàn)：

?

2 ?0 ~11的SG值為：0 1 2 3 1 4 3 2 1 4 2 6

?

2 12~23的SG值為：4 1 2 7 1 4 3 2 1 4 6 7

?

2 24~35的SG值為：4 1 2 8 5 4 7 2 1 8 6 7

?

2 36~47的SG值為：4 1 2 3 1 4 7 2 1 8 2 7

?

2 48~59的SG值為：4 1 2 8 1 4 7 2 1 4 2 7

?

2 60~71的SG值為：4 1 2 8 1 4 7 2 1 8 6 7

?

2 72~83的SG值為：4 1 2 8 1 4 7 2 1 8 2 7

?

2 并且從72開始，SG值以12為循環(huán)節(jié)，不斷的重復(fù)出現(xiàn)，這樣我們求出所有SG值的復(fù)雜度就降到了常數(shù)，這樣判斷第一步的如何選擇的復(fù)雜度就降為了O(N)。

?

2 具體問題具體分析

?

2 也有很多題目不能完全照搬上述模型的，這就需要具體問題具體分析。來看2011年湖南省程序設(shè)計(jì)競賽的題目E：

?

2 盒子游戲

?

2 題目大意：

?

2 有兩個相同的盒子，其中一個裝了n個球，另一個裝了一個球。Alice和Bob發(fā)明了一個游戲，規(guī)則如下：Alice和Bob輪流操作，Alice先操作。每次操作時(shí)，游戲者先看看哪個盒子里的球的數(shù)目比較少，然后清空這個盒子（盒子里的球直接扔掉），然后把另一個盒子里的球拿一些到這個盒子中，使得兩個盒子都至少有一個球。如果一個游戲者無法進(jìn)行操作，他（她）就輸了。

?

2 面對兩個各裝一個球的盒子，Bob無法繼續(xù)操作，因此Alice獲勝。你的任務(wù)是找出誰會獲勝。假定兩人都很聰明，總是采取最優(yōu)策略。

?

2 輸入

?

2 輸入最多包含300組測試數(shù)據(jù)。每組數(shù)據(jù)僅一行，包含一個整數(shù)n（2?≤?n?≤?109）。輸入結(jié)束標(biāo)志為n=0。

?

2 輸出

?

2 對于每組數(shù)據(jù)，輸出勝者的名字。

?

2 樣例輸入

?

2 2

?

2 3

?

2 4

?

2 0

?

2 樣例輸出

?

2 Alice

?

2 Bob

?

2 Alice

?

2 分析：

?

2 這個題目，無法套用巴什博弈、威佐夫博弈、斐波那契博弈、尼姆博弈這四個常見模型，和清空/分割游戲也有差別。如果用萬能的alpha-beta剪枝算法絕對超時(shí)。怎么辦？不妨耐心的仔細(xì)分析，找出規(guī)律，因?yàn)楦傎愵}都是應(yīng)試教育下的變態(tài)產(chǎn)物（不過也能培養(yǎng)一頂?shù)哪芰?#xff09;，你要做出這類題，第一是要有耐心，第二是你的思維要比出題的劉汝佳之流更加變態(tài)才行。

?

2 仔細(xì)分析，可以發(fā)現(xiàn)，既然球數(shù)量少的盒子里的球都是要丟棄的，這道題可以轉(zhuǎn)換為，在一個剩下n個球的盒子里，拿走k個球，其中1 ≤ k ≤ int(n/2)，還剩下int(n – k)個球。如果某個游戲者面對盒子里的球只剩下1個，即n=1時(shí)，就敗了。引入函數(shù)win(n)，表示這個盒子剩下的球數(shù)為n時(shí)，當(dāng)前游戲者是否能獲得必勝態(tài)，由于不存在平局，當(dāng)win(n)=1時(shí)，當(dāng)前游戲者能獲得必勝態(tài)，當(dāng)win(n)=0時(shí)由于對手足夠聰明，當(dāng)前游戲者只能獲得必?cái)B(tài)。所以：

?

2 n=1時(shí)，根據(jù)游戲規(guī)則，對當(dāng)前游戲者來說是必?cái)B(tài)，即win(1) = 0。

?

2 n>1時(shí)，對當(dāng)前游戲者拿走k個球，還剩下r個球留給對方，r = n – k，其中1 ≤ k ≤ (int)(n/2)，這樣，r就有個范圍，即int((n + 1)/2) ≤ r ≤ n – 1。博弈樹是一種特殊的與或樹，“或”結(jié)點(diǎn)和“與”結(jié)點(diǎn)是逐層交替出現(xiàn)的。己方擴(kuò)展的結(jié)點(diǎn)之間是“或”關(guān)系，對方擴(kuò)展的結(jié)點(diǎn)之間是“與”關(guān)系（關(guān)于博弈樹的這段話關(guān)緊要，看不懂的同學(xué)可以掠過，看得懂的同學(xué)能在瞬間明白是怎么回事）。所以只要win(int((n + 1)/2))、win(int((n + 1)/2) + 1)、win(int((n + 1)/2) + 2)、…、win(n – 1)中所有的值是1，那么對方都必勝，自己就只能獲得必?cái)B(tài)；但是，只要win(int((n + 1)/2))、win(int((n + 1)/2) + 1)、win(int((n + 1)/2) + 2)、…、win(n – 1)中存在某個值是0，那么自己可以獲得必勝態(tài)。

?

2 換句話來說：

?

2 一旦發(fā)現(xiàn)某個r值使得win(r) = 0，則從win(r + 1)到win(2 * r)的值都是1；

?

2 一旦發(fā)現(xiàn)win(r + 1)到win(2 * r)的值都是1，則win(2 * r + 1) = 0；

?

2 ……

?

2 上述分析很重要，搞明白上述分析后，

?

2 r = 1時(shí)，已知win(1) = 0，能推出win(2) = 1，以及win(3) = 0。

?

2 r = 3時(shí)，由win(3) = 0，又能推出win(4) = win(5) = win(6) = 1，以及win(7) = 0。

?

2 r = 7時(shí)，由win(7) = 0，又能推出win(8) = win(9) = … = win(14) = 1，以及win(15) = 0。

?

2 r = 15時(shí)，由于win(15) = 0，又能推出win(16) = win(17) = … = win(30) = 1，以及win(31) = 0。

?

2 r = 31時(shí)，由于win(31) = 0，又能推出win(32) = win(33) = … = win(62) = 1，以及win(63) = 0。

?

2 ……

?

2 自此，由數(shù)學(xué)歸納法可以證明，只有n = (int)pow(2, m) – 1時(shí)（m為非負(fù)整數(shù)），win(n) = 0，當(dāng)前游戲者面臨必?cái)B(tài)，除此之外，當(dāng)前選手都能面臨必勝態(tài)！

?

2 求win函數(shù)的代碼我寫了一個，只有寥寥數(shù)行。

?

2 農(nóng)大公布的標(biāo)準(zhǔn)程序采用的是遞歸的方法，我個人認(rèn)為沒有我上面的算法效率高，我的算法實(shí)質(zhì)上就是判斷n+1是不是構(gòu)成2的某個非負(fù)整數(shù)次方冪。

?

2 豬縣長同學(xué)寫的程序可能效率更高，他采用的是預(yù)制表的辦法，將問題規(guī)模內(nèi)的2的所有整數(shù)次方冪-1的值放在一個向量或者數(shù)組中，然后用類似二分查找的辦法去找，找到了就是先手必勝，否則先手必?cái)　?/p>

?

2 #include <iostream>

?

2 using namespace std;

?

2 int Win(int n)

?

2 {

?

2 ????int m = log(n + 1) / log(2);

?

2 ????int k = pow(2, m);

?

2 ????if(k == n + 1) return 0; //先手必?cái)?/p>

?

2 ????return 1; //先手必勝

?

2 }

?

2 int main()

?

2 {

?

2 ????int n;

?

2 ????cin >> n;

?

2 ????while( n > 0)

?

2 ????{

?

2 ????????if(Win(n)) cout << “Alice\n”;

?

2 ????????else cout << “Bob\n”;

?

2 ????????cin >> n;

?

2 ????}

?

2 ????return 0;

?

2 }

總結(jié)

以上是生活随笔為你收集整理的组合博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。