golang[107]-约瑟夫问题与2的次方的特性

问题描述

约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

13人的例子,最后赢家为11号

我们以k = 2 即跳过1人后 执行下一个人为例,来探讨一个有趣的性质。

假设参与人数为2的次方数。

参与人数为8人的情形

每回合消除的人数与二叉树类似。
Pass 1 four people: 2, 4, 6, 8.
Pass 2 two people: 3, 7
Pass 3 one person: 5

最后剩下的人数为1号,这不是偶然的。
我们可以用归纳法证明:
当参与人数是2^m+1, 经过一轮后,减少人数到2^m,并且减少的都是偶数的编号,编号1保留。
因此总会到达上面我们讨论的8人数,得证。

当参与人数不是2的幂

有一点我们是肯定的,当参数人数不是2的幂后,编号1一定不是最后的幸存者。
这是由于总有一次参数会是一个奇数,编号1就会被下一轮干掉。

参数人数不是2的幂

Pass 1 eliminates six people: 2, 4, 6, 8, 10, 12.
Pass 2 eliminates four people: 1, 5, 9, 13.
Pass 3 eliminates one person: 7.
Pass 4 eliminates one person: 3.

分析:当参与人数不是2的幂时, 到某一时刻总会变为2的幂。
变为2的幂后就会符合上面我们指出的规律。

分析

分析

假设参数人数是n = 2^m + k

那么 在 k 次消除后, n = 2 ^ m 次数编码到达了2k + 1。
因此可以证明编号2k + 1 就是幸存者。

假设n = 2^m + k
m = 2k + 1

可证 w = 2(n - 2^m)+1
即 w = 2(n - 2^(log2(n)))+1

编程求最后一个安全数

编程求最后一个安全数的最快方法是
假设 n = 0x1 0 1 0 0 1
则安全数为 = 0x010011
即将最前面的1移动到最后方。

(bits.Len64(x) 计算x的最高位。
( 1 << (bits.Len64(x)) -1 ) 最高位变为0
(x << 1 | 1) 最低位加1。

1
2
3
func calEndVal(x uint64) uint64{
return ( 1 << (bits.Len64(x)) -1 ) & (x << 1 | 1)
}