= =拖延癥真的沒辦法…本來打算周更的也變成了半月更…

順利刷了20%了…可喜可賀可喜可賀…_(:з」∠)_

292. Nim游戲 （Nim Game）

• 題目：你和你的朋友，兩個(gè)人一起玩 Nim游戲：桌子上有一堆石頭，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者。你作為先手。
  你們是聰明人，每一步都是最優(yōu)解。 編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲。

• 思路：
  其實(shí)本問題算是較為基礎(chǔ)的尼姆博弈問題。由于了解不深…介紹一下我所知道的基礎(chǔ)概念吧…
  （1）關(guān)于“必勝狀態(tài)”與“必?cái)顟B(tài)”
  ??一個(gè)狀態(tài)是 必?cái)顟B(tài) 當(dāng)且僅當(dāng) 它的所有后繼都是必勝狀態(tài)。
  ??一個(gè)狀態(tài)是 必勝狀態(tài) 當(dāng)且僅當(dāng) 它至少有一個(gè)后繼是必?cái)顟B(tài)。
  （2）SG定理
  ??【目前還在看書研究…是的我又five了】
  （3）SG函數(shù) 通用解法
  ??首先介紹集合$S$的$mex()$函數(shù)：$$mex(S)=不在S集合中的最小非負(fù)整數(shù)$$??例如
  S1={1,2,3,4},mex(S1)=0?;S2={0,1,3,4},mex(S2)=2?;S3={}.mex(S3)=0S_1=\{1,2,3,4\} ,mex(S_1)=0\ ; \\ S_2=\{0,1,3,4\},mex(S_2)=2 \ ; \\ S_3=\{\}.mex(S_3)=0S1?={1,2,3,4},mex(S1?)=0?;S2?={0,1,3,4},mex(S2?)=2?;S3?={}.mex(S3?)=0
  ??對于SG函數(shù)有：
  $$SG(x)=mex(S)，其中S為x所有后繼狀態(tài)的集合$$
  ??另有：
  $$SG(x)=0?x為必敗狀態(tài)$$

（當(dāng)然對于這個(gè)題，為了刷排名…可以找到判別式…因?yàn)檫@個(gè)題簡單…其他尼姆博奕題目還是需要利用SG函數(shù)的解法【嘿嘿沒想到吧.jpg】8說了，摸魚摸魚）

class Solution {public boolean canWinNim(int n) {return n%4!=0;} }

[另一道利用SG函數(shù)解尼姆博弈的問題下次補(bǔ)充…]

轉(zhuǎn)載于:https://www.cnblogs.com/MTwz-NINE/p/10073847.html

總結(jié)

以上是生活随笔為你收集整理的【LeetCode刷题记】鹅厂秋招题集（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。