292. Nim 游戲
你和你的朋友，兩個人一起玩 Nim 游戲：
桌子上有一堆石頭，
你們輪流進行自己的回合，你作為先手，
每一回合，輪到的人拿掉 1 - 3 塊石頭，
拿掉最后一塊石頭的人就是獲勝者，
假設你們每一步都是最優解，請撰寫一個函式，來判斷你是否可以在給定石頭數量為 n 的情況下贏得游戲，如果可以贏，回傳 true；否則，回傳 false ，
示例 1：
輸入：n = 4
輸出：false
解釋：如果堆中有 4 塊石頭，那么你永遠不會贏得比賽；
因為無論你拿走 1 塊、2 塊 還是 3 塊石頭，最后一塊石頭總是會被你的朋友拿走，
示例 2：
輸入：n = 1
輸出：true
示例 3：
輸入：n = 2
輸出：true
提示：
1 <= n <= 231 - 1
開始沒有想太多，一看就想到動態規劃問題
即對于先手來說，即如果在他的回合只剩下0個石頭時他是必敗的，如果剩下1~3個石頭他是必勝的，
所以當有n個石頭時，如果先手對應n個石頭，后手則對應n-1或n-2或n-3個石頭，則要求先手對應n個石頭能不能必贏時，我們需要滿足后手的n-1，n-2,n-3三個方案中有一個必輸的方案即可，因為對手是十分聰明的，如果不能在三個中找到使得后手必輸的方案，我們就一定會輸，而由于我們也是十分聰明的，所以我們也只需要在三個方案中找到一個使得后手必輸的就行了，因為后手的三個方案到底是哪一個都是由我們先手的決定的，
所以不妨設a[n]為表示n個石頭時，先手的輸贏情況，
所以可列出a[n]=！(a[n-1]==1&&a[n-2]==1&&a[n-3]==1)
因為此時已經為n個石頭了，所以式子后面的a[n-1]==1&&a[n-2]==1&&a[n-3]==1則為下一個狀態了，即因為后手在先手先操作，操作后，他自己也就變成了先手，所以此時可以用來表示后手的輸贏情況了，
也可以這樣理解：
在n個石頭變成n-1或n-2或n-3時已經代表先手拿過了，則此時后手就相當于為n-1或n-2或n-3個石頭的先手了，
但是這樣會超時：
bool canWinNim(int n){
bool a[n];
if(n==1||n==2||n==3)
return 1;
a[0]=1;
a[1]=1;
a[2]=1;
for(int i=3;i<n;i++)
{
if(a[i-1]==1&&a[i-2]==1&&a[i-3]==1)
a[i]=0;
else
a[i]=1;
}
return a[n-1];
}
查看題解后發現可直接數學化思考：
即當1，2，3個石頭時先手都必贏，4個則必輸，當有5 個石頭時，我們發現若開始先手拿1個，則后手也必輸，所以可以知道即當誰的回合對應4個石頭時誰就必輸，因為大家都是聰明人，不論他這回合拿多少，下一個人總是能拿完剩下的所有石頭，
而當我們知道這個“逢四必輸”后，我們可以再看看8個石頭，我們發現當先手拿1~3個石頭后，后手總是有一種方案來使得最后給我們的還是4個石頭，所以我們還是必輸，所以我們知道了“逢八必輸”，當12個石頭時同理我們先手也會碰到8個石頭的情況…所以我們可知一旦石頭為4的倍數我們總是會由于后手的“聰明操作”而導致面臨4的倍數的石頭的情況，所以可知代碼：
bool canWinNim(int n){
return n%4!=0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240464.html
標籤：其他
上一篇：攻防世界game_逆向之旅001
下一篇：游戲地圖背景移動C++