怎么理解SG函數及性質

本篇內容主要講解“怎么理解SG函數及性質”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么理解SG函數及性質”吧!

{

Sprague-Grundy函數性質

所有的終結點SG值為0（因為它的后繼集合是空集）
SG為0的頂點，它的所有后繼點都滿足SG不為0
對于一個SG不為0的頂點，必定存在一個后繼滿足SG為0

滿足組合游戲性質
所有SG為0定點對應P點，SG大于0頂點對應N點

}

hdu1847 Good Luck in CET-4 Everybody! 

題意：

總共n張牌，雙方輪流抓牌，每人每次抓牌的個數只能是2的冪次（即：1，2，4，8，16…），抓完牌，勝負結果也出來了：最后抓完牌的人為勝者。給出n，問先手贏還是后手贏？

PS：當然這題可以直接推出 n%3==0必敗，否則必勝。 //巴什博奕

下面介紹另外一種做法 

SG值：一個點的SG值就是一個不等于它的后繼點的SG的且大于等于零的最小整數。//同mex()函數

簡單點來講就是當前狀態離最近一個必敗點的距離。

SG(x)=mex（S）
S是x的后繼狀態的SG函數值集合

mex(S)表示不在S內的最小非負整數

我們枚舉下牌數為0-10的SG值：
num： 0 1 2 3 4 5 6 7 8 9 10
sg值：0 1 2 0 1 2 0 1 2 0 1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;


const int maxn = 1000 + 10;
int arr[11], sg[maxn];


void pre() { //把1000以內的所有的可能一次拿的牌都算出來！ 
    arr[0] = 1;
    for(int i=1; i<=10; ++i) arr[i] = arr[i-1]*2;
}


int mex(int x) { //這是求解該點的sg值的算法函數(采用記憶化搜索) 
    if(sg[x]!=-1) return sg[x];
    bool vis[maxn];
    memset(vis, false, sizeof vis );
    for(int i=0; i<10; ++i) {
        int temp = x - arr[i];
        if(temp<0) break;
        sg[temp] = mex(temp);
        vis[sg[temp]] = true;
    }


    for(int i=0; ; ++i) {
        if(!vis[i]) {
            sg[x] = i;
            break;
        }
    }
    return sg[x];
}
int main() {
    int n;
    pre();
    while(scanf("%d", &n)!=EOF) {
        memset(sg, -1, sizeof sg );
        if(mex(n)) printf("Kiki\n");
        else printf("Cici\n");
    }
    return 0;
}

到此，相信大家對“怎么理解SG函數及性質”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！