avatar

一个经典约瑟夫问题的分析与解答

一、约瑟夫问题的由来

  约瑟夫问题(Josephus)是由古罗马的史学家约瑟夫(全名Titus Flavius Josephus)提出的。它是一个出现在计算机科学和数学中的经典问题。在计算机编程的算法中,类似问题又称为约瑟夫环。
  Josephus是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。Josephus将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
  约瑟夫问题的一般描述形式为:设有编号为1,2,……,n的N个人围成一个圈,从第1个人开始报数,报到M时停止报数,报M的人出圈,再从他的下一个人起重新报数,报到M时停止报数,报M的出圈,……,按照这个规则进行下来,直到所有人全部出圈为止。当任意给定N和M后,构建相关数据结构与算法求N个人出圈的次序。

二、典型例题

  有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下来的是原来第几号的那个人。

三、分析解答

  可以采用数组或者循环链表的数据结构来解答这道题目。各有优点。数组实现起来简单,但是逻辑上复杂。循环链接逻辑上简单,实现起来复杂。下面采用两种方法解答此题。

3.1 采用数组存储数据

  利用数组保存这N个人的序号,设计两个计数器,一个k作为报数计数器,一个m作为退出人数报数器。从第一个人开始计数(数组下标i=0),计数器k到3后清零,数组元素报到最后的时候再从第一个人开始。每退出一个人,相应的数组元素置0,报数计数时只对非0元素计数,当计数器m到n-1是说明只剩下一个人,这时候算法结束,输出剩下人的编号即可。

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
#include<stdio.h>
#define NMAX 50

int main(){

//k 报数计数器
//m 退出人数计数器
int i,k,m,n,num[NMAX];

scanf("%d",&n);

//给N个人写上序号
for(i=0;i<n;i++){
num[i] = i+1;

}

i = k = m =0;
// m = n-1 时说明只剩下一个人
while(m < n -1){

//当前位置的值不为0,则计数,为0代表退出了
if(num[i] != 0){

k++;
}

//计数器K=3的位置人数退出,退出的位置记为0。计数器归0重新计数。退出人数m+1;
if(k == 3){

num[i] = 0;
m++;
k = 0;
}

i++;

if(i == n){

i = 0;
}
}

//输出最后留下来的那个数
i= 0;
while(num[i] ==0){

i++;
}

printf("Left is %d\n", num[i]);

return 0;

}

3.2 采用循环链表存储数据

  利用循环链表存储N个人的序号。将报到k=3的节点从循环链表汇总移除,最后只剩下一个节点循环结束,输出剩下人的编号即可。(其中报数器K的值可以自定义)

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
#include<stdio.h>
#include<stdlib.h>

typedef struct Num_node{

int data;
struct Num_node *next;

}Num_Node;

int main(){

//n 总人数,m退出的人数,k报数计数器
int n,k;
Num_Node *head = NULL , *tail =NULL, *p = NULL;

int i=0;
//输入N,然后初始化链表
scanf("%d",&n);
while(i++<n){

//申请节点所占用的内存空间
if( (p = (Num_Node *)malloc(sizeof(Num_Node))) == NULL){

printf("memery is not available");
exit(1);

}

p->data = i;
p->next = NULL;

//当前申请的是第一个节点
if(head == NULL){

head = tail = p;

}else{
//链尾插值

tail->next = p;
tail = p;

}
//如果是最后一个元素,让其指向head:这样就构成了循环链表
if(i == n){
tail->next = head;
}
}

//凡是报到k=3的节点就从链表中去除。(这个k可以自己定义,只要K<N就行)
k = 3;
p = head;

Num_Node *pre_p = NULL; //p的前驱指针,删除p的时候,需要用到这个指针。

while(p->next != p) //直到p指向自己,说明只剩下一个元素了。
{
for(i = 1; i < k; i++)
{
pre_p = p;
p = p->next;
}
pre_p->next = p->next;
free(p); // 删除结点,从内存释放该结点占用的内存空间
p = pre_p->next;
}


printf("Left is %d \n",p->data);

return 0;
}

三、总结

  约瑟夫问题是一个经典的计算机与数学问题,由来已久,解法也各异。上面两种方法,分别利用了数组、循环链表数据结构来分析这个题目,虽然都可以解决,但是逻辑上的复杂性却有很大的差异。这其中就能够看出数据结构在解决问题过程中的重要性,合适的数据结构会大大降近解题的难度。

文章作者: IT之旅
文章链接: https://www.meijindong.top/posts/3265782771.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 程序员在旅途
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论