Nim游戲：　

? ?1. 一個(gè)狀態(tài)是必?cái)顟B(tài)當(dāng)且僅當(dāng)它的所有后繼都是必勝狀態(tài)。

　2. 一個(gè)狀態(tài)是必勝狀態(tài)當(dāng)且僅當(dāng)它至少有一個(gè)后繼是必?cái)顟B(tài)。

對(duì)于Nim游戲來(lái)說(shuō)，早有科學(xué)家給出了一個(gè)定理（Bouton定理）：狀態(tài)（x1,x2.....xn）為必?cái)顟B(tài)當(dāng)且僅當(dāng)x1^x2^......^xn= 0，即把所有數(shù)進(jìn)行異或和操作，也稱Nim sum。【能夠證明，當(dāng)Nim sum為0 時(shí)為必?cái)顟B(tài)，非0 時(shí)為必勝狀態(tài)，這是因?yàn)?#xff0c;當(dāng)前狀態(tài)為0 時(shí)，進(jìn)行的某個(gè)操作總能使Nim sum變?yōu)榉?（因?yàn)楦淖內(nèi)魏我粋€(gè)數(shù)字（即任何一堆石子），它的二進(jìn)制形式會(huì)有一位或多位的變化，此時(shí)原本各位上都為0 的Nim sum就會(huì)有所變動(dòng)（某些位會(huì)變成1）），即所有后繼都是必勝狀態(tài)了；當(dāng)前狀態(tài)為非0 時(shí)，必定會(huì)有某個(gè)操作能使Nim sum變?yōu)?（只需在Nim sum二進(jìn)制上那些為1的位上面著手即可），即一定有一個(gè)后繼狀態(tài)為必?cái)B(tài)。這就是Bouton定理。】

Bouton定理實(shí)質(zhì)上是SG定理的具體應(yīng)用。什么是SG定理呢？

SG定理：

Sprague-Grundy定理（SG定理）：游戲和的SG函數(shù)等于各個(gè)游戲SG函數(shù)的Nim和。這樣就可以將每一個(gè)子游戲分而治之，從而簡(jiǎn)化了問(wèn)題。而B(niǎo)outon定理就是Sprague-Grundy定理在Nim游戲中的直接應(yīng)用，因?yàn)閱味训腘im游戲 SG函數(shù)滿足 SG(x) = x。

對(duì)于SG定理：

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

這一步應(yīng)該是非常簡(jiǎn)單的，就是定義了新的運(yùn)算為mex。

對(duì)于任意狀態(tài) x ， 定義 SG(x) = mex(S)，其中S是 x 后繼狀態(tài)的SG函數(shù)值的集合（就是上述mex中的數(shù)值）。最后返回值（也就是SG(X)）為0為必?cái)↑c(diǎn)，不為零必勝點(diǎn)。

進(jìn)一步解釋一下S，就是題意中給出的可以移動(dòng)的次數(shù)。舉個(gè)例子來(lái)說(shuō)，一堆石子，每次只能拿1，3，5，7個(gè)，那么S數(shù)組就是1，3，5，7。

假如說(shuō)是在一個(gè)游戲中有多個(gè)石子堆該怎么辦了。我們只需要把對(duì)每個(gè)石子堆進(jìn)行sg函數(shù)的調(diào)用，將得到的所有的值進(jìn)行異或。得出來(lái)的結(jié)果為0則該情形為必?cái)B(tài)。否則為必勝態(tài)。

#include<cstdio> #include <iostream> #include <cstring> using namespace std; const int MAX_N = 100; int sg[MAX_N];//sg函數(shù) bool vis[MAX_N];//標(biāo)記數(shù)組void solve(int n) {memset(vis, false, sizeof(vis));for (int i = 0; i < n; ++i)vis[sg[i]] = true;for (int i = 1; i <= n; ++i)//因?yàn)榭梢苑殖蓛啥?#xff0c;如果三堆，就寫(xiě)三重循環(huán)for (int j = 1; j <= n; ++j) {if (i + j == n) vis[sg[i] ^ sg[j]] = true;}int i;for (i = 0; ; ++i)//沒(méi)有i < n，如果都不成立，最后i = nif (!vis[i]) break;sg[n] = i;cout << "sg[" << n << "]=" << i << endl; }

?

總結(jié)

以上是生活随笔為你收集整理的博弈——sg函数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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