Nim Game (E)
題目
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.
Example:
Input: 4
Output: false
Explanation: 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.
題意
二人取石子游戲，每人一次可以取1-3個石子，取到最后一個石子的人獲勝，給定n個石子，問如果你先取，能否獲勝，
思路
找規律：
1勝 2勝 3勝 4敗 5勝 6勝 7勝 8敗 9勝 10勝 ...
簡單規律就是當n為4的倍數時會輸，
假設共有n個石子，每個人一次可取1-m個，那么顯然當n=(m+1)k時，先取的人必敗，因為后取的人總是可以將該輪取走的石子總數控制為m+1；而當n=(m+1)k+x時，只要先取的人只取x個，情況就變成了相當于后取的人從(m+1)k個石子開始取，這樣先取的人總能控制每輪取走總數為m+1，從而能保證勝利，
代碼實作
Java
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41164.html
標籤：其他