如何打印约瑟夫序列?

Question

CSES问题Josephus问题I要求我们打印n个人且k = 2时人们是如何被选中的序列。我在这里找到了一个优雅的解决方案。基本上，代码类似于这样:

void J(int n)
{
int a = 1, b = 0;
while (n > 0)
{
for (int i = 2; i <= n; i += 2)
{
cout << a * i + b << ' ';
}
if (n & 1)
cout << a + b << ' ', b += a;
else
b -= a;
a <<= 1;
n >>= 1;
}
}

有人能解释一下为什么它有效吗?

Answer 1

我对代码做了一些修改，以说明它是如何工作的。

void J(int n)
{
int a = 1, b = 0;
while (n > 0)
{
std::cout << "n=" << n << std::endl;
std::cout << "a=" << a << ", b=" << b << std::endl;
for (int i = 2; i <= n; i += 2)
{
std::cout << a * i + b << ' ';
}
if (n & 1) // equivalent to n % 2 == 1 (if n is odd)
std::cout << '*' << a + b << ' ', b += a;
else
b -= a;

std::cout << std::endl;
a <<= 1; // a = a * 2;
n >>= 1; // n = n / 2;
}
}

首先要注意的是，变量a和b被初始化为允许我们计算将在我们绕圈时被淘汰的人的位置的值(也使用for循环中的迭代器i)。a = 1, b = 0的初始值是，这样我们就可以在第一次迭代中消除所有偶数人。

接下来，每次通过while(n)循环，剩下的一半人将被淘汰。如果n是奇数，我们循环回到循环的开始，并消除当前迭代开始时的人。

我认为这里棘手的部分是a和b的值如何在if语句中变化。如果n为奇数，则将b加a的值。如果n是偶数，我们用b减去a的值。然后我们将a的值加倍，为下一次循环做准备。选择a和b的值是为了说明通过消除之前迭代中的位置而留下的圆的间隙。

最后，在下一次迭代之前，我们将n除以2，因为圆圈中剩下的人数是原来的一半。下面是n=19运行的示例。

输出:

n=19
a=1, b=0
2 4 6 8 10 12 14 16 18 *1
n=9
a=2, b=1
5 9 13 17 *3
n=4
a=4, b=3
11 19
n=2
a=8, b=-1
15
n=1
a=16, b=-9
*7