数学 模拟 递归与递推

约瑟夫问题

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

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

Tip

考虑在有$n-1$个人，处决$k$的情况下最后一个人的编号是$f(n-1,k)$,那么对$n$个人而言，有递推式==$f(n,k)=(f(n-1,k)+k)\mathrm{mod}n$==

递推式求解抽象化：考虑对$f(n-1,k)$，扩展到$n$人时，我们只需要将第$k$个人处决，问题便又回到了对$n-1$人中找$f(n-1,k)$的问题上，但我们删除编号$k$个数时候,所有数的编号都会进行变化映射,即新的环的起点发生了变化,即集体向后移动$k$位且保证在$n$范围内,所以需要取模与n

即 : ==$f(n,k)=(f(n-1,k)+k)\mathrm{mod}n$==

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

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

答案的最漂亮的形式，与$n$的二进制表示有关：把$n$的第一位移动到最后，便得到$f(n)$。如果$n$的二进制表示为$n=b_0{b}_1{b}_2{b}_3\dots b_m$则$f(n)=b_1{b}_2{b}_3\dots b_m{b}_0$。这可以通过把$n$表示为$2^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
}