前言

前两天朋友给我发来一个题目,问我能不能用C语言链表实现。

13个人围成一圈,从第1个人开始顺序报号1,2,3。凡报到“3”者退出圈子,找出最后留在圈子中的人原来的序号。要求用链表实现。

看了题目以后发现其实是 约瑟夫环,是一个数学应用问题。

约瑟夫环

约瑟夫环 又称为 约瑟夫问题丢手绢问题

一群人围在一起坐成环状,从某个编号开始报数,数到某个数的时候,此人出列,下一个人重新报数,一直循环,直到所有人出列,约瑟夫环结束。

例如有序号分别为 1、2、3 的人围成一个圈, 从 1 开始报数,数到 3 的淘汰。

第一轮,淘汰:3,剩余 1、2、

第二轮,淘汰:1,剩余 2

2 号就是最后留在圈子中的人。

代码实现

代码中用了链式队列的思想来模拟报数,头部取出,尾部插入。

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

/**
* 结构体
*/
struct PerNode {
// 序号
int m_iNumber;
// 下一个元素的指针
struct PerNode * m_pNextPer;
};

/*
**函数功能:采用malloc函数动态地创建并初始化一个单向链表
**入口参数:iLstLen为拟创建链表的结点数
**返回值:新创建链表的头结点的指针
*/
struct PerNode * crtPrLst(int iLstLen) {
// 生成头节点
struct PerNode *headNode = malloc(sizeof(struct PerNode));

struct PerNode * perNode = headNode;
perNode->m_pNextPer = NULL;

// 用于存放临时生成的元素
struct PerNode *temp;

// 创建链表
for (int i = iLstLen; i >= 1 ; i--) {
temp = malloc(sizeof(struct PerNode));
temp->m_iNumber = i;
temp->m_pNextPer = perNode->m_pNextPer;
perNode->m_pNextPer = temp;
}

return headNode;
}

/**
* 删除并返回链表的第一个元素
* @param pTmp
* @return
*/
struct PerNode * pop(struct PerNode * pTmp) {
if (pTmp == NULL) {
return NULL;
}

// 取出第一个元素
struct PerNode * temp = pTmp->m_pNextPer;

if (temp == NULL) {
return NULL;
}

// 移除第一个元素
pTmp->m_pNextPer = temp->m_pNextPer;

return temp;
}

/**
* 向链表的末尾添加一个元素
* @param pTmp
* @param value
*/
void push(struct PerNode * pTmp, int value) {
struct PerNode * l = pTmp->m_pNextPer;

// 遍历到最后一个元素
while (l != NULL && l->m_pNextPer != NULL) {
l = l->m_pNextPer;
}

// 新建一个元素
struct PerNode * node = malloc(sizeof(struct PerNode));
node->m_iNumber = value;
node->m_pNextPer = NULL;

// 如果最后一个元素不为空则插入到它的后面
if (l != NULL) {
l->m_pNextPer = node;
}
}

struct PerNode * josephus(struct PerNode *pTmp) {
// 计数器,用来报数
int i = 0;
// 最后留在圈子中的元素
struct PerNode * p;

while (1) {
// 模拟报数
i++;
// 取出一个元素
struct PerNode * node = pop(*&pTmp);
// 如果元素为 NULL,则说明没有人了
if (node == NULL) {
break;
}

// 如果这个人报数不是 3,则放回链表尾部
if (i % 3 != 0) {
push(*&pTmp, node->m_iNumber);
}

// 记录当前的元素
p = node;
}

return p;
}

/**
* 打印链表
* @param l
*/
void printLink(struct PerNode * l)
{
while (l != NULL) {
printf("%d \n", l->m_iNumber);
l = l->m_pNextPer;
}

printf("---------\n");
}

int main() {
// 创建一个长度为13的链表
struct PerNode *pHead = crtPrLst(13);
// 找出最后在圈子中的人
pHead = josephus(pHead);
// 打印它的序号
printf("%d \n", pHead->m_iNumber);

return 0;
}

2018 年最后一篇文章。