数学基础（四）博弈论(巴什博弈~威佐夫博弈（黄金分割率）~尼姆博奕~斐波那契博弈~SG函数模板)_巴什博奕为什么最少拿1件

一、巴什博弈

1、问题模型
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。

2、解决思路：
当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-x个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

结论：当（n-1）%（m+1）==0时后手胜利。

二、威佐夫博奕（黄金分割率）

1. 问题模型
有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
2. 解决思路
我们用(a[k]，b[k]) (a[k] ≤ b[k] ,k=0，1，2，…n)来表示两堆物品的数量，并且称这个为局势。

首先我们来从最简单的情况开始分析：

如果现在的局势是(0，0)，很明显此时已经没有办法再取了，所以肯定是之前的人在上一局中取完了。

假设现在的局势是(1，2)，那么先手只有四种取法。

（1） 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。

（2）如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。

（3）如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。

（4）如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。

由此可得，先手必输。
结论
若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w==x，则先手必败，否则先手必胜。
课外 黄金分割率（1.618 = (sqrt(5.0) + 1) / 2）

三. 尼姆博弈

1. 问题模型
有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
结论
把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。

变形：
有 n 堆石子，将这 n 堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[1005];
int main()
{
	cin>>n;
	while(n--){
		cin>>m;
		for(int i=1;i<=m;i++){
			cin>>a[i];
		}
		if(abs(a[1]-a[m])<2) cout<<"0"<<endl;
		else cout<<"1"<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四. 斐波那契博弈：

1. 问题模型
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

结论
先手胜当且仅当n不是斐波那契数（n为物品总数）

SG函数

1. 问题
题目描述一般为

A ，B 2人做游戏。A B交替进行某种游戏规定的操作，每操作一次，选手可以在有限的操作（操作必须合法）集合中任选一种。对于游戏的任何一种可能的局面，合法的操作集合只取决于这个局面本身，不取决于其它因素（跟选手，以前的所有操作无关）如果当前选手无法进行合法的操作，则为负。

/*
f[N]为事先的合法操作集合。 
sg[N]为需要打表的数据；sg[0]始终为0，可以从1开始。 
s[N] 为 x 的后续状态集合 
*/
int n,m,f[N],s[N],sg[N];
void SG() {
	memset(sg,-1,sizeof(sg));
	sg[0]=0;
	for(int i=1; i<=N; i++) {
		memset(s,0,sizeof(s));//每一次都需要将上一个状态的后续集合重置 
		for(int j=1; f[j]<=i&&j<=n; j++) {
			s[sg[i-f[j]]]=1;// //将后继状态的SG函数值进行标记
		}
		for(int j=0;; j++) {// //查询当前后继状态SG值中最小的非零值
			if(!s[j]) {
				sg[i]=j;
				break;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22