取石子游戏-题解（C语言代码）

解题思路:

威佐夫博弈（Wythoff's game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

我们用(a[k]，b[k])    (a[k] ≤ b[k] ,k=0，1，2，......n)来表示两堆物品的数量，并且称这个为局势。

首先我们来从最简单的情况开始分析：

如果现在的局势是(0，0)，很明显此时已经没有办法再取了，所以肯定是之前的人在上一局中取完了。

假设现在的局势是(1，2)，那么先手只有四种取法。

（1） 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。

（2）如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。

（3）如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。

（4）如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。

  由此可得，先手必输。

是不是觉得这个后手好厉害，无论先手怎么取，后手都会胜利。

在学习威佐夫博弈之前，我也是这样认为的。不过，当你继续看完这篇博客，你也会轻松获得胜利。

为了让大家更好地理解威佐夫博弈，我们继续来进行具体分析。

假设现在的局势是（3，5），首先根据上面分析的经验，我们知道先手肯定不能把任意一堆物品取完，这是因为每次可以从任意一堆取走任意个物品，那么后手就可以直接把另一堆取完，所以后手获胜。

所以我们这里就不分析那些情况，来分析其他的情况。

先看在一堆中取的情况：

（1） 假设先手在“3”中取1个，后手就可以在“5”中取走4个，这样就变成了（1，2）的局势，根据上面的分析，我们知道是先手输，后手获胜。

（2） 假设先手在“3”中取2个，后手就可以在 “5” 中取走3个，这样也变成了（1,2）的局势了，还是先手输，后手获胜。

（3）假设先手在“5”中取1个，后手就在 “3”和“5” 中各取走2个，这样又成了（1，2）的局势了，先手输，后手赢。

（4）假设先手在“5”中取2个，后手就在 “3”和“5” 中各取走3个，这样变成了（0，0）的局势，先手输，后手赢。

（5）假设先手在“5”中取3个，后手就在 “3”和“5” 中各取走1个，也变成了（1，2）的局势，先手输，后手胜利。

（6）假设先手在“5”中取4个，后手在“3”中取走1个，还是（1，2）的局势，先手输，后手赢。

我们发现上面列举的这几种局势，无论先手怎么取都是后手赢

第一种（0，0）

第二种（1，2）

第三种（3，5）

第四种  (4 ，7）

第五种  (8，13）

第六种  (9 ， 15）

第七种  (11 ，18）

第n种  （a[k]，b[k]）

我们把这些局势称为“奇异局势”

再找规律的话我们会发现，第一个值 = 差值 * 1.618 

而1.618 = （sqrt（5）+ 1） /  2 。

注意事项:  奇异先手输，非奇异先手胜

参考代码:

#include<stdio.h>

#include<math.h>

int main(){

int n,m,a,b,temp;

double c,r;

while(scanf("%d%d",&n,&m)!=EOF){

if(n>=m){

a=m;

b=n;

}else{

a=n;

b=m;

}

r=(sqrt(5.0)+1)/2;

c=(double)(b-a);

temp=(int)(r*c);

if(temp==a)printf("0\n");

else printf("1\n");

}

}