小朋友学数据结构（1）：约瑟夫环的三种解法
约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。
约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
解法一：用循环链表实现
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}Node;
/**
* @功能 约瑟夫环
* @参数 total:总人数
* @参数 from:第一个报数的人
* @参数 count:出列者喊到的数
* @作者 zheng
* @更新 2013-12-5
*/
void JOSEPHUS(int total, int from, int count)
{
Node *p1, *head;
head = NULL;
int i;
// 建立循环链表
for(i = 1; i <= total; i++)
{
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = i;
if(NULL == head)
{
head = newNode;
}
else
{
p1->next = newNode;
}
p1 = newNode;
}
p1->next = head; // 尾节点连到头结点，使整个链表循环起来
p1 = head; // 使pcur指向头节点
// 把当前指针pcur移动到第一个报数的人
// 若从第一个人开始报数，这一段可要可不要
for(i = 1; i < from; i++)
{
p1 = p1->next;
}
Node *p2 = NULL;
// 循环地删除队列中报到count的结点
while(p1->next != p1)
{
for(i = 1; i < count; i++)
{
p2 = p1;
p1 = p1->next;
}
p2->next = p1->next;
printf("Delete number: %d\n", p1->data); // 打印所要删除结点的数据
free(p1); // 删除结点，从内存释放该结点占用的内存空间
p1 = p2->next; // p1指针指向新的结点p2->next，即原先的p1->next
}
printf("The last one is No.%d\n", p1->data);
}
int main()
{
int total, from, count;
scanf("%d%d%d", &total, &from, &count);
JOSEPHUS(total, from, count);
return 0;
}
运行结果：
13 1 3
Delete number: 3
Delete number: 6
Delete number: 9
Delete number: 12
Delete number: 2
Delete number: 7
Delete number: 11
Delete number: 4
Delete number: 10
Delete number: 5
Delete number: 1
Delete number: 8
The last one is No.13
解法二：数组实现
思路：设数组a有n个变量，每个变量中初始放的标识数是1，表示这个人在队列里，若出列标识数就变为0。
现在计数器从1开始向后数，每报一个数即把累加器加1。这里累加器表示报数人数。累列到m时，报数的人要出列，标识数要变为0。下一个人从1开始重新报数。
报到最后一个人后，从第一个人开始继续报数。
#include<stdio.h>
#include<memory.h>
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int flag[n + 1]; // 在队列里标记为1，出列标记为0
memset(flag, 0, sizeof(flag)); //把数组每个元素置0，在memory.h中声明
int i = 0;
int outCnt = 0; // 记录出列的人数
int numoff = 0; // 报数
// 默认都标记为1
for(i = 1; i <= n; i++)
{
flag[i] = 1;
}
while(outCnt < n - 1)
{
for(i = 1; i <= n; i++ )
{
if (1 == flag[i])
{
numoff++;
if(numoff == m)
{
printf("Dequeue：%d\n", i);
outCnt++;
flag[i] = 0; // 已出列的人标记为0
numoff = 0; // 从头开始报数
}
}
}
}
for(i = 1; i <= n; i++)
{
if(1 == flag[i])
{
printf("The last one is: %d\n", i);
}
}
return 0;
}
运行结果：
13 3
Dequeue：3
Dequeue：6
Dequeue：9
Dequeue：12
Dequeue：2
Dequeue：7
Dequeue：11
Dequeue：4
Dequeue：10
Dequeue：5
Dequeue：1
Dequeue：8
The last one is: 13
解法三：用数学公式求解
上面编写的解约瑟夫环的程序模拟了整个报数的过程，因为N和M都比较小，程序运行时间还可以接受，很快就可以出计算结果。可是，当参与的总人数N及出列值M非常大时，其运算速度就慢下来。例如，当N的值有上百万，M的值为几万时，到最后虽然只剩2个人，也需要循环几万次（由M的数量决定）才能确定2个人中下一个出列的序号。显然，在这个程序的执行过程中，很多步骤都是进行重复无用的循环。
那么，能不能设计出更有效率的程序呢？
办法当然有。其中，在约瑟夫环中，只是需要求出最后的一个出列者最初的序号，而不必要去模拟整个报数的过程。因此，为了追求效率，可以考虑从数学角度进行推算，找出规律然后再编写程序即可。
为了讨论方便，先根据原意将问题用数学语言进行描述。
问题：将编号为0～（N–1）这N个人进行圆形排列，按顺时针从0开始报数，报到M–1的人退出圆形队列，剩下的人继续从0开始报数，不断重复。求最后出列者最初在圆形队列中的编号。
下面首先列出0~(N-1)这N个人的原始编号如下：
0 1 2 3 … N-3 N-2 N-1
根据前面曾经推导的过程可知，第一个出列人的编号一定是(M–1)%N。例如，在13个人中，若报到3的人出列，则第一个出列人的编号一定是(3–1)%13=2，注意这里的编号是从0开始的，因此编号2实际对应以1为起点中的编号3。根据前面的描述，m的前一个元素(M–1)已经出列，则出列1人后的列表如下：
0 1 2 3 … M-3 M-2 ○ M M+1 M+2 … N-3 N-2 N-1
注意，上面的圆圈表示被删除的数。
根据规则，当有人出列之后，下一个位置的人又从0开始报数，则以上列表可调整为以下形式（即以M位置开始，N–1之后再接上0、1、2……，形成环状）：
M M+1 M+2 … N-2 N-1 0 1 … M-3 M-2
按上面排列的顺序从0开始重新编号，可得到下面的对应关系：
M M+1 M+2 … N-2 N-1 0 1 … M-3 M-2
0 1 2 … N-(M+2) N-(M+1) N-M N-(M-1) … N-3 N-2
这里，假设上一行的数为x，下一行的数为y，则对应关系为:
y = (x - M + N) % N 公式【1】
或者
x = (y + M) % N 公式【2】
通过上表的转换，将出列1人后的数据重新组织成了0～（N–2）共N–1个人的列表，继续求N–1个参与人员，按报数到M–1即出列，求解最后一个出列者最初在圆形队列中的编号。
看出什么规律没有？通过一次处理，将问题的规模缩小了。即对于N个人报数的问题，可以分解为先求解（N–1）个人报数的子问题；而对于（N–1）个人报数的子问题，又可分解为先求[(N-1)-1]个人报数的子问题，……。
问题中的规模最小时是什么情况？就是只有1个人时（N=1），报数到（M–1）的人出列，这时最后出列的是谁？当然只有编号为0这个人。因此，可设有以下函数：
F(1) = 0
那么，当N=2，报数到（M–1）的人出列，最后出列的人是谁？应该是只有一个人报数时得到的最后出列的序号加上M，因为报到M-1的人已出列，只有2个人，则另一个出列的就是最后出列者，利用公式【2】，可表示为以下形式：
F(2) = [F(1) + M] % N = [F(1) + M] % 2
比如，N=2, M=3时，有F(2) = [F(1) + M]%N = (0 + 3)%2 = 1
根据上面的推导过程，可以很容易推导出，当N=3时的公式：
F(3) = [F(2) + M] % N = [F(2) + M] % 3
于是，咱们可以得到递推公式：
F(1) = 0
F(N) = [F(N - 1) + M] % N (N>1)
有了此递推公式，可使用递归方法来设计程序：
#include <iostream>
using namespace std;
int josephus(int n, int m)
{
if(1 == n)
{
return 0;
}
return (josephus(n - 1, m) + m) % n;
}
int main()
{
int n, m;
cin >> n >> m;
cout << "最后出列的人的编号为（从0开始编号）：" << josephus(n, m) << endl;
return 0;
}
运行结果：
13 3
最后出列的人的编号为（从0开始编号）：12
使用递归函数会占用计算机较多的内存，当递归层次太深时可能导致程序不能执行，比如64层的汉诺塔需要计算很长的时间。
因此，这里可以将程序直接编写为以下的递推形式：
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int out = 0;
for(int i = 2; i <= n; i++)
{
out = (out + m) % i;
}
cout << "最后出列的人的编号为（从0开始编号）：" << out << endl;
return 0;
}
TopCoder & Codeforces & AtCoder交流QQ群：648202993
更多内容请关注微信公众号
wechat_public.jpg
