约瑟夫环(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: %dn", p1->data);   // 打印所要删除结点的数据        free(p1);                      // 删除结点,从内存释放该结点占用的内存空间        p1 = p2->next;      // p1指针指向新的结点p2->next,即原先的p1->next    }    printf("The last one is No.%dn", p1->data);}int main(){    int total, from, count;    scanf("%d%d%d", &total, &from, &count);    JOSEPHUS(total, from, count);    return 0;}

运行结果:

13 1 3Delete number: 3Delete number: 6Delete number: 9Delete number: 12Delete number: 2Delete number: 7Delete number: 11Delete number: 4Delete number: 10Delete number: 5Delete number: 1Delete number: 8The 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:%dn", i);                    outCnt++;                    flag[i] = 0;    // 已出列的人标记为0                    numoff = 0;     // 从头开始报数                }            }        }    }    for(i = 1; i <= n; i++)    {        if(1 == flag[i])        {            printf("The last one is: %dn", i);        }    }    return 0;}

运行结果:

13 3Dequeue:3Dequeue:6Dequeue:9Dequeue:12Dequeue:2Dequeue:7Dequeue:11Dequeue:4Dequeue:10Dequeue:5Dequeue:1Dequeue:8The 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-20 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) = 0F(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;}