怎么理解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#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函数及性质-创新互联
网页地址:http://myzitong.com/article/eooid.html