參考博客：https://baike.baidu.com/item/SG%E5%87%BD%E6%95%B0/1004609

https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

主要參考百度百科：

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

對于任意狀態(tài) x ， 定義 SG(x) = mex(S),其中 S 是 x 后繼狀態(tài)的SG函數(shù)值的集合。如 x 有三個后繼狀態(tài)分別為?SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。?這樣 集合S 的終態(tài)必然是空集，所以SG函數(shù)的終態(tài)為 SG(x) = 0,當且僅當 x 為必敗點P時。

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

首先，所有的terminal position（目標位置）所對應的頂點，也就是沒有出邊的頂點，其SG值為0，因為它的后繼集合是空集。然后對于一個g(x)=0的頂點x，它的所有前驅(qū)y都滿足 g(y)!=0。對于一個g(x)!=0的頂點，必定存在一個后繼y滿足g(y)=0。

表明，頂點x所代表的postion（位置）是P-position（必敗點）當且僅當g(x)=0。

?

SG值的意義：

1，當g(x)=k時，表明對于任意一個0<=i<k，都存在x的一個后繼y滿足g(y)=i。為什么一定存在呢？

?因為mex函數(shù)運算時，g(y)等于最小的不屬于（y后繼狀態(tài)）這個集合的非負整數(shù)，換言之，y的后繼狀態(tài)一定有 [0,k-1] 這個范圍，才會出現(xiàn)g(x)=k,k為不小于后繼狀態(tài)（集合），因為函數(shù)g就是按照mex運算得來的。

2，當某枚棋子的SG值是k時，我們可以把它變成0、變成1、……、變成k-1，但絕對不能保持k不變。這個聯(lián)想到Nim游戲， Nim游戲的規(guī)則就是：每次選擇一堆數(shù)量為k的石子，可以把它變成0、變成1、……、變成k-1，但絕對不能保持k不變。這表明，如果將n枚棋子所在的頂 點的SG值看作n堆相應數(shù)量的石子，那么這個Nim游戲的每個必勝策略都對應于原來這n枚棋子的必勝策略！

3，對于n個棋子，設(shè)它們對應的頂點的SG值分別為(a1,a2,…,an)，再設(shè)局面(a1,a2,…,an)時的Nim游戲的一種必勝策略是把ai 變成k，那么原游戲的一種必勝策略就是把第i枚棋子移動到一個SG值為k的頂點。這就相當于可以看做，每次最聰明的操作是按照Nim游戲SG(N)值來移動，例如我們想把SG(N)變?yōu)?span style="color:#f33b45;">SG(小于N)，就滿足最聰明移動，但我們真正移動的又不是SG(N)的值，移動的是原來頂點N的值，咦，好像也是哦，沒關(guān)系，我們依舊移頂點N的值，只是說移動頂點N的值時，要滿足移動后頂點值（小于N），SG(小于N)的值是我們想要的最聰明的SG值。 ? ? ? ?

? ? ? ? ? ? ?

這就好像我們敲代碼，我們通過高級程序語言來間接寫機器語言運行計算機。

?

計算1~n的SG函數(shù)值步驟如下：

1、使用 數(shù)組f 將 可改變當前狀態(tài) 的方式記錄下來。

2、然后我們使用 另一個數(shù)組 將當前狀態(tài)x 的后繼狀態(tài)標記。

3、最后模擬mex運算，也就是我們在標記值中 搜索 未被標記值 的最小值，將其賦值給SG(x)。

4、我們不斷的重復 2 - 3 的步驟，就完成了 計算1~n 的函數(shù)值

代碼：

//f[N]:可改變當前狀態(tài)的方式，N為方式的種類，f[N]要在getSG之前先預處理 //SG[]:0~n的SG函數(shù)值 //S[]:為x后繼狀態(tài)的集合 int f[N],SG[MAXN],S[MAXN]; void getSG(int n){int i,j;memset(SG,0,sizeof(SG));//因為SG[0]始終等于0，所以i從1開始for(i = 1; i <= n; i++){//每一次都要將上一狀態(tài) 的 后繼集合 重置memset(S,0,sizeof(S));for(j = 0; f[j] <= i && j <= N; j++)S[SG[i-f[j]]] = 1; //將后繼狀態(tài)的SG函數(shù)值進行標記for(j = 0;; j++) if(!S[j]){ //查詢當前后繼狀態(tài)SG值中最小的非零值SG[i] = j;break;}} }

?

給出一道入門級的題目：

hdu 1848

#include <cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=1010; #define N 20 int f[N],SG[MAXN],S[MAXN];///f[]可走步數(shù)//S[]后繼存在狀態(tài) void getSG(int n){int i,j;memset(SG,0,sizeof(SG));///PN點for(i = 1; i <= n; i++){///從i=1開始memset(S,0,sizeof(S));///每次初始化S[]后繼存在狀態(tài)for(j = 0; f[j] <= i && j < N; j++)///f[i]<i;S[SG[i-f[j]]] = 1;///f[]可走步數(shù)///S[]后繼存在狀態(tài)for(j = 0;;j++) if(!S[j]){///找出后繼存在狀態(tài)中的最小非負整數(shù)；SG[i] = j;?///最終得出該點i的SG值break;}} } int main(){int n,m,k;f[0] = f[1] = 1;for(int i = 2; i <= 16; i++)///由題意得初始化可走步數(shù)（可取個數(shù)）f[i] = f[i-1] + f[i-2];getSG(1000);///得出所有點的SG函數(shù)值while(scanf("%d%d%d",&m,&n,&k),m||n||k){if(SG[n]^SG[m]^SG[k]) printf("Fibo\n");else printf("Nacci\n");}return 0; }

?

?

我的標簽：做個有情懷的程序員。

?

?

?

總結(jié)

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

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