nim游戏与进位制


在博弈论里最经典的题目就是nim游戏了,nim游戏是说,有若干堆石子,每次可以选择一堆石子,从这堆石子中拿走任意数量的石子,也就是至少拿走一个,最多把这堆石子全部拿走,两人轮流取,谁取走最后一个石子谁就赢,也就是无石子可取的人就输了,问是否先手必胜。

nim游戏的解答很难让人去联想到和进位制的关系,而nim游戏就是利用二进制完美解决了。假设有n堆石子,数量分别为a1,a2,a3...an,那么如果石子的异或和不是0那么先手必胜也就是a1^a2^...^an!=0那么,先手必胜。

考虑这样一个事实,若干个数的异或和为非0,我们总能只通过减小某个数的大小,从而使异或和为0。我们只要减小和异或和最高位所在的位置都是1的那个数即可。比如3个数,0101,0100,0010(都是二进制的),异或是0011,那么只要减小0010即可,而且这个数总能找到,因为必定有某个数在那个位置贡献了1。这样我们把那个数的对应异或和里是1的位置1变0,0变1即可,对于刚才的例子就是把0010变成0001。

有了上面的事实,回到nim游戏,先手总可以把石子的异或和变为0,而后手无论怎么做都只能把异或和变为非0,这样先手一定可以达到异或和是0的没有石子的状态,也就是赢了这个游戏。

ok,扩展一下,如果每次不是选择一堆石子而是选择两堆石子去取呢,这个时候就是考虑三进制的异或和了(感谢3楼提醒,这里有点小trick,就是数字仍然是变为2进制,但是异或操作是3进制的异或操作)。也就是说只要异或和不是0,总可以通过减少两个数使得异或和是0,而且,只要异或和是0,不管怎么减少任意两堆石子,异或和都会变为非0。如果还是二进制的话,后手显然可以通过改变两堆石子使得异或仍为0,这样就不能保证先手必胜了。

-------------我是nim游戏的分割线---------------

让我们再看一个进位制妙用的例子。记得有一个有趣的题是这样的,给定若干个数,其中只有一个数出现了1次,其他的都出现了2次,如何只用额外的常数空间找到这个数呢。熟悉这道题的一般一眼就看出答案了吧,就是把所有数异或,那么就可以找到这个数了。

进一步的,如果只有一个数只出现了1次,其他的出现了3次呢,相信看过本文的童鞋们一定可以想到,这次只要利用三进制的异或和就可以轻松解决了。当然还有其他扩展如有两个数出现1次,其他的出现2次,或者有一个数出现2次,其他的出现3次啦,这里就不再赘述了。

总之有时候利用进位制的一些特性,帮我们解决题目的时候会有意想不到的结果呢。

您可能喜欢:
我猜您可能还喜欢:

《nim游戏与进位制》有 8 条评论

  1. 话说第一个把nim想到二进制的真NB啊;conway大神把博弈弄到surreal number上的不合理形式上更NB啊……

  2. 路过的 | #2

    有两个数出现1次,其他的出现2次,有什么好方法?
    我的思路是:先a1...an异或一次,取异或的结果中1最高位将a1...an分为两堆,再对两堆分别取异或,即可得到这两个数。

  3. 路过的 | #3

    "这个时候就是考虑三进制的异或和了。也就是说只要异或和不是0,总可以通过减少两个数使得异或和是0,而且,只要异或和是0,不管怎么减少任意两堆石子,异或和都会变为非0。"

    这段话怎么理解?据我所知,如果三进制非要说异或的话,应该是这样的吧:
    1 xor 0 = 1
    1 xor 1 = 2
    1 xor 2 = 0
    2 xor 0 = 2
    2 xor 2 = 1
    0 xor 0 = 0

    如果是这样的话,剩下两堆,分别为3和6,则按照3进制异或为0,但实际上只要是剩下两堆的,先手总是会赢的。不知道博主说的三进制异或是什么意思,能否给个例子?

发表评论