0%

约瑟夫生死游戏

问题描述

用循环链表实现:N个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长告诉乘客,只有将部分乘客投入海中,其余人才能幸免于难。 无奈,大家只得同意这种办法。于是N个人围成一圈(从1,2,3…N分别编号)。由编号为1的人开始,依次报数,数到第M人,便把他投入大海中, 然后再从他的下一个人数起,数到第M人,再将他扔到大海中,如此循环地进行,直到剩下K个乘客为止。按顺序依次输出被扔下大海的乘客的编号。

提交格式: 实现int * solve(int N,int M,int K)函数。 函数参数为乘客人数N、间隔人数M和剩余乘客人数K,1<=N<=1000,1<=M<=500000,0<=K<N。 函数返回值为按顺序被扔下大海乘客编号的数组。 请不要printf输出任何内容。

核心思路
  1. 创建并初始化循环链表;

  2. 按照间隔人数M删除节点,同时记录被扔下大海乘客编号;

  3. 返回按顺序被扔下大海乘客编号的数组地址。

实现要点
  1. 头节点不存储编号,循环时注意绕开;

  2. 动态内存分配后,应立即判断是否分配成功;

  3. 删除i==M处节点时,需从i==M-1处节点对下一个节点进行判断,从而绕开头节点。这使得当M==1时,需从i==0处节点进行判断,不在i的循环范围1~M之中。故M==1的情况须单独处理。

测试样例

输入样例1: 9 3 2 输出样例1: 3 6 9 4 8 5 2

输入样例2: 12 5 6 输出样例2: 5 10 3 9 4 12

输入样例3: 7 1 3 输出样例3: 5 6 7

源代码
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
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int d;
struct node* next;
} node;
int* solve(int N, int M, int K);
void print(int* a,int n,int k);
int main()
{
int n, k, m;
int* data;
printf("请输入人数n,间隔人数m,剩余人数k:\n");
scanf_s("%d%d%d", &n, &m, &k);
data = solve(n, m, k);
print(data,n,k);
return 0;
}
int* solve(int N, int M, int K)
{
node* Header = (node*)malloc(sizeof(node));
if (!Header)return NULL;
node* p, *q;
Header->next = Header;
p = Header;
for (int i = 1; i <= N; ++i)
{
q = (node*)malloc(sizeof(node));
if (!q)
{
return NULL;
}
q->d = i;
q->next = p->next;
p->next = q;
p = q;
}
p = Header->next;
int z = N - K;
int* a = (int*)malloc(z*sizeof(int));
if (!a)
{
return NULL;
}
int i = 1, j = N,s=0;//i控制每M个人删除;j存储剩余人数
if (M == 1)
{
for (i = 0; i < z; i++)
{
a[s++] = i + 1;
}
}
else
{
while (j > K)
{
if (i == M - 1)
{
if (p->next != Header)//不是删除第一个结点
{
q = p->next;
p->next = q->next;
a[s++] = q->d;
}
else//删除第一个结点
{
q = Header->next;
Header->next = q->next;
a[s++] = q->d;
}
free(q);
if (p->next != Header)
{
p = p->next;
}
else
{
p = Header->next;
}
--j;
i = 1;
}
else
{
if (p->next == Header)
{
p = Header->next;
}
else
{
p = p->next;
}
++i;
}
}
}
return a;
}
void print(int* a,int n,int k)
{
for (int i = 0; i < (n-k); i++)
{
printf("%d ",a[i]);
}
}
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道