威佐夫博奕
威佐夫博奕
威佐夫博奕（Wythoff Game）:有兩堆各若干個物品，兩個人輪流從某一堆或同
時從兩堆中取同樣多的物品，規定每次至少取一個，多者不限，最後取光者得勝。
這種情況下是頗為複雜的。我們\((a_k,b_k)\)（\(a_k\le b_k ,k=0，1，2，…,n)\)表示兩堆物品的數量並稱其為局勢，如果甲面對（0，0），那麼甲已經輸了，這種局勢我們稱為奇異局勢。前幾個奇異局勢是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
我們會發現他們的差值是遞增的，分別是0,1,2,3,4,5,6,7……n
可以看出\(a_0=b_0=0\)
對於奇異局勢\((a_k,b_k)\)，通過數學方法分析得到
\(a_k\)是未在前面出現過的最小自然數,而\(b_k=a_k+k\)
奇異局勢有以下三條性質：
- 1.任何自然數都包含在一個且僅有一個奇異局勢中
證法一：
反證法，假設存在一個自然數\(n\)存在於兩個奇異局勢中，分別設為\((a,n),(b,n)\)其中\((a<b)\)，
甲和乙進行博弈
假設甲拿到奇異局勢\((b,n)\)，根據定義甲是必輸的
那麼甲就可以取\((b-a)\)個物品，讓乙面對奇異局勢\((a,n)\),這樣就是乙必輸，甲必贏
原本甲先拿到奇異局勢，就是甲必輸，但最後得出甲必勝，乙必輸，
這樣原來的奇異局勢\((b,n)\)就是非奇異局勢，與原來的假設相互矛盾，
故不存在一個自然數\(n\)存在於兩個奇異局勢中，
即任何自然數都包含在一個且僅有一個奇異局勢中
證畢
證法二：
由於\(a_k\)是未在前面出現過的最小自然數，所以有\(ak > ak-1\) ，而 $$b_k= a_k + k> a_{k-1} + k-1 =b_{k-1}>a_{k-1}$$所以性質1成立
- 2.任意操作都可將奇異局勢變為非奇異局勢
證明：
與性質一的證明類似，若存在一種取法，使得甲面對奇異局勢，轉換為乙面對奇異局勢，那麼由原先的甲必輸轉換為乙必輸，矛盾
故不存在一種取法，使得奇異局勢轉換為奇異局勢
即任意操作都可以將奇異局勢變為非奇異局勢
證畢
- 3.採用適當的方法，可以將非奇異局勢變為奇異局勢。
這個很好理解，證明也很簡單分類討論就行，這裡就不加以贅述
威佐夫博奕的編程問題
威佐夫博奕主要有兩種問題
- 給定一個自然數，輸出對應的奇異局勢
- 給定一個局勢，判斷它是不是奇異局勢
問題一：打表實現，很簡單
問題二：
仔細觀察我們會發現，每種奇異局勢的第一個值(這裡假設第一堆數目小於第二堆的數目)
總是等於當前局勢的差值乘上1.618
我們都知道0.618是黃金分割率。而威佐夫博弈正好是1.618，這就是博弈的奇妙之處！
即 \(a_k=[(b_k-a_k)\times 1.618]\)（中括號代表向下取整）
C/C++中的double強制轉為int，就是向下取整,而並非是四捨五入
即a[k]=(int)((b[k]-a[k])*1.618));
當然這邊的1.618是近似值，編程題對精度eps要求極高
\(\displaystyle \frac{\sqrt{5} +1}{2} \approx 1.618\)
實際的值應該是約等號左邊的值
下面來看一下一道威佐夫博奕的題目，也是NOI的題目，hdu1527
題目鏈接
代碼實現
#include<cstdio>
#include<cmath>
using namespace std;
int main() {
int a, b,tmp;
double r, c;
r = (sqrt(5) + 1) / 2;//為精確值
while (~scanf("%d%d", &a, &b)) {
//a存小的值，b存大的值
if (a > b) {//若a>b則交換a和b
a ^= b;
b ^= a;
a ^= b;
}
c = (double)(b - a);
tmp = r * c;//double轉int，向下取整後的結果
printf("%d\n", tmp != a);
//關係表達式返回1或0
}
}
本文參照：//www.cnblogs.com/java20130726/archive/2013/05/24/3218207.html
//blog.csdn.net/qq_41311604/article/details/79980882
