博弈论之Nim Game

Nim Game这个游戏是:

有一堆石头叠在一起。然后两个人互相remove石头from top. 一个人一次可以拿1--3块石头。

whoever remove the last pieces win. 游戏由我方开始。

这个题的level是一个Easy,但是我很可耻的没有做出来。【基本就是想了10秒就放弃了。。。】

正确的思考逻辑是: 什么情况我们会输? 假设最简单的case, 4个石头。 我先拿1--3块石头。 发现拿不完,但是剩下的1--3块石头刚好对手可以一次性拿走。 这种情况我们赢不了。

那如果5块石头呢?我一次拿1块, 对手就会只剩4块石头。 这时候我们根据4块石头的case得出结论,我一定能赢。 如果6块石头呢? 我一次拿2块石头,又让情况回到了4块石头的水平。

所以这个pattern 看下来,如果我有办法让对手那轮只剩4个石头,我就赢定了,否则我就输定了。到这里都还属于比较简单的, 但是怎么代码怎么实现这个判断呢?

我觉得从这里还是看不出来。。。

需要举更多的例子来看出。 【最重要的部分】假设8块石头,我一次可以拿1--3块石头。但是对手可以通过调整数量使下一次轮到我的时候 只剩4个石头,所以8个石头的case 我是一定输的。得出一个结论,谁轮到8个石头谁输。 那12个石头呢? 假设我先,我能拿1-3个,对手可以逼迫我回到8个石头的情况,我还是输。所以只要是4的倍数,我就赢不了。

return(n%4!=0);

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 好莱坞大片中肉末横飞漫天浓烟的场面震撼吗?这时如果没有高能量的音乐烘托气氛,简直就像看毛片却把声音关掉了。来看看在...
    izan阅读 3,446评论 2 3
  • 这是一种极至的享受吧, 我裹着暖暖的睡袍,静静地坐在窗前, 看落日的褪去。 耳边是清新的钢琴曲,回旋在我的房间,有...
    路还长天会亮阅读 1,209评论 0 2