标签:
幽魂之家数学逻辑游戏文化 |
分类: 休闲娱乐类 |
在《数学逻辑游戏01:世纪末日,如何逃脱?》中给出了三个类似的数学游戏题。这些题的一般形式是给定n人,找出最后剩下的是哪个位置的人。这类题目是有一般解法的:找出与n最接近的2的幂,剩下的数乘2加1就是答案。
设n = 2^s + t,其中t<2^s,则m = 2*t + 1就是答案。
对于《数学逻辑游戏01:世纪末日,如何逃脱?》中的三个题,它们的答案就是:
1. n = 13 = 8+5,m = 11 = 2*5+1。
2. n = 30 = 16+14,m = 29 = 2*14+1。
3. n = 1997 = 1024+973,m = 1946 = 2*973+1。
用二进制可以给出一个简单的方法:
将 n化为二进制,将这个二进制的首位1放到最后,得到的新的二进制就是答案m。
1. n = 13 = 1101,m = 11 = 1011。
2. n = 30 = 11110,m = 29 = 11101。
3. n = 1997 = 11111001101,m = 1946 = 11110011011
分析一下为什么这两种做法是一样的?
将二进制的首位1放到最后,得到的新的二进制,可以分解成三步,
1. 去掉首位1。
2. 整个向前移一位。
3. 最后一位添上1。
如果 n = 2^s + t ,则化为二进制就有 s + 1 位,首位1就是
2^s,去掉这首位就是t,整个向前移一位就是乘2,得2*t,最后一位添上1就是加1,得 2*t + 1 。