imicola 约瑟夫问题
约瑟夫问题

约瑟夫问题

525 字 · 约 1 分钟

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

现在我想知道幸存者的编号(编号从0开始)的多少

int josephus(int n, int k)
{
    int s = 0;
    for (int i = 2; i <= n; i++) s = (s + k) % i;
    return s + 1;
}
cpp

上述算法时间复杂度O(n)O(n),空间复杂度O(1)O(1),但对 k=2k = 2的情况我们可以有特殊解法使时间复杂度降低到O(log⁡n)O(\log n) : 引用自Wikipedia

答案的最漂亮的形式,与nn的二进制表示有关:把nn的第一位移动到最后,便得到f(n)f(n)。如果nn的二进制表示为n=b0b1b2b3…bmn=b_{0}b_{1}b_{2}b_{3}\dots b_{m}则f(n)=b1b2b3…bmb0f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}。这可以通过把nn表示为2m+l2^{m}+l来证明。

int yuesefu(int n)
{
    // 找到最高位的值,即n的最高位所代表的2的幂
    int highestBit = 1;
    while (highestBit <= n) {
        highestBit <<= 1; // 将最高位左移
    }
    // 移动后的结果
    return (n - (highestBit >> 1)) << 1 + 1;
 // return (n -  highestBit / 2) * 2 + 1
}
cpp