數(shù)據(jù)結(jié)構(gòu)總結(jié)系列（三）——循環(huán)鏈表之約瑟夫問題

印度阿三17 2019-06-01

展開全文

約瑟夫問題簡介：

約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數(shù)，第M個將被殺掉，最后剩下一個，其余人都將被殺掉。例如N=6，M=5，被殺掉的順序是：5，4，6，2，3，1。分析：（1）由于對于每個人只有死和活兩種狀態(tài)，因此可以用布朗型數(shù)組標(biāo)記每個人的狀態(tài)，可用true表示死，false表示活。（2）開始時每個人都是活的，所以數(shù)組初值全部賦為false。（3）模擬殺人過程，直到所有人都被殺死為止。（由于博主懶癌犯了導(dǎo)致隨便截取了某度百科的內(nèi)容，或許更新之后會用這種方法呢~~~）

我們現(xiàn)在確定了使用循環(huán)鏈表，那么就開始定義：

由于循環(huán)鏈表尾部指針指向頭部，所以循環(huán)鏈表的定義和單鏈表一致，只有表示時有些許差別。

show?code：

typedef struct node
{
    int data;
    struct node *next;//指向下一個節(jié)點
}LinkNode;

typedef LinkNode *RollList;//重定義了循環(huán)鏈表的頭節(jié)點

插入：

void Creat(RollList &R,int length)
{
    RollList tmp=R;//這里修改了tmp，避免直接對頭結(jié)點修改
    for(int i=2;i<=length;i  )//由于確定了每個節(jié)點的數(shù)據(jù)，單獨(dú)將第一個節(jié)點拿出來定義
    {
        LinkNode *L=new LinkNode;
        L->data=i;
        L->next=R;
        tmp->next=L;//這里的插入也很簡單
        tmp=tmp->next;
    }
}

Kill的函數(shù)：

void Kill(RollList &R,int m,int length)
{
    RollList tmp=R;
    for(int i=1;i<=length-1;i  )//循環(huán)n-1次。
    {
        for(int j=1;j<=m-2;j  )//這里首先走到要刪除節(jié)點的前一個節(jié)點
        {
            tmp=tmp->next;
        }
        cout << "Kill the " << tmp->next->data << "people " << endl;
        tmp->next=tmp->next->next;//這里對指針進(jìn)行修改（直接跳過了刪除節(jié)點）
        tmp=tmp->next;
    }
    cout << endl;
    cout << "Survive people :" << endl;
    cout << tmp->data << endl;
}

那么，我們的約瑟夫問題已經(jīng)可以求解了：

直接上代碼：

#include <bits/stdc  .h>

using namespace std;

int arr[200];

typedef struct node
{
    int data;
    struct node *next;//指向下一個節(jié)點
}LinkNode;

typedef LinkNode *RollList;//重定義了循環(huán)鏈表的頭節(jié)點

void Creat(RollList &R,int length)
{
    RollList tmp=R;//這里修改了tmp，避免直接對頭結(jié)點修改
    for(int i=2;i<=length;i  )//由于確定了每個節(jié)點的數(shù)據(jù)，單獨(dú)將第一個節(jié)點拿出來定義
    {
        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  )//循環(huán)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  )//循環(huán)n-1次。
    {
        for(int j=1;j<=m-2;j  )//這里首先走到要刪除節(jié)點的前一個節(jié)點
        {
            tmp=tmp->next;
        }
        cout << "Kill the " << tmp->next->data << "people " << endl;
        tmp->next=tmp->next->next;//這里對指針進(jìn)行修改（直接跳過了刪除節(jié)點）
        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;
}

不得不說（快排牛皮！?。。。?/p>