约瑟夫环

Josephus问题的定义如下:假设n个人排成环形,且有以正整数m<=n。从某个制定的人开始,沿环报数,每遇到第m个人就让其出列,且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1,2,…,n的(n, m)-Josephus排列。例如,(7,3)-Josephus排列为<3,6,2,7,5,1,4>。

a)假设m为整数。请描述一个O(n)时间的算法,使之对给定的整数n,输出(n, m)-Josephus排列。
b)假设m不是个常数。请描述一个O(nlgn)时间的算法,使给定的整数n和m,输出(n, m)-Josephus排列。

递归求解约瑟夫环

约瑟夫序列从0,1,2…..,N-1中报数为M-1的出列,从M开始又重新从1开始报数,这可以用典型的递归来求解,递归的具体过程如下图所示:

01

02

不妨用$f(i)$表示问题规模$size=i$的时候,数的下标的排列,值得注意的是,从$size=i$问题规模递减为$size=i-1$的时候,同一个数的下标发生变化,其实是对应函数的映射,不妨用$f(i)$表示这种映射。

如上图所示,在Josephus排列中,满足
$f(i)=(f(i-1)+k)\ mod\ i$

根据这种算法,可以使用递归求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main()
{
int N;
int M;
cin>>N;
cin>>M;
int result=0;
for(int i=2; i<=N;i++)
result=(result+M)%i;
//值得注意的是,这里的i表示规模,递推关系
//表示从i递推到i-1,问题规模数组大小
//最小就为1,所以i的初值为2
std::cout << "最后输出的元素是" <<result+1<<endl;
return 0;
}

递归算法的局限性:用这样的递归算法,无法获得一个Josephus的(n,m)排列,我们只知道最后一个出队的人,在初始时候的下标,并不知道所有的人,分别什么时候出队。

使用循环链表输出

不删除结点的时候,我们需要给每一个节点加上status属性,判断这个结点是否已经处理过?
或者就采用最普通的删除结点的方式来处理。每当完成报数的时候,删除节点让报数的人退出Josephus环。

这里给出两种实现函数,XXX_stus用status属性判断是否出队,但不删除节点,不带_stus的函数每隔m删除一个人。

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <iostream>
using namespace std;
#define n 30
#define m 3
#define LEN sizeof(struct circular_list)
#define LEN_status sizeof(struct circular_list_status)
struct circular_list
{
int key; //存储数据
circular_list *next;
};
struct circular_list_status
{
int key;
bool status; //用来存储该节点的状态,出队没有?
circular_list_status *next;
circular_list(int k,circular_list *init):key(k),status(TRUE),next(init){}
};
struct circular_list *tail=NULL;
struct circular_list_status *tail_status=NULL;
circular_list *insert(circular_list *head, int k)
{
circular_list *z=new circular_list[LEN];
z->key=k;
if(head==NULL)
{
head=tail=z;
head->next=tail; //自循环
}
else
{
//插入表尾
tail->next=z;
z->next=head;
tail=z;
}
return head;
}
circular_list_status *insert_stus(circular_list_status *head,int k)
{
circular_list_status *z=new circular_list_status[LEN_status];
z->key=k;
z->status=TRUE;
if(head==NULL)
{
head=tail=z;
head->next=tail; //自循环
}
else
{
//插入表尾
tail->next=z;
z->next=head;
tail=z;
}
return head;
}
circular_list *delete(circular_list *head, circular_list *z)
{
circular_list *p=head;
//先是要寻找到z这个结点的位置
while(p->next!=z) //要删除的是p->next这个节点
p=p->next;
if(head==tail)
p->next=NULL;
else
{
if(p->next==head)
head=p->next->next;
else if(p->next==tail)
tail=p;
p->next=p->next->next;
}
return p->next;
}
circular_list_status *delete_stus(circular_list_status *head, circular_list_status *z)
{
circular_list_status *p=head;
while(p->next!=z) //要删除的是p->next这个节点
p=p->next;
if(head==tail)
p->next=NULL;
else
{
if(p->next==head)
head=p->next->next;
else if(p->next==tail)
tail=p;
p->next=p->next->next;
}
return p->next; //返回的值,是更新后的p->next
}
void Josephus_n_m(circular_list_status *head, int n,int m)
{
struct circular_list_status *p=head;
//p作为遍历指针
int count=0;
while(p && count<=n)
{
int i=0;
while(i!=m-1)
{
if(p->status==TRUE)
{
p=p->next;
i++;
}
else p=p->next;
}
//循环到最后,i报数报M-1
p->status=false;
count++;
p=p->next;
}
}
void Josephus_link_imple(circular_list *head,int m)
{
circular_list *p=head;
while(p)
{
int i=0;
while(i!=m-1)
{
p=p->next;
i++;
}
circular_list *z=p;
cout<<z->key<<" ";
p=delete(head,z);
}
}
int main()
{
int a[n]={0}
for(int i=0;i<n;i++)
a[i]=i+1;
int j=0;
circular_list *head=NULL;
while(j!=n)
{
head=insert(head,a[j]);
j++;
}
circular_list *p=head;
do {
cout<<p->key;
p=p->next;
/* code */
} while(p!=head);
cout<<endl;
Josephus_link_imple(head,m);
}

