题目描述： 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，
一是可以在任意的一堆中取走任意多的石子；
二是可以在两堆中同时取走相同数量的石子。
最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你是胜者，输出Win,否则输出Loose。例如，a=3,b=1, 则输出Win(你先在a中取一个，此时a=2，b=1,此时无论对方怎么取，你都能将所有石子都拿走).
示例：
输入：a = 2 b = 1
输出： Loose
分析: 这种情况下是颇为复杂的。我们 \((ak,bk)(ak≤bk,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
这几个奇异局势是如何推导出来的呢？
这个是自己手动推导出来的，一定要注意，有两种取法，我自己第一次思考的时候，只考虑了第一种，结果就导致，我推导出来了一大推错误的 奇异局势，所以最后就错了。
可以看出a0=b0=0 对于奇异局势(ak,bk)，通过数学方法分析得到 ak是未在前面出现过的最小自然数,而bk=ak+k
奇异局势有以下三条性质：
- 1.任何自然数都包含在一个且仅有一个奇异局势中
证法一： 反证法，假设存在一个自然数n存在于两个奇异局势中，分别设为(a,n),(b,n)其中(a < b), 甲和乙进行博弈 假设甲拿到奇异局势(b,n)，根据定义甲是必输的 那么甲就可以取(b−a)个物品，让乙面对奇异局势(a,n),这样就是乙必输，甲必赢 原本甲先拿到奇异局势，就是甲必输，但最后得出甲必胜，乙必输， 这样原来的奇异局势(b,n)就是非奇异局势，与原来的假设相互矛盾， 故不存在一个自然数n存在于两个奇异局势中， 即任何自然数都包含在一个且仅有一个奇异局势中 证毕
证法二： 由于ak是未在前面出现过的最小自然数，所以有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}) * 1.618] (中括号表示向下取整)\) 当然这里的 1.618 只是一个近似值，在编程的时候，我们需要更高的精度，于是乎就有了下面的公式： \((\sqrt(5)+1) / 2 \approx 1.618\) 这里就有一个比较致命的问题了，这个 1.618 是怎么被算出来的，我只能说，记一下吧，当作公式来背。我是直接记忆的，然后又忘记了。 （ps: 我感觉我得了健忘症）
代码:
1
2
3
4
5
6
7
import math
if a > b:
a, b = b, a
k = b - a
temp = int(k * (1+math.sqrt(5)) / 2);
# print(temp)
print("Loose" if temp == a else "Win")