循环链表应用——约瑟夫置换

约瑟夫问题

介绍

约瑟夫问题,又称约瑟夫置换丢手绢问题

一般形式

(本部分内容来自百度百科

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

代码

问题描述

本文以以下问题为例

编号为1-10的10 个人围成一圈,从第一个开始报数,第9个被淘汰出圈,剩下的组成新的圈。依次这样下去,求最后一个人的编号

解决

注意:该段代码与上篇文章——《 循环链表定义及操作 》相接

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
//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;

if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}

if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}

do{

i += interval;

//找查第i个结点,p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;

}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;

cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空,继续报数

cout << "最后一个出圈者的编号" << num << endl;

return true;
}

完整代码

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <string>

using namespace std;


typedef struct _LinkNode
{
int data;
struct _LinkNode *next;
}LinkList;

bool InitList(LinkList* &L)
{
L = new LinkList;

if(!L) return false;

L->next = L;
L->data = 0;

return true;
}

bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkList *last = NULL;
if(!L || !node) return false;

if(L == L->next)
{
//头结点指针指向了自己(链表只有头结点)
node->next = L;
L->next = node;
}else{
//非空的循环链表
last = L->next;
//寻找尾结点(指向头结点的结点)
while(last->next != L)
{
last = last->next;
}

node->next = L;
last->next = node;
}
return true;
}

void LinkListPrint(LinkList *L)
{
LinkList *p;
if(!L || L == L->next)
{
cout << "链表为空\n";
return;
}

p = L->next;

while(p != L)
{
cout << p->data << "\t";
p = p->next;
}


cout << endl;
}

//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;

if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}

if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}

do{

i += interval;

//找查第i个结点,p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;

}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;

cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空,继续报数

cout << "最后一个出圈者的编号" << num << endl;

return true;
}

int main()
{
LinkList *L, *s;
int i = 0;
if(InitList(L))
{
cout << "创建一个空的循环链表\n";
}else{
exit(-1);
}

cout << "尾插10个元素...\n";

while((++i)<=10)
{
s = new LinkList;
s->data = i;
s->next = NULL;
if(ListInsert_back(L, s))
{
cout << "success\n";
}else{cout << "default\n";}
}

LinkListPrint(L);

Joseph(L,9);

return 0;

}

输出结果

注:0为头结点的数据,该结点并不计入约瑟夫环中(但最后也将其删除销毁链表释放内存)

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
创建一个空的循环链表
尾插10个元素...
success
success
success
success
success
success
success
success
success
success
1 2 3 4 5 6 7 8 9 10
当前结点:9 上一个结点:8 下一个结点:10
1 2 3 4 5 6 7 8 10
当前结点:8 上一个结点:7 下一个结点:10
1 2 3 4 5 6 7 10
当前结点:10 上一个结点:7 下一个结点:0
1 2 3 4 5 6 7
当前结点:2 上一个结点:1 下一个结点:3
1 3 4 5 6 7
当前结点:5 上一个结点:4 下一个结点:6
1 3 4 6 7
当前结点:3 上一个结点:1 下一个结点:4
1 4 6 7
当前结点:4 上一个结点:1 下一个结点:6
1 6 7
当前结点:1 上一个结点:0 下一个结点:6
6 7
当前结点:6 上一个结点:0 下一个结点:7
7
当前结点:7 上一个结点:0 下一个结点:0
链表为空
最后一个出圈者的编号7

循环链表应用——约瑟夫置换

https://cairbin.top/2021/09/18/Joseph/

作者

CairBin

发布于

2021-09-18

更新于

2021-09-18

许可协议

评论