99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

本篇內(nèi)容主要講解“怎么理解SG函數(shù)及性質(zhì)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么理解SG函數(shù)及性質(zhì)”吧!

專(zhuān)注于為中小企業(yè)提供成都做網(wǎng)站、網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)小店免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千多家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

{

Sprague-Grundy函數(shù)性質(zhì)

所有的終結(jié)點(diǎn)SG值為0（因?yàn)樗暮罄^集合是空集）
SG為0的頂點(diǎn)，它的所有后繼點(diǎn)都滿(mǎn)足SG不為0
對(duì)于一個(gè)SG不為0的頂點(diǎn)，必定存在一個(gè)后繼滿(mǎn)足SG為0

滿(mǎn)足組合游戲性質(zhì)
所有SG為0定點(diǎn)對(duì)應(yīng)P點(diǎn)，SG大于0頂點(diǎn)對(duì)應(yīng)N點(diǎn)

}

hdu1847 Good Luck in CET-4 Everybody!

題意：

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

PS：當(dāng)然這題可以直接推出 n%3==0必?cái)。駝t必勝。 //巴什博奕

下面介紹另外一種做法

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

簡(jiǎn)單點(diǎn)來(lái)講就是當(dāng)前狀態(tài)離最近一個(gè)必?cái)↑c(diǎn)的距離。

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

mex(S)表示不在S內(nèi)的最小非負(fù)整數(shù)

我們枚舉下牌數(shù)為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
#include
#include
using namespace std;


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


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


int mex(int x) { //這是求解該點(diǎn)的sg值的算法函數(shù)(采用記憶化搜索) 
    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;
}

到此，相信大家對(duì)“怎么理解SG函數(shù)及性質(zhì)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)建站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)站題目：怎么理解SG函數(shù)及性質(zhì)-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.ef60e0e.cn/article/eooid.html