未分類

Nim Game

Brainteaser, Go, LeetCode

Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example: 

1
If there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
提示 解題應用
Brainteaser 規律觀查

Default:

1
2
3
func canWinNim(n int) bool {
}

解答思路:

一開始本來想用遞回的方式將石頭分別-1,-2,-3順勢找出全部會贏的狀況，但這種情況包含了對方是亂玩的情況，所以結果就是都會贏根本猜不出結果，這種遊戲如果換個角度來想，當雙方能力皆為相等的狀況下，而且是相當優秀的兩人，那麼整個過程就會只有一種，而且誰先誰後就是最大的關鍵，如此一來我們倒不如從最少的石頭來開始推論，說不定可以發現規律存在:

因為是我們先的關係，所以只要小於等於3時必定會贏

win: 1, 2, 3

而到4的時候，不管拿1還是2還是3，最後剩下的數量肯定小於等於3給對方拿，所以必定會輸

lose: 4

5的時候一開始只拿一個最後不管對方怎麼拿肯定輸，而6則是兩個，7則是三個

win: 5, 6, 7

到8的時候不管我拿1~3個，最後對方的數量會變成5~7個，而之前一開始我們拿5~7時必贏，這次換對方的數量變為5~7，所以接下來肯定必輸

lose: 8

從上面的推論我們可以發現在我們先拿的情況下，只要是4的倍數時必定會輸，其餘的情況則是必贏，而這個就是我們最後的結論。

程式碼解說:

從上述的結論可以知道4的倍數時必定會輸，所以取4的餘數如果為0就回傳false，其它的狀況則必定會贏就回傳true

1
2
3
4
if n%4 == 0 {
	return false
}
return true

完整程式碼:

1
2
3
4
5
6
func canWinNim(n int) bool {
	if n%4 == 0 {
		return false
	}
	return true
}

總結:

如果是同等智力且聰明的人在玩遊戲(不含運氣成分)，其遊戲過程必為1種，如此一來便能夠透過統計來整理出結論，進而準確預測之後隨著條件不同而造成的結果。

分享到