愛奇藝2017校招-Java開發-線上算法筆試題-NIM博弈問題，牛牛羊羊吃草

題目為：

牛牛和羊羊吃草，有t捆，每捆n個，兩個人玩一個遊戲，規則為，每個人每次隻能吃4的幂，即1個，4個，或者16個。。。，直到無草可吃為輸，每個人均會按照最佳政策進行。

輸入t為堆數，之後輸入每堆的個數；

如果牛牛赢，輸出niu

如果羊羊赢，輸出yang

5
1
2
3
4
5
niu
yang
niu
niu
yang
           

典型的NIM問題，博弈問題，對應每個石子數n可以分為兩種狀态：

N:先手赢

P:後手赢

• (n)代表此刻的石子數量，因為每次可以拿1,4,16，...對應的子狀況為(n-1),(n-4),(n-16)
• (0)時，自己沒有石子可拿，一定對手赢，狀态為P
• (1)時，自己全拿走一定赢，先手赢，狀态N
• (2)時，自己拿一個，對手拿走一個，自己肯定輸，(2)對應子狀态(1)為N,是以（2）為P
• (3)時，對應子狀态為(2)狀态為P,是以(3)為N
• (4)時，對應子狀态為(0)-》P,(3)-》N，考慮到每個人會選擇最佳政策，為了赢選擇P(0)，此時變為N
• (5)時，可以選擇拿1個，對應(4)為N 拿4個，對應(1)為N,都是先手赢，是以(5)為P,是後手赢
• (6)時，可以選擇拿1個，對應(5)為P, 拿4個，對應(2)為P,都是後手赢，是以(6)為N,是先手赢
• ….
• 以此類推，(17)時，子狀态(1) (13) (16)..

N先手赢為1，P後手赢為0,目前石子為n時狀态為NIM(n),則狀态轉移方程為

NIM(n-1) NIM(n-4) NIM(n-16) NIM()… NIM(n)

1 1 1 1 0

0 0 0 0 1

0 0 0 1 1

0 0 1 1 1

核心是

隻要子狀态包含P後手赢，那麼為了赢，一定會選擇這個狀态為P的子狀态，讓自己赢

如果子狀态都是N先手赢，那麼無論怎麼做，輪到下一個都必赢，自己一定會輸。

import java.util.Scanner;

/**
 * Created by Luna on 2017/10/14.
 */
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int loop = input.nextInt();
        int c=0;
        int[] num = new int[loop];
        while (c<loop){
            num[c]=input.nextInt();
            c++;
        }
        for (int i = 0; i < loop; i++) {
            System.out.println(NIM(num[i])?"niu":"yang");
        }


    }
    public static boolean NIM(int k) {
        if (k==0)
            return false;
        if (k==1)
            return true;
        int tmp=1;
        int count=-1;
        while(tmp<=k){   //判斷輸入值包含4的k次幂，對應有k+1個子狀況 
            if(tmp==k)
                return true;
            tmp<<=2;
            count++;
        }
        for (int i = 0; i <=count ; i++) {
            int next=k - (int)Math.pow(4, i);
            if(!NIM(next)) return true;   //隻要包含false  那麼就選擇它，讓自己赢
        }
        return false;//如果子狀況都是先手赢，那麼自己必輸。
    }
}
           

運作結果：

5
1
2
3
4
5
niu
yang
niu
niu
yang
           

5
16
19
31
42
76
niu
niu
niu
yang
niu