算法分析:时间复杂度是$O(mn)=O(n)$

是两个循环的嵌套,在m值不大的情况下可以使用该算法实现。

使用顺序统计树实现

假设m不是一个常数,用$O(nlgn)$的算法实现

这里采用顺序统计树来存储Josephus环中的点,通过映射关系查找每次需要删除的节点的坐标并执行删除。
映射关系如下图所示:

03

相关的递推表示为:

主要的实现函数

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
void Josephus_imple(os_tree *T, int m, int n)
{
os_node *x=T->root;
int k=0, i=n;
int t=1;
while(T->root!=NULL && i>0)
{
k=(t+m-1)%i;
//k就是我们需要删除的点,注意到我们对一个点执行删除之后
//这个点原来的下标是k,删除了之后k+1就自动补到k的位置上
//这样新的k重新编号的话就是1,相当于原来的t=1
if(k==0)
k=i;
os_node *del=os_select(T,k);
//这里del表示要删除的结点
cout<<del->key<<" ";
//输出节点
RB_delete(del);
t=k;
i--;
}
}

这里采用的数据结构是一种顺序统计量,能够计算出rank值。但值得注意的是,在顺序统计量中,计算一个节点的rank值的函数的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Interative_os_rank(os_tree *T,os_node *x)
//确定x这个节点的顺序统计树的rank
{
int r=x->left->size+1;
os_node *y=x; //沿左脊柱上升,r=x->left->size+1
while(y!=T->root) //如果是沿着右脊柱上升?y->size=y->left->size+1+sum{y->parent->size}
{ //沿左脊柱上升,r保持不变;一旦拐弯到了右脊柱,要关注y->parent->left->size+1
if(y==y->parent->right)
r=r+y->parent->left->size+1;
y=y->parent;
//不管是左脊柱还是右脊柱,都要沿树上升
}
return r;
}

特别说明,当函数沿左脊柱上升的时候,r的值是r=x->left->size+1,但是,沿右脊柱,情形就变成了r=r+y->parent->left->size+1,具体的说明请看下图:

04

**

$O(lgn)$算法的实现

os_tree.h

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
#define RED 0
#define BLACK 1
#define NIL -1
#define LEN sizeof(struct os_node)
#define LENTREE sizeof(struct os_tree)
struct os_node
{
os_node *left;
os_node *right;
os_node *parent;
int key;
int color;
int size; //用于顺序统计量
os_node(os_node *init,int num)
:left(init),right(init),parent(init),key(num),color(RED),size(0){}
};
struct os_tree
{
os_node *root;
os_node *nil;
os_tree()
{
nil=new os_node(NULL,NIL);
root=nil;
}
};

