博弈模板

 1 ///博弈模板
 2 一）巴什博弈（Bash Game）：
 3 问题描述:
 4 只有一堆n个物品，两个人轮流从这
 5 堆物品中取物，规定每次至少取一
 6 个，最多取m个。最后取光者得胜
 7 问题解答:
 8 很容易想到当n%(m+1)<>0时，先取必胜，
 9 第一次先拿走n%(m+1)，以后每个回合到
10 保持两人拿走的物品总和为m+1即可
11 
12 二）威佐夫博弈（Wythoff Game）：
13 问题描述:
14 有两堆各若干个物品，两个人轮流从某
15 一堆或同时从两堆中取同样多的物品，
16 规定每次至少取一个，多者不限，最
17 后取光者得胜。
18 问题解答：
19 奇异局势：第一个人必输的局
20 那么任给一个局势（a，b），怎
21 样判断它是不是奇异局势呢？我
22 们有如下公式：
23 ak =[k（1+√5）/2]，
24 bk= ak + k  。
25 主要代码：
26 const double p=(1+sqrt(5.0))/2;
27 if (a>b) swap(a,b);
28 int k=b-a;
29 if (a==(int)(p*k))
30 {
31     printf("2
");
32 }
33 else printf("1
");
34 
35 三）Nim游戏  ：
36 问题描述:
37 有三堆各若干个物品，两个人轮流
38 从某一堆取任意多的物品，规定每
39 次至少取一个，多者不限，最后取
40 光者得胜
41 问题解答:
42 奇异局势:a[0]^a[1].....^a[n-1]=0.