約瑟夫環(huán)問題（帶密碼）

編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針方向圍坐一圈，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m 值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。例如，n=7,7個(gè)人的密碼依次為：3,1,7,2,4,8,4,m的初值取6，則正確的出列順序應(yīng)為6,1,4,7,2,3,5

分析

約瑟夫環(huán)的大小是變化的，因此相應(yīng)的結(jié)點(diǎn)也是變化的，使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以動(dòng)態(tài)的生成其中的結(jié)點(diǎn)，出列操作也非常簡(jiǎn)單。用單向循環(huán)鏈表模擬其出列順序比較合適

解決

用結(jié)構(gòu)指針描述每個(gè)人

struct Joseph {//約瑟夫環(huán)中某個(gè)人的序號(hào)int number;//約瑟夫環(huán)中某個(gè)人的密碼int password;//約瑟夫環(huán)的下一個(gè)節(jié)點(diǎn)struct Joseph *next; };

初始化約瑟夫環(huán)

Node *init(int n, int array[]) {int i = 1;//鏈表頭結(jié)點(diǎn)Node *head;//鏈表當(dāng)前節(jié)點(diǎn)Node *current;//鏈表下一個(gè)節(jié)點(diǎn)Node *next;current = static_cast<Node *>(malloc(sizeof(Node)));current->number = i;current->password = array[i - 1];head = current;for (i = 2; i <= n; ++i) {next = static_cast<Node *>(malloc(sizeof(Node)));next->number = i;next->password = array[i - 1];//連接鏈表與新創(chuàng)建的節(jié)點(diǎn)current->next = next;current = next;}//尾節(jié)點(diǎn)連接到頭結(jié)點(diǎn)，形成循環(huán)鏈表current->next = head;return head; }

報(bào)數(shù)出列

void function(Node *head, int len, int password) {//前一個(gè)節(jié)點(diǎn)Node *pre;//后一個(gè)節(jié)點(diǎn)Node *next;//要?jiǎng)h除的節(jié)點(diǎn)Node *temp;//初始化next = head;for (int i = 1; i < len; ++i) {pre = next->next;next = next->next;}//遍歷所有人for (int i = 1; i <= len; ++i) {//先將指針移動(dòng)到出列的前一個(gè)for (int j = 1; j < password; ++j) {pre = pre->next;}//保存要?jiǎng)h除的節(jié)點(diǎn)temp = pre->next;//下一個(gè)節(jié)點(diǎn)next = temp->next;//修改密碼password = temp->password;//輸出出列序號(hào)cout << temp->number << endl;//連接鏈表，去除中間節(jié)點(diǎn)pre->next = next;//釋放中間節(jié)點(diǎn)free(temp);} }

完整代碼

#include <iostream>using namespace std;struct Joseph {//約瑟夫環(huán)中某個(gè)人的序號(hào)int number;//約瑟夫環(huán)中某個(gè)人的密碼int password;//約瑟夫環(huán)的下一個(gè)節(jié)點(diǎn)struct Joseph *next; };typedef Joseph Node;/*** 初始化約瑟夫環(huán)* @param n 成員數(shù)目* @param array 每個(gè)人的密碼* @return 頭結(jié)點(diǎn)*/ Node *init(int n, int array[]) {int i = 1;//鏈表頭結(jié)點(diǎn)Node *head;//鏈表當(dāng)前節(jié)點(diǎn)Node *current;//鏈表下一個(gè)節(jié)點(diǎn)Node *next;current = static_cast<Node *>(malloc(sizeof(Node)));current->number = i;current->password = array[i - 1];head = current;for (i = 2; i <= n; ++i) {next = static_cast<Node *>(malloc(sizeof(Node)));next->number = i;next->password = array[i - 1];//連接鏈表與新創(chuàng)建的節(jié)點(diǎn)current->next = next;current = next;}//尾節(jié)點(diǎn)連接到頭結(jié)點(diǎn)，形成循環(huán)鏈表current->next = head;return head; }/*** 遍歷約瑟夫環(huán)，報(bào)數(shù)出列* @param head 頭結(jié)點(diǎn)* @param len 約瑟夫環(huán)長(zhǎng)度* @param password 初始密碼*/ void function(Node *head, int len, int password) {//前一個(gè)節(jié)點(diǎn)Node *pre;//后一個(gè)節(jié)點(diǎn)Node *next;//要?jiǎng)h除的節(jié)點(diǎn)Node *temp;//初始化next = head;for (int i = 1; i < len; ++i) {pre = next->next;next = next->next;}//遍歷所有人for (int i = 1; i <= len; ++i) {//先將指針移動(dòng)到出列的前一個(gè)for (int j = 1; j < password; ++j) {pre = pre->next;}//保存要?jiǎng)h除的節(jié)點(diǎn)temp = pre->next;//下一個(gè)節(jié)點(diǎn)next = temp->next;//修改密碼password = temp->password;//輸出出列序號(hào)cout << temp->number << endl;//連接鏈表，去除中間節(jié)點(diǎn)pre->next = next;//釋放中間節(jié)點(diǎn)free(temp);} }int main() {//環(huán)的長(zhǎng)度int len;cout << "輸入約瑟夫環(huán)的長(zhǎng)度：";cin >> len;int array[len];cout << "請(qǐng)輸入m的初始值 m:";int m;cin >> m;cout << "請(qǐng)輸入每個(gè)人的密碼: " << endl;for (int i = 0; i < len; ++i) {cin >> array[i];} // int len = 7; // int array[] = {3, 1, 7, 2, 4, 8, 4}; // int m = 6;//創(chuàng)建約瑟夫環(huán)Node *head = init(len, array);function(head, len, m);return 0; }

總結(jié)

以上是生活随笔為你收集整理的约瑟夫环问题（带密码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。