rotate.h

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
#include "os_tree.h"
void left_rotate(os_tree *T,os_node *x)
{
os_node *y=x->right; //左孩子结点
x->right=y->left;
//这一部处理的是加在x,y之间的“内结点”,y->left原先
//夹在x->left和y->right之间,旋转之后子树的相对顺序不变,最外边的结点是
//x->left和y->right,注意是围绕x和y进行的旋转,所以子树的相对位置保持不变
if(y!=T->nil && y->left!=T->nil)
y->left->parent=x;
//旋转之后需要重新更新parent结点信息
y->parent=x->parent; //这个时候y作为子树的根了,y要连到祖先中!
if(x->parent==T->nil)
T->root=y;
else if(x->parent->left==x)
x->parent->left=y;
else
x->parent->right=y;
//保证x与祖先结点相连接
//最后处理x和y的关系
y->left=x;
x->parent=y;
//顺序统计树新增部分
y->size=x->size;
//旋转之后,y代替原来x的位置,而x的位置在树的高处
//直接将原来x的size值赋值给y就可以了
x->size=x->left->size+x->right->size+1;
}
//右旋,对称的代码
void right_rotate(os_tree *T,os_node *x)
{
//只需要把上述代码的相对位置,right和left互换就可以了
os_node *y=x->left;
x->left=y->right;
if(y!=T->nil && y->right!=T->nil)
y->right->parent=x;
//旋转之后需要重新更新parent结点信息
y->parent=x->parent;
if(x->parent==T->nil)
T->root=y;
else if(x->parent->left==x)
x->parent->left=y;
else
x->parent->right=y;
//保证x与祖先结点相连接
//最后处理x和y的关系
y->right=x;
x->parent=y;
y->size=x->size;
x->size=x>left->size+x->right->size;
}

