约瑟夫问题：递归的角度

Posted on | Edited on | In ,

约瑟夫问题(The Josephus Problem)是计算机科学中一个经典问题，编程语言教学中它经常作为练习题。虽然司空见惯，背后却隐藏着玄机。它又如何与进位制转换扯上关系呢？本篇文章从递归的角度来重新解析这个流传近2000年的老问题，并提出一类递推式的快速解法。

问题定义

经典的约瑟夫问题定义如下：

有n个人，标号为 1 ~ n，从n开始，每隔一个人死于非命，求幸存者编号J(n)

问题很简洁。它的背景是犹太罗马战争时期，有兴趣者移步。举个简单的例子，假如 n = 10，那么：

  • 第一轮淘汰：2 4 6 8 10 死于非命，剩下 1 3 5 7 9 开始新的一轮淘汰
  • 第二轮淘汰：3 7 死于非命，剩下 1 5 9 继续
  • 第三轮淘汰：1 9 死于非命，剩下 5
  • Game over

可以发现，每一轮淘汰后（n个人），下一轮实际参与人只有 n/2。它的结果是和 J(n/2) 是同一个人，仅仅标号不同而已，而标号之间存在对应关系。上面的例子是偶数个人，以奇数个人试一试会有同样的发现。

问题求解

这个问题的暴力解法是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *flag;
int n;
// 查找当前元素cur隔一个的活人
int next(int cur)
{
  // 跳过所有的死人，得到接下来的活人
  while(!flag[ ++cur % n]);
  // 跳过得到活人后面的所有死人，得到隔一个的活人
  while(!flag[ ++cur % n]);
  return cur % n;
}

int main()
{
  printf("Please input the number:");
  scanf(" %d", &n);
  flag = (char*) malloc(sizeof(char)*n);
  // 初始为活
  memset(flag, 1, n);
  // 死 n－1 个人
  int dead, cur = 0;
  for(dead=0; dead < n ; dead++)
  {
    int tmp = next(cur);
    flag[tmp] = 0;
    cur = tmp;
  }
  free(flag);
  printf("Alive: %d\n", cur == 0? n:cur);
  return 0;
}

它的思路很简单，使用数组模拟人的死亡，下标为0的元素表示n号对应的人，由于这n个人形成的是环，这样做是可以的。这段代码看注释容易明白。当然还可以使用循环队列来解决问题，这样更直观，但效率相对较低。

这种解法却没有利用到上面提到的规律，进一步发掘那个规律，J(10)第一轮剩下的五个人相当于J(5)重新编号，而且是 

J(10)站在同一位置的编号 = J(5)对应的编号*2 - 1

同理 J(5)第一轮剩下的两个人相当于J(2)重新编号：

J(5)站在同一位置的编号 = J(2)对应的编号*2 + 1

即存在以下递归关系：

J(1) = 1;
J(2n) = 2J(n) - 1    n≥1;
J(2n+1) = 2J(n) + 1    n≥1;

这个递推式按照指数形式缩减n，但是这种形式不便于计算，我们需要找到一种封闭的形式，通常可以看到更多的信息。

这个解答使用 Common Lisp 描述如下：

1
2
3
4
5
6
7
8
9
10
(format t "Please input the number: ")
(setf n (read))

(defun josephus (n)
  (cond ((= n 1) 1)
    ((= (mod n 2) 0)
        (- (* 2 (josephus (/ n 2))) 1))
    (t (+ (* 2 (josephus (/ (- n 1) 2))) 1))))

(format t "Alive: ~A~%" (josephus n))

下面这个式子是显而易见的：

J(2n+1) - J(2n) = 2;

使用这个递推关系或者上面的程序可以得出下面这张表：

n 1 . 2 3 . 4 5 6 7 . 8 9 10 11 12 13 14 15 . 16
J(n) 1 . 1 3 . 1 3 5 7 . 1 3 5 7 9 11 13 15 . 1

尤里卡！按照上面的分组，每一组的J(n)都是从1开始，依次递增2。可以用以下的形式改写上述递推式：

J(2^m + l) = 2l + 1;

其中 2^m + l = n，2^m 是不超过n的2的最大次幂，l是余下的数。这个结论使用数学归纳法很容易证明。有了这个式子，无需递归就可以线性时间解决这个问题。

