问题描述】m个人围成一圈,1,2,3循环报数,报到3的人退出,并将退出的序号依次存到数组p中,包括最后一个人的序号。输出最后退出的是原来的第几号(最初的序号,以1起始)。若m=6,则最后退出的是1号,退出的顺序是 : 3 6 4 2 5 1;若m=10,则最后退出的是4号,退出顺序是: 3 6 9 2 7 1 8 5 10 4;若m=100,则最后退出的是91号,退出顺序是: 3 6 9……100 58 91。 编写函数int fun(int m ,int p[ ])实现上述功能,返回m个人中最后退出人的序号,并将退出的序号顺序写入p指向的数组中。在主函数中输入人数,调用fun后输出实参数组中保存的退出序号。每行输出10个数据。 本问题限定人数m不超过200人。
时间: 2023-06-10 14:07:24 浏览: 107
数据结构中约瑟夫环的实现编号为1到n的n个人围成一圈,每人带一个密码c,以m为报数上限。然后从第一个人开始顺时针自1开始报数,报到m的人出列,将其密码作为新的m值,从他的下一个人开始,同样顺时针自1开始报数,依次循环下去,直到所有的人都出列!要求得到依次出列的那些人的编号序列!
4星 · 用户满意度95%
这道题可以使用循环链表来解决,具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num;
struct node *next;
} Node;
int fun(int m, int p[]) {
Node *head, *tail, *p1, *p2;
int i, count;
// 创建循环链表
head = tail = (Node*)malloc(sizeof(Node));
head->num = 1;
for (i = 2; i <= m; i++) {
p1 = (Node*)malloc(sizeof(Node));
p1->num = i;
tail->next = p1;
tail = p1;
}
tail->next = head; // 尾节点指向头节点,形成循环链表
// 开始报数
count = 0;
p1 = head;
while (p1->next != p1) { // 只剩一个节点时退出循环
count++;
if (count == 3) {
p2 = p1->next;
p1->next = p2->next;
p[p1->num-1] = p2->num;
free(p2);
count = 0;
} else {
p1 = p1->next;
}
}
return p1->num;
}
int main() {
int m, p[200], i, j;
printf("请输入人数m:");
scanf("%d", &m);
int last_num = fun(m, p);
printf("最后退出的是原来的第%d号\n", last_num);
printf("退出顺序:");
for (i = 0; i < m; i++) {
printf("%d ", p[i]);
if ((i+1) % 10 == 0) {
printf("\n");
}
}
return 0;
}
```
代码思路如下:
1. 先创建一个循环链表,链表中每个节点表示一个人,节点的 num 属性表示这个人的编号。
2. 从头节点开始,依次报数,每报到 3 就删除当前节点,并将删除的节点的编号存入数组 p 中。
3. 最后只剩一个节点时退出循环,返回这个节点的编号,即为最后退出的人的编号。
注意,数组 p 中存储的是退出的人的编号,不是退出的顺序。退出顺序需要根据数组 p 中的编号进行计算。
阅读全文