今天分享一道超簡單的博弈題，通過找規(guī)律的方式來發(fā)現(xiàn)其中的奧秘，最后只需要一行代碼解決。
題目描述
愛麗絲和鮑勃一起玩游戲，他們輪流行動。愛麗絲先手開局。
最初，黑板上有一個數(shù)字 N 。在每個玩家的回合，玩家需要執(zhí)行以下操作：
- 選出任一
x，滿足0 < x < N且N % x == 0。 - 用
N - x替換黑板上的數(shù)字N。
如果玩家無法執(zhí)行這些操作，就會輸?shù)粲螒颉?/p>
只有在愛麗絲在游戲中取得勝利時才返回 True，否則返回 false。假設(shè)兩個玩家都以最佳狀態(tài)參與游戲。
示例 1：
輸入：2
輸出：true
解釋：愛麗絲選擇 1，鮑勃無法進(jìn)行操作。
示例 2：
輸入：3
輸出：false
解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進(jìn)行操作。
提示：
1 <= N <= 1000
題目解析
對于這種博弈類的題目，如果沒有思路的話我們不妨多舉幾個例子，嘗試著從中找尋規(guī)律。
- 假設(shè)
N = 1，愛麗絲沒得選擇，直接失敗，即 鮑勃獲勝； - 假設(shè)
N = 2，愛麗絲有選擇，她可以選擇x = 1，鮑勃面對的就是N = 2 - 1 = 1，無法操作，愛麗絲獲勝； - 假設(shè)
N = 3，愛麗絲只能選擇x = 1，因為選x = 2不滿足3 % 2 = 0，鮑勃面對的就是N = 3 - 1 = 2，參考上面N = 2的情形，此時鮑勃為N = 2的先手，鮑勃獲勝； - 假設(shè)
N = 4，愛麗絲可以選擇x = 1來使鮑勃遇到N = 3的情況，愛麗絲獲勝；
貌似有個規(guī)律：N 為奇數(shù)時， 鮑勃獲勝；N 為偶數(shù)時， 愛麗絲獲勝。
是這樣嗎？
是的。
事實上，無論 N 為多大，最終都是在 N = 2 這個臨界點結(jié)束的。誰最后面對的是 N = 2 的情形，誰就能獲勝（這句話不太理解的話，仔細(xì)看看 N = 2、N = 3 這兩種情形）。
接下來，我們得知道一個數(shù)學(xué)小知識：奇數(shù)的因子（約數(shù)）只能是奇數(shù)，偶數(shù)的因子（約數(shù)）可以是奇數(shù)或偶數(shù)。
千萬不要忽略 1 也是因子！
愛麗絲是游戲開始時的先手。
- 當(dāng)她面對的 N 為偶數(shù)時，她 一定可以 選到一個 N 的奇數(shù)因子 x（比如 1 ），將 N - x 這個奇數(shù)傳給鮑勃；用
N - x替換黑板上的數(shù)字N，鮑勃面對的就是奇數(shù) N，只能選擇 N 的奇數(shù)因子 x，奇數(shù) - 奇數(shù) = 偶數(shù)，此時傳給愛麗絲的又是偶數(shù)。這樣輪換下去愛麗絲會遇到 N = 2 的情形，然后獲勝； - 當(dāng)愛麗絲遇到的 N 是奇數(shù)時，只能傳給鮑勃偶數(shù)或無法操作 (N = 1) ，無法獲勝。
代碼實現(xiàn)
class Solution {
public boolean divisorGame(int N) {
return N % 2 == 0;
}
}
