約瑟夫環(huán)（約瑟夫問題）是一個數學的應用問題：已知 n 個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。. 從編號為 k 的人開始報數，數到 m 的那個人出圈；他的下一個人又從 1 開始報數，數到 m 的那個人又出圈；依此規(guī)律重復下去，直到剩余最后一個勝利者。. 例如：有10個人圍成一圈進行此游戲，每個人編號為 1-10 。. 若規(guī)定數到 3 的人出圈。. 則游戲過程如下。. （1）開始報數，第一個數到 3 的人為 3 號，3 號出圈。. 1， 2， 【 3 】， 4， 5， 6， 7， 8， 9， 10。. （2）從4號重新從1開始計數，則接下來數到3的人為6號，6號出圈。
廢話不多說，直接上代碼：
下面是頭文件，命名為”約瑟夫環(huán).h“
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#ifndef Josephus_circle//判斷是否被定義過Josephus_circle#define Josephus_circle struct Node//定義一個結構體，用來表示每一個結點 { int data;//表示每一個結點的數字，也就是序號 Node* next;//定義一個結構體指針，用來指向后一個結點}; class Josephus//定義一個類，里面包含有三個接口，和兩個私有成員變量{public : Josephus(int n);//定義一個構造函數，用來創(chuàng)建一個約瑟夫環(huán) ~Josephus();//析構函數，用以銷毀一個約瑟夫環(huán) void ResultShow(int m);//展示出圈順序private : Node * rear,*first;//定義一個節(jié)點形指針，用來指向最后一個結點};#endif |
下面是接口的具體實現，命名為“約瑟夫環(huán).cpp”
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include<iostream>//引入輸入輸出流#include"約瑟夫環(huán).h"//引入約瑟夫環(huán)頭文件 using namespace std; Josephus::Josephus(int n) { first=rear = new Node;//將頭指針和尾指針指向第一個新建的結點，也就是初始化指針 rear->data = 1;//首先，將第一個結點數據域賦值為1 for (int i = 2; i <= n; i++) //從2開始 { Node* s = new Node;//定義一個Node形指針s，指向新建的一個結點 rear->next = s;//將指向頭結點的尾指針指向下一個結點，也就是s所指的結點 s->data = i;//將新建的結點數字域賦值為i rear = s;//將尾結點移動到新建結點s } rear->next = first;//在循環(huán)過后，將尾結點和頭節(jié)點連接起來，構成循環(huán)鏈表}Josephus::~Josephus(){ if (first!=rear)//判斷環(huán)是否為空 { while (first != rear)//每次循環(huán)都是當頭節(jié)點不等于尾結點時候，開始刪除：…… { Node * p = first;//定義一個新的節(jié)點形指針，指向頭節(jié)點，用作暫存要刪去的結點 first = first->next;//將頭節(jié)點移動到下一個結點 delete p;//刪除之前頭節(jié)點所指向的結點 } delete rear;//在刪除完成后，剩下的最后就只有尾結點了，刪除即可 } else { cout << "約瑟夫環(huán)為空，請先建立新環(huán)！" << endl;//空表提示 }}void Josephus::ResultShow(int m){ cout << "出環(huán)順序為：" << endl; Node * p = first;//定義一個Node類型的p，等于first Node * pre=first,* reserve=nullptr;//定義pre等于first，和一個代替p指針被刪除的結點的指針 int count = 1;//定義一個計數的count使其為一 while (p->next != p)//如果p->next所指向的結點是p的話，表示，這已經是最后一個結點了，該節(jié)點為最后出圈 { if (count < m)//count來計數，每次到了m就出圈對應結點 { pre = p;//將pre等于p，以便于表示p變換前的結點 p = p->next;//p向下一結點移動 count++;//移動一次count加一次 } else//每次count=m時候就開始刪除對應結點 { pre->next = p->next;//首先從環(huán)中摘去要刪除的p所指的結點 reserve = p;//使用reserve來保存被摘去的結點p cout << p->data << "\t";//輸出結點p所數據域，輸出在屏幕上表示p結點的出圈 p = p->next;//p指向下一結點，以便于下一輪的循環(huán) delete reserve;//刪除保存p的reserve所對應的結點 count = 1;//將計數恢復為1，以便下一輪計數 } } cout << p->data << endl;//這最后一個就是最后出圈的結點，也就是所謂的勝利者，最后單獨輸出屏幕 delete p;//輸出最后再刪除這一結點，釋放內存 pre=first=rear=p = NULL;//避免野指針出現使其指向空} |
下面是main函數，命名為“約瑟夫環(huán)_main.cpp”
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<iostream>//引入輸入輸出流#include"約瑟夫環(huán).h"//引入頭文件 using namespace std; //主函數區(qū)域int main() { int m, n; cout << "請輸入約瑟夫環(huán)人數以及密碼\n"; cout << "人數n："; cin >> n; cout << endl << "密碼m："; cin >> m; Josephus L(n);//創(chuàng)建一個約瑟夫環(huán)，環(huán)數為10 L.ResultShow(m);//定義密碼m，輸出出圈順序 return 0;} |
下面是運行截圖：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/qq_56715530/article/details/120990262
