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);