记LC292 Nim游戏

下面描述一下我的解题思路:

  首先,我回忆了一下Nim博弈的规律,后来发现想不起来,决定自己想。但其实心里觉得自己肯定想不出来,可能又要看题解了。

  在N小于等于4时,是可以直接推得结果的。看见题目中“你们是聪明人,每一步都是最优解。”,会不会要考虑平手的情况?我想起了SG博弈里的递归求解,后来我就想能不能这么做。但不太敢下手编程,没有很清楚的思路。我甚至没有看题目中有没有平手的说明,只是想到了这个可能,没有分析就认定了?还觉得自己应该没漏什么可能吧。

  后来又想了一会儿,就觉得我应该做不出来,先放一下吧,结果放了之后更没劲了,过了一天就看了题解,发现原来只要判断是否是4的倍数即可。

  题目理解有问题,题目信息没有分析到位,还很可能读错题。

  我似乎是在记题,而从没有认真的分析这个题目,也没有掌握分析题目的方法,只是把自己已知的或者说想到的往里套。

 

马后炮分析:

  两个人Nim一堆石子,我先手,轮流拿1~3块石头,拿到最后1块胜利。也就是说,我如果想赢,就必须保证不论对方怎么选,我能让对方给我留下1~3块的石堆。如何保证至少1块?因为每次最多只能拿3块,我每次必须给对手留下大于3块的石堆。接着倒推,如果倒数第二局对手碰到4,我赢,如果是5,我输,这样就可以发现必须留给对手4的倍数才行。

原文地址:https://www.cnblogs.com/canchan/p/12857846.html