数据结构总结系列（三）——循环链表之约瑟夫问题

叁歲伎倆 2021-11-01 14:16 269阅读 0赞

约瑟夫问题简介：

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

分析：

（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。

（2）开始时每个人都是活的，所以数组初值全部赋为false。

（3）模拟杀人过程，直到所有人都被杀死为止。

（由于博主懒癌犯了导致随便截取了某度百科的内容，或许更新之后会用这种方法呢~~~）

![1606266-20190601130649402-1045206466.png][]

我们现在确定了使用循环链表，那么就开始定义：

由于循环链表尾部指针指向头部，所以循环链表的定义和单链表一致，只有表示时有些许差别。

show code：

typedef struct node
    {
        int data;
        struct node *next;//指向下一个节点
    }LinkNode;
    
    typedef LinkNode *RollList;//重定义了循环链表的头节点

插入：

void Creat(RollList &R,int length)
    {
        RollList tmp=R;//这里修改了tmp，避免直接对头结点修改
        for(int i=2;i<=length;i++)//由于确定了每个节点的数据，单独将第一个节点拿出来定义
        {
            LinkNode *L=new LinkNode;
            L->data=i;
            L->next=R;
            tmp->next=L;//这里的插入也很简单
            tmp=tmp->next;
        }
    }

Kill的函数：

void Kill(RollList &R,int m,int length)
    {
        RollList tmp=R;
        for(int i=1;i<=length-1;i++)//循环n-1次。
        {
            for(int j=1;j<=m-2;j++)//这里首先走到要删除节点的前一个节点
            {
                tmp=tmp->next;
            }
            cout << "Kill the " << tmp->next->data << "people " << endl;
            tmp->next=tmp->next->next;//这里对指针进行修改（直接跳过了删除节点）
            tmp=tmp->next;
        }
        cout << endl;
        cout << "Survive people :" << endl;
        cout << tmp->data << endl;
    }

那么，我们的约瑟夫问题已经可以求解了：

直接上代码：

#include <bits/stdc++.h>
    
    using namespace std;
    
    int arr[200];
    
    typedef struct node
    {
        int data;
        struct node *next;//指向下一个节点
    }LinkNode;
    
    typedef LinkNode *RollList;//重定义了循环链表的头节点
    
    void Creat(RollList &R,int length)
    {
        RollList tmp=R;//这里修改了tmp，避免直接对头结点修改
        for(int i=2;i<=length;i++)//由于确定了每个节点的数据，单独将第一个节点拿出来定义
        {
            LinkNode *L=new LinkNode;
            L->data=i;
            L->next=R;
            tmp->next=L;//这里的插入也很简单
            tmp=tmp->next;
        }
    }
    
    
    //下面的注释代表了另一种显示存活的人的方法（快排是真的牛皮）
    /*void Kill(RollList &R,int m,int length,int arr[])
    {
        RollList tmp=R;
        for(int i=1;i<=length-1;i++)//循环n-1次。
        {
            for(int j=1;j<=m-2;j++)
            {
                tmp=tmp->next;
            }
            cout << "Kill the " << tmp->next->data << "people " << endl;
            arr[i]=tmp->next->data;
            tmp->next=tmp->next->next;
            tmp=tmp->next;
        }
    }*/
    
    void Kill(RollList &R,int m,int length)
    {
        RollList tmp=R;
        for(int i=1;i<=length-1;i++)//循环n-1次。
        {
            for(int j=1;j<=m-2;j++)//这里首先走到要删除节点的前一个节点
            {
                tmp=tmp->next;
            }
            cout << "Kill the " << tmp->next->data << "people " << endl;
            tmp->next=tmp->next->next;//这里对指针进行修改（直接跳过了删除节点）
            tmp=tmp->next;
        }
        cout << endl;
        cout << "Survive people :" << endl;
        cout << tmp->data << endl;
    }
    
    int main()
    {
        RollList R=new LinkNode;
        R->data=1;
        R->next=R;
        int length,m;
        cout << "input people :" << endl;
        cin >> length;
        Creat(R,length);
        cout << "input death :" << endl;
        cin >> m;
        cout << endl;
        /*Kill(R,m,length,arr);
        cout << "Survive people :" << endl;
        sort(arr,arr+length);
        for(int i=1;i<=length-1;i++)
        {
            if(arr[i]!=i)
            {
                cout << i << endl;
                break;
            }
        }*/
        Kill(R,m,length);
        return 0;
    }

不得不说（快排牛皮！！！！）

![1606266-20190601132223208-1046537658.png][]

偷偷说一下（或许之后会有另一种方法求解约瑟夫问题，但是懒癌博主不知何时会更新，不过快放假了呢~~）

转载于:https://www.cnblogs.com/ever17/p/10959304.html

[1606266-20190601130649402-1045206466.png]: /images/20211101/e3ac6654e4e547ddbfdbe2935c9808b1.png
[1606266-20190601132223208-1046537658.png]: /images/20211101/9b48786983794de0a2d936fc834da29b.png