C++實現約瑟夫環

編號是1,2,……,n 的n 個人按照順時針方向圍坐一圈,每個人只有一個密碼(正整數)。一開始任選一個正整數作為報數上限值m,從第一個仍開始順時針方向自1 開始順序報數,報到m 時停止報數。報m 的人出列,將他的密碼作為新的m 值,從他在順時針方向的下一個人開始重新從1 報數,如此下去,直到所有人全部出列為止。

1. 利用單向循環鏈表存儲結構模擬此過程,按照出列順序輸出各個人的號。

2. 測試數據：m 的初值為20,n=7,7 個人的密碼依次為3,1,7,2,4,7,4,首先m=6,則正確的輸出是什麼？

3. 輸入數據：建立輸入函數處理輸入的數據,輸入m 的初值n,輸入每個人的密碼,建立單向循環鏈表。

4.輸出形式：建立一個輸出函數,將正確的出列順序輸出。

程序源代碼

#include<iostream>
#include<cstdlib>

using namespace std;

struct PNode{        //成員結構體
    int num;          //成員編號
    int password;      //成員密碼
    PNode *next;
};

int main()
{
    PNode *head, *end, *ptemp;        //head，end為兩個工作指針，head保存第一個結點，end向後創建鏈表最後一個結點的next為head，ptemp保存要刪除的結點
    int people_num, password_temp, *pass_word;  //人數，臨時m，每個人的password 數組
    cout << "請輸入人數和m的初值：";
    cin >> people_num >> password_temp;
    pass_word = new int[people_num];      //申請password 數組
    cout << "請依次輸入" << people_num << "個人的密碼：";
    for (int i = 0; i < people_num; i++)
    {
        cin >> pass_word[i];
    }
    head = end = new PNode;  //創建第一個結點，
    head->num = 1;
    head->password = pass_word[0];
    for (int i = 1; i < people_num; i++)  //將密碼數組中的密碼賦值給循環鏈表中
    {
        end->next = new PNode;
        end = end->next;
        end->num = i + 1;
        end->password = pass_word[i];
    }
    end->next = head;    //鏈接成循環隊列
    cout << "人員退出序列：" << endl;
    cout << "編號：" << '\t' << "密碼：" << endl;
    while (people_num)
    {
        for (int i = 1; i < password_temp; i++)
        {
            end = end->next;
        }
        ptemp = end->next;
        password_temp = ptemp->password;
        end->next = ptemp->next;
        cout << ptemp->num <<'\t'<< ptemp->password << endl;
        delete ptemp;
        people_num--;
    }
    cout << endl;
    system("pause");
    return 0;
}