线性表的基本应用(四):用循环链表模拟约瑟夫(Josephus)环问题

要求:

已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。要求输出出列的过程和最后一个人的编号。

思路:

该问题为古希腊著名史学家约瑟夫(Josephus)提出的问题演变而来,通常被称为约瑟夫环问题。若用循环链表来模拟,需要使用n个结点存储每个人的编号,由第一个结点开始循环遍历每个结点,且在遍历时同时计数。当计数到m时,打印访问结点的信息并将访问结点删除后继续循环遍历,直到链表仅剩余最后一个结点时结束。最后打印剩余结点信息。

#include <bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int num; //num为约瑟夫环中每个人初始的编号
    struct Node * pNext;
}NODE,*PNODE;

class Josephus //Josephus类创建了一个不包含头结点的循环链表
{
public:
    Josephus(int n,int m); //构造函数中,n为约瑟夫环的初始长度,报到m的人出列
    void start();
private:
    PNODE pHead;
    PNODE pTail;
    int n; //在这里,n为约瑟夫环当前的长度,当n=1时,程序终止
    int m; //报到m的人出列
};

Josephus::Josephus(int n,int m)
{
    PNODE p;
    pHead = pTail = new Node();
    pHead->num = 1;
    pTail->pNext = pHead;
    for (int i = 2; i<=n; i++)
    {
        p = new Node();
        p->num = i;
        pTail->pNext = p;
        pTail = p;
        pTail->pNext = NULL;
    }
    pTail->pNext = pHead;
    this->n = n;
    this->m = m;
}

void Josephus::start()
{
    PNODE p = pTail;
    PNODE q = pHead;
    for (int i = 1; ; i++)
    {
        if (this->n == 1) //当n=1时,终止遍历
        {
            printf("\n最终留下的是%d号!\n",q->num);
            break;
        }
        if (i == this->m) //当计数到第m个结点时,删除该结点继续遍历
        {
            printf("%d",q->num);
            if(n>2)
                printf("-");
            p->pNext = q->pNext;
            delete q;
            q = p->pNext;
            i = 1;
            n--;
        }
        p=p->pNext;
        q=q->pNext;
    }
}

int main()
{
    Josephus j(41,3);
    j.start();
    return 0;
}

运行结果如下图所示:

发表评论

电子邮件地址不会被公开。 必填项已用*标注