Massive Algorithms: Leetcode: Extra: 主要是game theory

给两个数，每次你都可以用大的数减去小的的数字的正整数倍数（得数必须非负），然后交换玩家，首先得到0的人胜利，问是第一个人还是第二个

假设a，b，当a >= 2b时，当前的玩家获胜

证明：

当 a < 2b时，只有一种情况 (a, b) -> (a - b, b)。(a - b, b)时的获胜者必定会跟(a, b)时的获胜者不为一人（可以用反证法证明这个）

当 a >= 2b时, (a, b)可以转为(a - i * b, b), b < a - i * b < 2b, 所以可以(a, b)可以选择winning position，也可选择loosing position，所以此时(a, b)的玩家必胜

提醒：game theory题的定理：

All terminal positions are losing.
If a player is able to move to a losing position then he is in a winning position.
If a player is able to move only to the winning positions then he is in a losing position.

base case 为当a == b

int canWin(int a, int b, int player) {

    if (a == b) return player;

    if (a < b) return canWin(b,a,player);

    if (a >= 2 * b) return player;

    return canWin(a - b,b,(player + 1) % 2);

}

Labels