巴什博弈(Bash Game):只有一堆n个物品，两个人轮流取1物品，规定每次最少取一个，最多取m个，最后取完的人获胜。下面是从别的博客上看的：链接，经典巴什博奕的 解法
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果
n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
结论：
只要n%(m+1)!=0,先取者一定获胜。
但是，如果不是任意取1~m个而是给一个集合S={a1,a2,a3….an},只能取ai个，或者反一下两人轮流加1~m，加到大于等于n就算赢，或者乘到n，这些变形该怎么办？
分析此类问题主要方法是P/N分析：
P点：即必败点，某玩家位于此点，只要对方无失误，则必败；
N点：即必胜点，某玩家位于此点，只要自己无失误，则必胜。
三个定理：
一、所有终结点都是必败点P（上游戏中，轮到谁拿牌，还剩0张牌的时候，此人就输了，因为无牌可取）；
二、所有一步能走到必败点P的就是N点；
三、通过一步操作只能到N点的就是P点；
算法实现：
步骤1:将所有终结位置标记为必败点（P点）；（终结位置指的是不能将游戏进行下去的位置）
步骤2:将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；
步骤4:如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。
为了方便，我把用P/N分析法且是单数操作的全部归类为巴什博弈。（分类错了请见谅）
例题一
硬币游戏1
题目链接：挑战程序设计博弈篇上的
题目大意：x枚硬币，给定大小为k的集合S={a1,a2….ak}，Alice和Bob轮流取硬币，每次取的数目要为ai，取走最后一枚则获胜，谁会赢？
解题思路：利用P/N分析，设j为剩余硬币数，j=0为必败态。那么有以下两个规则：
①对于某个i,j-ai为必败态，那么j就是必胜态（N）。
②对于任意i,j-ai都是必胜态，j就是必败态（P）。
根据这些规则，我们只要按照j从小到大的顺序递推确定各点是必胜态还是必败态态，最后只要看x点是必胜还是必败就能知道谁获胜了。
代码：
1 #include<cstdio> 2 const int N=1e4+5; 3 int a[105]; 4 bool win[N]; 5 6 int main(){ 7 int x,k; 8 while(scanf("%d%d",&x,&k)){ 9 for(int i=1;i<=k;i++){ 10 scanf("%d",&a[i]); 11 } 12 win[0]=false;//j=0是必败态 13 14 for(int j=1;j<=x;j++){ 15 bool flag=false; 16 for(int i=1;i<=k;i++){ 17 //如果某个i令j-a[i]是必败态，则j为必胜态 18 if(a[i]<=j&&!win[j-a[i]]){ 19 flag=true; 20 break; 21 } 22 } 23 win[j]=flag; 24 } 25 if(win[x]) puts("Alice"); 26 else puts("Bob"); 27 } 28 }
例题二
HDU 2149 Public Sale
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2149
题目大意：初始价格为0，两个人轮流加价，加价范围是1~N，谁先把价格加到大于等于M谁就获胜。现在的要求是第一个人加价多少可以获得胜利，如果不能就输出“none”。
解题思路：用P/N分析发现了规律，只要通过加价t可以使得(M-t)%(N+1)那先手就会获胜，反之如果找不到t也就是t=0，那么就是“none”。
代码：
1 #include<cstdio> 2 int main(){ 3 int m,n; 4 while(~scanf("%d%d",&m,&n)){ 5 bool flag=false; 6 if(m%(n+1)==0) 7 printf("none"); 8 else{ 9 printf("%d",m%(n+1)); 10 //n>m的情况 11 for(int i=m+1;i<=n;i++) 12 printf(" %d",i); 13 } 14 printf("\n"); 15 } 16 return 0; 17 }
例题三
HDU 1517 A Multiplication Game
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1517
题目大意：两个人玩游戏，轮流操作，给你一个数字n以及p=1，每次可以从2~9中任选一个数字，并把它与p相乘，谁能先使得p>=n，谁就是胜者。
看了大牛的解法终于对P/N分析有了一点理解：
根据P/N分析的方法，先将终结位置[n,无穷]标记为P点。
然后找所有能到达P点的点[n/9,n-1]标记为N点。
接着找到只能进入N点的点[n/9/2,n/9-1]标记为P点。
循环以上两次操作，判断出1这个点是否为必胜点。
代码：
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef long long LL; 5 6 int main(){ 7 LL n; 8 while(~scanf("%lld",&n)){ 9 int x=0; 10 while(n>1){ 11 x++; 12 if(x&1) 13 n=ceil((double)n/9); 14 else 15 n=ceil((double)n/2); 16 } 17 if(x&1) 18 printf("Stan wins.\n"); 19 else 20 printf("Ollie wins.\n"); 21 } 22 } 23
今天的文章巴什博弈_足球凯利指数数据app分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/47541.html
