Wythoff博弈

说明

有两堆石子，石子数目分别为n和m,现在两个人轮流从两堆石子中拿石子，每次拿时可以从一堆石子中拿走若干个，也可以从两中拿走相同数量的石子，拿走最后一刻石子的人赢。

结论：如果当前局势未奇异局势则先手必败，否则先手必胜。奇异局势的判断公式为：ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...n 方括号表示取整函数)

可以发现，前面几组奇异局势为（a，b） ：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）

这其中第k组的a为前面没有出现过的最小非负整数，而b = a + k

两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。 那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式： ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...n 方括号表示取整函数)

使用方法

int ans = wzf(n, m); n和m分别为两堆石子的个数，如果是奇异局势（必败态）则返回0，否则返回1

模版

int wzf(int n, int m)
{
    if(n > m)
        swap(n, m);
    int k = m-n;
    int a = (k * (1.0 + sqrt(5.0))/2.0);
    if(a == n)
        return 0;
    else
        return 1;
}

例题

题目

同样是取石头问题，不过如果先手能赢，要输出第一次取石子后所剩的情况。（如果在任意的一堆中取走石子能胜同时在两堆中同时取走相同数量的石子也能胜，先输出取走相同数量的石子的情况） 这道题目要输出威佐夫博弈从非奇异局势到奇异局势的转变方案。比直接判断复杂了很多。

思路

1. 先判断能否从两堆中取出相同的石头，达到目的。
2. 判断从一堆中取出石头，这里其实可以分为三种。假设一开始的时候为（a，b）。第一种是从b当中取走少量的，变为（a，b - k）。第二种是从b中取走大量的，变为（b - t， a）。第三种是从a当中取走一些，变为（a - t，b）

代码

int main () {
    int a, b;
    while(scanf("%d%d", &a, &b)) {
        if (a == 0 && b == 0) break;
        int k = b - a;
        int n = (1 + sqrt(5.0)) / 2 * k;
        if (a == n) puts("0");
        else {
            puts("1");
            if (a - n == b - n - k) printf("%d %d\n", n, n + k);    //两者之间的差值不变
            if (a == 0) puts("0 0");    //如果a等于0了，差值只能为0，即为（0，0）。
            for (int i = 1; i <= b; i++) { //枚举a和b之间的差值，可能从1一直到b - 1
                n = (1 + sqrt(5.0)) / 2 * i;
                int tmp = n + i;
                if (n == a) printf("%d %d\n", n, tmp);
                if (tmp == a) printf("%d %d\n", n, tmp);
                if (tmp == b) printf("%d %d\n", n, b);
            }
        }
    }
    return 0;
}