5024-除數(shù)博弈

eternalshallow 發(fā)布于2019-08-19 11:39 / 2296人閱讀

摘要：前言的除數(shù)博弈愛(ài)麗絲和鮑勃一起玩游戲，他們輪流行動(dòng)。只有在愛(ài)麗絲在游戲中取得勝利時(shí)才返回，否則返回。示例輸入輸出解釋愛(ài)麗絲選擇，鮑勃無(wú)法進(jìn)行操作。

前言

Weekly Contest 132的除數(shù)博弈：

愛(ài)麗絲和鮑勃一起玩游戲，他們輪流行動(dòng)。愛(ài)麗絲先手開(kāi)局。
最初，黑板上有一個(gè)數(shù)字 N 。在每個(gè)玩家的回合，玩家需要執(zhí)行以下操作：
選出任一 x，滿足 0 < x < N 且 N % x == 0 。
用 N - x 替換黑板上的數(shù)字 N 。
如果玩家無(wú)法執(zhí)行這些操作，就會(huì)輸?shù)粲螒颉?/p>
只有在愛(ài)麗絲在游戲中取得勝利時(shí)才返回 true，否則返回 false。假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲。
示例1：
輸入：2
輸出：true
解釋：愛(ài)麗絲選擇 1，鮑勃無(wú)法進(jìn)行操作。
示例2：
輸入：3
輸出：false
解釋：愛(ài)麗絲選擇 1，鮑勃也選擇 1，然后愛(ài)麗絲無(wú)法進(jìn)行操作。
提示：
1 <= N <= 1000

解題思路

本題難度為簡(jiǎn)單，可是題目的描述會(huì)感覺(jué)解題十分困難，實(shí)際上本題只需要找出愛(ài)麗絲和鮑勃勝負(fù)的周期即可，同類型的題目有292. Nim游戲。下面先列出前5次的勝負(fù)情況：

N為1時(shí)，由于愛(ài)麗絲先手，無(wú)法進(jìn)行操作，鮑勃勝利，為false

N為2時(shí)，愛(ài)麗絲勝利，為true

N為3時(shí)，鮑勃勝利，為false

N為4時(shí)，取數(shù)情況為1,1,1，愛(ài)麗絲勝利，為true

N為5時(shí)，取數(shù)情況為1,1,1,1，鮑勃勝利，為false

從上面列出的勝負(fù)情況可以看出，當(dāng)N為奇數(shù)時(shí)，鮑勃勝利，當(dāng)N為偶數(shù)時(shí)，愛(ài)麗絲勝利。

實(shí)現(xiàn)代碼

   /**
     * 5024. 除數(shù)博弈
     * 1    false
     * 2    1    true
     * 3    1    false
     * 4    1,1,1    true
     * 5    1,1,1,1   false
     * @param N
     * @return
     */
    public boolean divisorGame(int N) {
        return N%2==0;
    }