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 }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605456.html