Skip to content

Latest commit

 

History

History
19 lines (12 loc) · 1.64 KB

README.md

File metadata and controls

19 lines (12 loc) · 1.64 KB

292.Nim游戏

问题描述

你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。

样例
输入: 4
输出: false
解释: 如果堆中有 4 块石头,那么你永远不会赢得比赛;因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

解决方案

  初看这个题目觉得要考虑很多种情况。但是其实,仔细想想并不是这样的,为什么样例数据是4的时候先手不论怎么样都是输呢。
  假设参与游戏的两个人是a和b,a拿掉1-3之间任意一个数字na的石头,b总可以选择拿4-na个石头,这样如果石头的总数是4的倍数的时候,a先手无论怎么拿掉石头,b都可以保证每一轮两个人一共拿掉4个石头(即剩余石头数永远保持4的倍数)。这样b一定有办法可以拿到最后一块石头,所以当总数是4的倍数时,后手方b总有办法可以获得胜利。
  考虑到这种情况,当石头总数不是4的整数倍的时候,只要先手方a第一次取走的石头数目能保证剩下的石头数目是4的倍数(因为可以取走1-3个石头,所以肯定能保证),就可以转换成“石头总数是4的倍数,但是先手方变成b”的情况了,所以只要石头数目不是4的倍数,先手方a总有方法可以取胜。