Saturday, September 5, 2015

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);
}


No comments:

Post a Comment