CLRS 14-2 Josephus问题的定义如下：假设n个人排成环形，且有以正整数m<=n。从某个制定的人开始，沿环报数，每遇到第m个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列为<3,6,2,7,5,1,4>。
a)假设m为整数。请描述一个O(n)时间的算法，使之对给定的整数n，输出(n, m)-Josephus排列。b)假设m不是个常数。请描述一个O(nlgn)时间的算法，使给定的整数n和m，输出(n, m)-Josephus排列。解答：
a)首先，我们很容易想到用一个循环链表，即最后一个结点指向头结点的单链表。然后，选定一个结点，走m步，输出此结点的值，然后删除之，然后再走m步，依次循环下去，由于建立链表时间为O(n)，而删除的过程为O(m*n)，由于m为常数，故总的时间复杂度为O(n)。(伪)伪代码：//i为起始点 1 PROCESS(list, i) 2 { 3 node = list.get(i); 4 while (list != NULL) 5 { 6 for (i = 0; i < m-1; i++) 7 { 8 node = node->link; 9 }10 tmp = node;//保存node的副本11 print node->key;//输出值12 node = node->link;//在删除之前指向下一个结点13 delete tmp;//从链表删除，当然，之前还有指针之间的链接转变14 }15 } 1 //建立顺序统计树，在题设中，原始数据是一个排好序的数组，即{1,2,3...n} 2 CreateTree() 3 { 4 for (i = 1; i <= n; i++) 5 insert(T, node[i]);//node存储的是数组元素 6 } 7 8 //T为顺序统计树，i为选择的起始点，这里的i表示的是位置，不是node里面的key值，可以理解为第i小的数 9 Process(T, i)10 {11 while (T != NULL)12 {13 i = (i+m-2)%(n--) + 1;//在这里，我们不用(i+m-1)%(n--)，是因为这个表达式可能计算的结果等于0，但i != 0;14 print key[OS-SELECT(T, i)];15 OS-DELETE(T, i);16 }17 } 我们来对数组{1，2，3，4，5，6，7}走一遍，我们选择第一个数为起始点，i=1，选择m=3，则
i = (i+m-2)%(n--) + 1 = 3，好的，输出第3个数，即3，然后去除3，剩下{1,2,4,5,6,7}，n=6接着i = (i+m-2)%(n--) + 1 = 5,好的，输出第5个数（这里不是5，在树中剩下的元素中，是第五小的数），即为6，然后删除6，现在剩下元素为{1,2,4,5,7},n=5,接着i = (i+m-2)%(n--) + 1 = 2，好的，输出第2个数，即为2，然后删除2，现在剩下元素为{1,4,5,7}，n=4，接着i = (i+m-2)%(n--) + 1 = 4，输出第四个数，即为7，然后删除7，现在剩下元素为{1,4,5},n=3，接着......我们发现，这个算法的执行是正确的。