给两个数,每次你都可以用大的数减去小的的数字的正整数倍数(得数必须非负),然后交换玩家,首先得到0的人胜利,问是第一个人还是第二个
假设a,b,当a >= 2b时,当前的玩家获胜
假设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.
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