delete.h

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include "os_tree.h"
#include "rotate.h"
#include "succ_and_other.h"
//删除调整,这个时候x有两重黑色
void RB_delete_fixup(os_tree *T, os_node *x)
{
os_node *w=T->nil;
while (x!=T->root && x->color==BLACK)
{
if(x==x->parent->left)
{
w=x->parent->right; //w为x的兄弟结点
if(w->color==RED)
{
w->color=BLACK; //将这种情况划归为下面一种情况
w->parent->color=RED;
left_rotate(T,x->parent);
w=x->parent->right;
}
if(w->left->color==BLACK && w->right->color==BLACK)
{
w->color=RED;
x=x->parent; //x和w的黑色沿树上升,注意到x有双重黑色,所以x的颜色不变
} //变得是w,x->parent的颜色
else
{
if(w->right->color==BLACK)
{
w->left->color=BLACK;
w->color=RED; //同样,内节点变为外节点
right_rotate(T,w);
w=x->parent->right;
}
w->color=x->parent->color; //这里x->parent的颜色不确定,但是w的颜色是黑色
//x有双重黑色,通过改变颜色加上旋转,可以将双重黑色表现在图中,这样完成了红黑树的局部平衡
x->parent->color=BLACK;
w->right->color=BLACK;
left_rotate(T,x->parent);
//红黑树局部平衡了
x=T->root;
}
}
else
{
w=x->parent->left;
if(w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
right_rotate(T,x->parent);
w=x->parent->left;
}
}
if(w->left->color==BLACK && w->right->color==BLACK)
{
w->color=RED;
x=x->parent;
}
else
{
if(w->left->color==BLACK)
{
w->right->color=BLACK;
w->color=RED;
left_rotate(T,w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=BLACK;
w->left->color=BLACK;
right_rotate(T,x->parent);
x=T->root;
}
}
x->color=BLACK;
}
void transplant(os_tree *T, os_node *u, os_node *v)
{
if(u->parent==T->nil)
T->root=v;
else if(u==u->parent->left)
u->parent->left=v;
else u->parent->right=v;
if(v!=T->nil)
v->parent=u->parent;
}
void RB_delete(os_tree *T, os_node *z)
{
os_node *y=z, *x;
int y_original_color=y->color;
os_node *par=z->parent; //par作为被删除节点的双亲
if(z->left==T->nil)
{
//删除一个节点的时候,size会发生变化
while(par!=T->nil)
{
//删除节点后,z的双亲的size值会减小
par->size--;
par=par->parent; //自底向上遍历,所有的节点的size都减小
}
x=z->right;
transplant(T,z,z->right);
}
else if(z->right==T->nil)
{
while(par!=T->nil)
{
//删除节点后,z的双亲的size值会减小
par->size--;
par=par->parent; //自底向上遍历,所有的节点的size都减小
}
x=z->left;
transplant(T,z,z->left);
}
else
{
y=tree_minimum(T,z->right); //这里是查找z的后继,为y,用y来代替z的位置
y_original_color=y->color;
os_node *par=y->parent;
//这里用y嫁接到z处,原先y位置往上所有的节点相当于
//少了一个y结点,所以par往上遍历的过程中所有的size都为size--
//特别地,当用y来代替z的时候,并不是y->size=z->size
//因为子树中少了一个y,所以size-1
//特别注意,实际上,从y结点到z节点之间的节点,少了一个y
//从z节点往上,少了一个z,由于size结点是不包括当前节点的
//所以y->size=z->size-1
/*y->size=z->size-1;
while(par!=T->nil)
{
//删除节点后,z的双亲的size值会减小
par->size--;
par=par->parent; //自底向上遍历,所有的节点的size都减小
}*/
//还有一种方法:完成transplant之后自底向上调整!
x=y->right;
if(y->parent==z)
{
x->parent=y;
}
else
{
transplant(T,y,y->right);
y->right=z->right;
y->right->parent=y;
}
transplant(T,z,y);
y->left=z->left;
y->left->parent=y;
y->color=z->color;
//这里进行size属性的维护
while(par!=T->nil)
{
//删除节点后,z的双亲的size值会减小
par->size--;
par=par->parent; //自底向上遍历,所有的节点的size都减小
}
}
if(y_original_color==BLACK)
RB_delete_fixup(T,x); //x为y的孩子结点,y的删除会影响x的相关性质
}

insert.h

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
#include "os_tree.h"
#include "rotate.h"
void RB_insert_fixup(os_tree *T, os_node *z);
void RB_insert(os_tree *T, os_node *z)
{
os_node *y=T->nil;
//y作为遍历指针的双亲
RB_node *x=T->root;
while(x!=T->nil)
{
y=x;
if(z->key<x->key)
x->x->left;
else x=x->right;
}
z->parent=y;
//y作为遍历指针x的母结点,x遍历寻找合适的插入位置
if(y==T->nil)
T->root=z;
else if(z->key<y->key)
y->left=z;
else y->right=z;
z->left=T->nil;
z->right=T->nil;
z->parent=RED;
//新插入节点的信息
z->size=1;
z->left->size=0;
z->right->size=0;
RB_insert_fixup(T,z); //最后插入的结点是红色的,与此同时进行红黑树性质的调整
}
void RB_insert_fixup(os_tree *T,os_node *z)
{
while(z->parent->color==RED)
{
if(z->parent==z->parent->parent->left)
{
os_node *y=z->parent->parent->right; //设置叔结点
if(y->color==RED)
{
z->parent->color=BLACK; //父节点的黑色可以下放给两个结点
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent; //z沿树上升
}
else
{
if(z==z->parent->right) //内结点先旋转成外节点
{
z=z->parent;
left_rotate(T,z);
}
z->parent->color=BLACK; //改变颜色之后,z的兄弟结点和z颜色相同
z->parent->parent->color=RED; //红黑树局部恢复平衡
right_rotate(T,z->parent->parent); //这个技巧是:改变颜色之后,然后旋转,这样不破坏红黑树性质
} //与此同时,结点沿树上升
}
else
{
os_node *y=z->parent->parent->left;
if(y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else
{
if(z==z->parent->left)
{
z=z->parent;
right_rotate(T,z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
left_rotate(T,z->parent->parent);
}
}
}
T->root->color=BLACK;
}

succ_and_other.h

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
#include "os_tree.h"
os_node *tree_maxinum(os_tree *T, os_node *x)
{
while(x!=T->nil && x->right!=T->nil)
x=x->right;
return x;
}
os_node *tree_minimum(os_tree *T,os_node *x)
{
while (x->left!=T->nil) {
x=x->left;
}
return x;
}
os_node *tree_successor(os_tree *T, os_node *x)
{
if(x->right!=T->nil)
{
return tree_minimum(x->right);
}
os_node *y=x->parent; //后继在根节点处
while(y!=T->nil && x==y->right)
{
x=y;
y=y->parent;
}
return y;
}
os_node *tree_predecessor(os_tree *T, os_node *x)
{
if(x->left!=T->nil)
{
return tree_maxinum(x->left);
}
os_node *y=x->parent;
while(y!=T->nil && x==y->left)
{
x=y;
y=y->parent;
}
return y;
}
os_node *Iterative_tree_search(os_tree *T,os_node *x, int k)
{
while(x!=T->nil && k!=x->key)
{
if(k<x->key)
x=x->left;
else x=x->right;
}
return x;
}
void in_order_traverse(os_tree *T, os_node *p)
{
if(p!=T->nil)
{
in_order_traverse(p->left);
cout<<p->key<<" "<<p->color<<" "<<p->size<<endl;
in_order_traverse(p->right);
}
}
os_node *os_select_rank(os_tree *T, os_node *x, int i)
{
int r=x->left->size+1;
if(i==r)
return x;
else if(i<r)
return os_select_rank(T,x->left,i);
else return os_select_rank(T,x->right,i-r);
}
int Interative_os_rank(os_tree *T,os_node *x)
//确定x这个节点的顺序统计树的rank
{
int r=x->left->size+1;
os_node *y=x; //沿左脊柱上升,r=x->left->size+1
while(y!=T->root) //如果是沿着右脊柱上升?y->size=y->left->size+1+sum{y->parent->size}
{ //沿左脊柱上升,r保持不变;一旦拐弯到了右脊柱,要关注y->parent->left->size+1
if(y==y->parent->right)
r=r+y->parent->left->size+1;
y=y->parent;
//不管是左脊柱还是右脊柱,都要沿树上升
}
return r;
}

Josephus_circle.h

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
#include "delete.h"
#include "succ_and_other.h"
void Josephus_imple(os_tree *T, int m, int n)
{
os_node *x=T->root;
int k=0, i=n;
int t=1;
while(T->root!=NULL && i>0)
{
k=(t+m-1)%i;
//k就是我们需要删除的点,注意到我们对一个点执行删除之后
//这个点原来的下标是k,删除了之后k+1就自动补到k的位置上
//这样新的k重新编号的话就是1,相当于原来的t=1
if(k==0)
k=i;
os_node *del=os_select(T,k);
//这里del表示要删除的结点
cout<<del->key<<" ";
//输出节点
RB_delete(del);
t=k;
i--;
}
}

主函数

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
#include "Josephus_circle.h"
#include <iostream>
#include "time.h"
#include "os_tree.h"
#include "delete.h"
#include "insert.h"
using namespace std;
int main()
{
srand((unsigned)time(NULL));
int m=0,n=0;
cout<<"输入Josephus排列的m和n值"<<endl;
cout<<"m=";
cin>>m;
cout<<"n=";
cin>>n;
int *array_jose=new int [n];
//对数组进行赋值和初始化
for(int j=0;j<n;j++)
{
array_jose[j]=j+1;
cout<<array_jose[j]<<" ";
}
cout<<endl;
os_node *nilnode=new os_node [LEN];
os_tree *T=new os_tree [LENTREE];
os_node *newroot=new os_node [LEN];
nilnode->key=-1;
nilnode->color=BLACK;
T->nil=nilnode;
int i=0;
newroot->key=array_jose[i++];
RB_insert(T,newroot);
T->root=newroot;
while(i!=n)
{
os_node *z=new os_node[LEN];
z->key=array_jose[i];
RB_insert(T,z);
i++;
}
in_order_traverse(T,T->root);
cout<<"Josephus排列"<<" ";
Josephus_imple(T,m,n);
}
原创技术分享,您的支持鼓励我继续创作