博弈論入門 Bash 、Nim 、Wythoff's Game結論及c++代碼實現

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 }