博弈论入门 Bash 、Nim 、Wythoff's Gam…

2019-01-23 07:39:21来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

SG函数先不说,给自己总结下三大博弈。和二进制及黄金分割联系密切,数学真奇妙,如果不用考试就更好了。

1.Bash Game:n个物品,最少取1个,最多取m个,先取完者胜。

给对手留下(m+1)的倍数肯定获胜。若n%(m+1)==0,先手必败。

51nod裸题:1066

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int main(){
 5     int t; cin>>t;
 6     int n,k;
 7     while(t--){
 8         cin>>n>>k;
 9         if(n%(k+1)==0)  puts("B");
10         else  puts("A");
11     }
12     return 0;
13 }

 

 

2.Nim Game:n堆物品,取某一堆的若干个,至少取一个,多者不限,先取完者胜。

在这个博弈中,对任何奇异局势 (a,b,c....n),都有a^b^...^n==0。

所以直接检测给的局势,若是奇异局,先手必败。

如何将(a,b,c)转化成奇异局:将c变为a^b,即c -= a^b(^是异或)

51nod裸题:1069

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int main(){
 5     int a[1005]={0};
 6     int ans=0;
 7     int n; cin>>n;
 8     for(int i=0;i<n;i++){
 9         cin>>a[i];
10         ans^=a[i];
11     }
12     if(ans)  puts("A");
13     else  puts("B");
14     return 0;
15 }

 

 

3.Wythoff's Game:两堆若干个,轮流从某一堆取任意个或同时从两堆取同样多任意个,最少一个,多者不限。先取完者胜。

局势:(ak,bk) 

前几个奇异局:(0,0)  (1,2)  (3,5)  (4,7)  (6,10)  (8,13)  (9,15)  (11,18)  (12,20)……

1.发现差值递增,且局面中第一个值为前面局面中没有出现过的数字的第一个数,且所有自然数都会出现。

2.再找规律:第一个值=(int) (差值*1.618) 而1.618 = ( sqrt(5)+1 )/2

3.所以,只要ak == (int) (bk - ak) * ( sqrt(5) + 1 ) / 2 先手必输,否则先手必胜

51nod裸题:1072

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 double c=(sqrt(5)+1)/2;
 6 int main(){
 7     int t; cin>>t;
 8     int ak,bk;
 9     while(t--){
10         cin>>ak>>bk;
11         if(ak>bk) swap(ak,bk);
12         int n=(bk-ak)*c;
13         if(ak==n)  puts("B");
14         else  puts("A");
15     }
16     return 0;
17 }

 


原文链接:https://www.cnblogs.com/noobimp/p/10306311.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:GetPixelAddress()函数Alpha通道会丢失

下一篇:简单的素数问题(C++)