189 8069 5689
本篇内容主要讲解“怎么理解SG函数及性质”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“怎么理解SG函数及性质”吧!
创新互联公司是专业的霍尔果斯网站建设公司，霍尔果斯接单;提供做网站、成都网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行霍尔果斯网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
{
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函数及性质”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！