约瑟夫问题
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,处刑下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。
现在我想知道幸存者的编号(编号从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上述算法时间复杂度,空间复杂度,但对 的情况我们可以有特殊解法使时间复杂度降低到 : 引用自Wikipedia
答案的最漂亮的形式,与的二进制表示有关:把的第一位移动到最后,便得到。如果的二进制表示为则。这可以通过把表示为来证明。
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