sg函数的理解
2024-08-27 20:19:22
sg，是用来判断博弈问题的输赢的，当sg值为0的时候，就是输，不为0就是赢；
在这之前，我们规定一个对于集合的操作mex，表示最小的不属于该集合的非负整数。 举几个栗子：mex{0,1,2}=3，mex{1,2,3}=0，mex{0,1,3}=2；
而我们要求的sg的值就和这个有关，定义SG函数：SG(x)=mex{ SG(y) | y是x的后继，也就是经过操作可以取得的剩下值 }。
举个栗子：比如一堆石子，我们可以取任意个，那么x个石子的石子的sg值是多少呢？
可以知道，0个石子sg为0，一的时候我们可以取一个，剩下0，的sg是0，那么mex（0）就是1，所以1的sg为1。
递推下去当为x的时候我们可以取1~x个，那么剩下的值石子个数就是x-1到0个，他的mex（...）就是x，所以这个例子的x值得sg值就是x；
那么，sg可以为我们做什么呢？比如Nimm问题，多堆的时候，我们只需要将每个sg值亦或一下，如果是0就会输，不是就赢，也就是将每堆的数量亦或就可以了
最新文章
- C# Iterator迭代器的实现方式
- c语言语系的命名风格和java系命名风格
- ThikPHP3.1 常用方法（one）
- Stanford机器学习---第六讲. 怎样选择机器学习方法、系统
- ACM第四站————最小生成树（克鲁斯卡尔算法）
- applet授权数字签名
- SQL Mon 介绍
- java运行时数据区域
- PHPCMS v9 列表页实现文件下砸
- JavaScript 基础学习1-day14
- nginx学习笔记(三)
- Json常用组件
- 嵌入式小系统I2S接口调试总结
- windows系统安装完后要做的事情
- Javascript合并表格相同内容单元格示例
- POJ 2387 Til the Cows Come Home 【最短路SPFA】
- WOSA/XFS PTR Form解析库—xfsptrdata.h
- HDFS 命令深入浅出
- 一.shell基础知识
- ORM--------Hibernate、Mybatis与Spring Data的区别