各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

威佐夫博弈(Wythoff Game)

April 15, 2018 • Read: 340 • 算法

简述

有两堆若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者胜

题解

我们用($a_k,b_k$)表示两堆物品的数量并称其为局势,如果甲面对 (0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8.13)、(9,15)、(11,18)、(12,20)。可以看出: $a_0=b_0=0$, $a_k$是未在前面出现过的最小自然数, 而$b_k=a_k+k$

必胜态必败态

满足$a_k=\frac{k*1 + \sqrt{5}} {2}$

$b_k=a_k+k$,先手必败,否则先手必胜(详细证明过程可以看这篇文章)。再抽象一点就是:有两堆物品的初始值为(x,y),且$x<y$$令z=y-x$,记$w=(int)[z*(frac{sqrt{5}+1}{2})]$,若$w=x$,则先手必败,否则先手必胜

题目链接:HDU1527 取石子游戏

题解

威佐夫博弈模板

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        int bb = min(a,b);
        int k = abs(a - b);
        int temp=(k * (1 + sqrt(5)) / 2);
        if(bb == temp)
            printf("0\n");
        else
            printf("1\n");
    }
    return 0;
}
Archives Tip
QR Code for this page
Tipping QR Code