约瑟夫环问题注记

---

    约瑟夫环问题注记
    作者：tyc611.cublog.cn，2008-10-19

---

约瑟夫环问题J(n,m)：有编号为1,2,3,...,n的n个人按顺时针站成一圈。然后，从编号为1的人开始沿顺时针方向从1开始报数，数到m的人出列，下一个人重新从1开始报数。重复此过程，直到最后剩下一人。请问最后剩下一人的编号J(n,m)是多少。

为了方便分析问题，我们把n个人的编号调整为0,1,2,...,n-1，此时的结果记为JJ(n,m)，则J(n,m) = JJ(n,m)+1。

对于编号为0,1,2,...,n-1的n个人，第一个出列的人的编号为(m%n - 1)。剩下的(n-1)个人的编号为0,1,...,k-2,k,...,n-1（其中，k=m%n），重新排列为P1=k,k+1,...,n-1,0,1,...,k-2。

可利用公式(i-k)%n（其中，i为前面排列中的每一个编号）把排列P1转换为排列P2=0,1,...,n-1-k,n-k,n-k+1,...,n-2，从而得到子问题JJ(n-1,m)。也可以通过公式(i+k)%n把排列P2转换回为排列P1。

因此，原问题的解为JJ(n,m) = (JJ(n-1,m)+k)%n = (JJ(n-1,m)+m%n)%n = (JJ(n-1,m)+m)%n。

于是，我们得到递推公式
    JJ(n,m) = (JJ(n-1,m)+m)%n
    JJ(n-1,m) = (JJ(n-2,m)+m)%(n-1)
    ...
    JJ(2,m) = (JJ(1,m)+m)%2

而JJ(1,m) = 0，由前面的递推公式从JJ(1,m)可推算得到JJ(n,m)。进一步得到J(n,m) = JJ(n,m)+1。

实现代码如下：

#include
using namespace std;

int main()
{
    int n, m;
   
    while (true) {
        cout << "Input 'n' and 'm': \n";
        cin >> n >> m;
        if (cin.eof() || cin.fail())
            break;
       
        int x = 0;
        for (int i = 2; i <= n; ++i)
            x = (x + m) % i;
        cout << "The last one: " << (x + 1) << '\n' << endl;
    }
}

运行测试结果：
Input 'n' and 'm':
10 4
The last one: 5

Input 'n' and 'm':
578921563　2
The last one: 84101303

Input 'n' and 'm':
^D

对于一般约瑟夫环问题J(n,m)，上面给出的是一个很好的解答。但对于m=2的特殊情形J(n,2)，有一个特殊的解法（详细分析见《Concrete Mathematics》（2nd）节1.3，这里只给出结论）。

如果把n表示二进制数 n = (b[k]b[k-1]...b[1]b[0])B，那么
J(n,2) = J((b[k]b[k-1]...b[1]b[0])B) = (b[k-1]...b[1]b[0]b[k])B
也就是，J(n,2)等于把n循环左移1位。

实现代码如下：

#include
using namespace std;

template
int GetValidBits(UnsignedInteger number)
{
    int count = 0;
    int bits = sizeof(UnsignedInteger) * 8 / 2;
    while (number > 0) {
        if (bits == 0) {
            count += 1;
            break;
        }
        if (number >> bits) {
            count += bits;
            number >>= bits;
        }
        bits /= 2;
    }
    return count;
}

int main()
{
    while (true) {
        unsigned int n;
        cout << "Input 'n' for J(n,2): \n";
        cin >> n;
        if (cin.eof() || cin.fail())
            break;
        if (n == 0)
            continue;
       
        int bits = GetValidBits(n);
        unsigned int mask = 1;
        mask <<= bits - 1;
        unsigned int x = ((n & ~mask) << 1) | 1;
        cout << "The last one: " << x << '\n' << endl;
    }
}

程序运行测试结果如下：
Input 'n' for J(n,2):
10
The last one: 5

Input 'n' for J(n,2):
100
The last one: 73

Input 'n' for J(n,2):
578921563
The last one: 84101303

Input 'n' for J(n,2):
^D

显然，第二个程序的效率要高很多，特别是输入的数很大时！

---