我在做一些编码方面的挑战,结果出现了一个问题,大致是这样的:
“两名选手轮流从一名选手开始。有N个
每名球员轮流拿1、2或3根棍子
玩家拿最后一棒输,目标是找到一个算法
这样一来,玩家1可以肯定地获胜(不一定总是可能的,玩家2应该轮流获胜),输出1、2或3作为
开始的棍子数,如果不可能赢的话,可以是0。
输入为N。示例:输入:2输出:1“
我试着去想,但我想到的是,这需要检查每一个可能的结果,因为如果N很大的话,所有的可能性都可能被联系在一起我还认为,如果最后一根棍子要由2号球员接过才能不输,那就是N-1被1号球员接过(无论是只接过N-1还是N-1,N-2还是N-1,N-2,N-3),把N留给2号球员,这是确保胜利的唯一方法。
结果发现解决方案是(n-1)mod 4,但我不明白为什么会这样。
所以我的问题是,如何处理这样的问题,为什么解是模还有没有办法发现这样的模问题其他的程序员做得相当快,所以我认为实践是完美的,但我不知道从哪里开始。
最佳答案
它是模4,因为如果一个玩家有优势,如果第一个玩家拿了1,他可以拿3根棍子保持同样的优势,如果第一个玩家拿了2,如果第一个玩家拿了3,他可以拿1根棍子另一个玩家已经没有任何控制权了。
把问题倒过来:
你不需要关心一个大n,你只需要分析一下当只剩下4根或更少的树枝时的情况。
剩下1,2,3或4支时谁会赢?
当剩下4N+1、4N+2、4N+3或4N+4杆时,谁会赢?