本篇内容主要讲解“怎么理解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
#include
#include
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函数及性质”有了更深的了解，不妨来实际操作一番吧！这里是创新互联建站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
文章标题：怎么理解SG函数及性质-创新互联
网页URL：
http://cdkjz.cn/article/eooid.html
