约瑟夫生死者游戏

[问题描述]

约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

[基本要求]

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]

m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]

程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。

算法代码

复制收展Markdown#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#define OK 1
#define ERROR -1
#define OVERFLOW 0
//约瑟夫生死者游戏（循环单链表实现） 2019-12-30
//[测试数据]m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
typedef struct LNode
{ // 结点类型定义
int no; //编号 
int pwd; //报m的人出列，将他的密码作为新的m值
int length; //长度 
struct LNode *next;
}LNode, *LinkList;
//初始化链表,函数调用完毕后,L会指向一个空的链表,即会改变指针的值。所以要用*L指向指针的指针 
int InitList_CL( LinkList *L ) //　生成只含头结点的空循环单链表
{
*L = (LinkList)malloc(sizeof(LNode));
if(!(*L)) 
exit(OVERFLOW);
(*L)->next = *L;
(*L)->length=0;
return OK;
}
//创建链表 
int CreateList_CL( LinkList L, int n )
{ // 按尾插入法建立含n个元素的循环单链表
LNode *p, *q;
int i,no; 
L->length=n;	//长度 
q = L;
//int pwds[]={0,3,1,7,2,4,8,4};
for(i=1; i<=n; i++)
{
p = (LNode *)malloc(sizeof(LNode)); // p指向新结点
//scanf ("%d",&p->data);
p->no = i; //编号 
//密码 
//p->pwd= i*i+1;
//p->pwd= pwds[i];
printf("输入第%d个人的密码pwd=", i);
scanf("%d", &(p->pwd)); 
//添加结点 
p->next = q->next; //新增结点最后一个结点p指向头结点L 
q->next = p; // 
q = p; // q指向表尾结点
}
return OK;
}

// 遍历循环单链表L
int TraverseList_CL( LinkList L )
{ 
LNode *p;
p = L->next;
while( p!=L )
{
printf ("no=%d ,pwd=%d\n",p->no, p->pwd);
p = p->next;
}
printf("\n");
return OK;
}

//约瑟夫（Joeph）问题
int yuesefu( LinkList L, int m)
{ LNode *p, *q;
int i=0;
p=L;
//结束 递归出口 
if(L->length == 0) return OK;
//报到m时停止报数
m = m % (L->length);
//最后一个得到的余数是0，且m此时和链表此时的长度一样
if(m == 0) m= L->length;
//printf("m=%d\n",m);
for(i=1;i<m;i++){
p = p->next;
//printf("p->no=%d\n",p->no);
}
//q是要出去的要删除的 
q=p->next; 
printf("编号为【%d】的人出列\n",q->no);
p->next=q->next;
L->length = L->length - 1;	
//printf("L->length=%d\n",L->length);
//printf("他们的编号是:\n");
//TraverseList_CL( L );
//printf("q->pwd=%d\n",q->pwd);
//+m是从第一个开始，模拟上一次的
return yuesefu(L, q->pwd+m-1);
}

void main()
{
LinkList L;
int i, m, n;
//初始化 
InitList_CL(&L);
printf("-----------约瑟夫生死者游戏-----------\n");
printf("【游戏规则】游戏编号为1,2,3…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。\n"); 
n=7;
m=20;
printf("一共有n个人n=");
scanf ("%d",&n);
//创建链表 
CreateList_CL( L, n );
printf("最开始他们的编号/密码是:\n");
TraverseList_CL( L );
printf("m的初值为m=");
scanf ("%d",&m);
//使用递归实现 
yuesefu(L, 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

效果