递推式与进位制

上述递推式涉及到2的次幂，很容易联想到二进制。如果令：

n (radix 10) = AmAm-1...A0 (radix 2)
n = Am * 2^m + Am-1 * 2^m-1 + ... + A0

那么：

Am = 1
l = Am-1 * 2^m-1 + ... + A0

J(n) = 2*(Am-1 * 2^m-1 + ... + A0) + 1
     = Am-1 * 2^m + ... + A0 * 2 + 1
     = Am-1Am-2...A0Am (radix 2)

好了，一个很明显的规律浮现了：

J(n) = n对应二进制数循环左移一位

验证一下：

J(10) = J(1010 (radix 2)) = 101 (radix 2) = 5
J(15) = J(1111 (radix 2)) = 1111 (radix 2) = 15

好了，虽然同为线性时间，但这个解比上一个解更加简洁，效率稍微高一点。

问题推广

上述问题描述的是每两个人有一个人死于非命，推广成一般情形：每隔a个人有一个人死于非命。那么上述递推式的形式转换成：

J(1) = a
J(2) = b
...
J(n-1) = c

J(an) = a * J(n) + x
...
J(an + (a-1)) = a * J(n) + z

我们猜测J(n)与a进制有对应的关系。将n表示为n进制数：

n = Am * a^m + ... + A1 * a + A0
  • n / a 以后余数 A0，使用 J(an+A0) 与 J(n) 关系的递推式。
  • n / a / a 以后余数 A1，使用 J(an+A1) 与 J(n) 关系的递推式。
  • 依次类推…
  • n / a^m 以后，只剩下余数l，这时递推式结束，结果是 J(l) 对应的值。

上述过程需要好好理解。重新整理上述过程，将它们联系起来，可以发现：

J(an+A0) 与 J(n) 关系的递推式常量值需乘以 3^0，J(an+A1) 与 J(n) 关系的递推式常量值需乘以 3^1，...，J(an+Am-1) 与 J(n) 关系的递推式常量值需乘以 3^m-1，J(l)需乘以 3^m。

也就是说，除了最高位，其它位都是选择递推式的常量值，最高位选择初始值。然后相加即为结果。

描述太过抽象，举个简单的例子：

J(1) = 4
J(2) = 8
J(3n) = 3J(n) - 1
J(3n+1) = 3J(n) + 4
J(3n+2) = 3J(n) + 5
求J(101)

使用上述结论：

J(101) = J(10202 (radix 3)) = 4*3^4 - 1*3^3 + 5*3^2 -1*3^1 + 5 = 344

验证一下：

J(101) = J(3*33+2) 
        = 3*J(33) + 5 
        = 3*J(3*11) + 5 
        = 3*(3*J(11) - 1) + 5 
        = 3*(3*J(3*3+2) - 1) + 5 
        = 3*(3*(3*J(3)+5) - 1) + 5 
        = 3*(3*(3*(3*J(1) - 1)+5) - 1) + 5 
        = 3*(3*(3*(3*4 - 1)+5) - 1) + 5 
        = 344

bingo！好了，此类递归式以后可以很容易求解了。

重新审视

上述一般的规律，实际上就是对递推式求解过程的重新编码，利用进位制转换关系，简化了求解过程。显然利用递归使用原递推式编程实现是很简单的，但效率不高。

一般的规律当然适用于特殊的二进制，但是我们在问题求解中得到的结论却是另一种，我们来重新审视一下：

n = Am*2^m +...+ A0

利用上述规律，n展开后，当某一位为0时替换成－1，为1时不变。即：

n对应的二进制 － n按位取反

也就是说，n循环左移一位的值和n对应的二进制数 － n按位取反后的二进制数是相等的。

拿J(10)验证一下：

1011 - 100 = 111
1010 - 101 = 101
...

小小的问题中竟然隐藏着这么多的奥秘！如此简洁的解答体现出数学之美！

后记

本篇文章问题推广以前部分详细描述可见其第一章，受启发于参考文献,问题推广及以后部分为自由发挥，如有问题请指正。

参考文献

  • Concrete Mathematics: A Fundation for Computer Science
    Ronald L. Graham, Donald E. Knuth, Oren Patashnik