292. 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, 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.

思路

纯数学题，这种题目一般找规律用数学归纳法

  • stones = 1: 拿一个，必赢
  • stones = 2: 拿两个，必赢
  • stones = 3: 拿三个，必赢
  • stones = 4: 不管拿几个，必输
  • stones = 5: 拿一个，必赢
  • stones = 6: 拿两个，必赢
  • stones = 7: 拿三个，必赢
  • stones = 8: 不管拿几个，必输
  • ...........

由此可见 当 stones 是 4 的倍数是必输

bool canWinNim(int n) {
    
    return n % 4;  // 无需考虑负数的情况，这个应该是调用者自己负责
    
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容