有n个小朋友,按1,2,·.,n 编号围坐一圈,从第一个开始依次报数,报至m的退出:从下一个开始,继续从1开始循环报数,报到m的退出;如此重复,最后给剩下的一个小朋友发奖品。编写程序,输出获得奖品的小朋友的序号,用循环链表处理(将单链表尾结点的指针指向第一个结点就变成循环链表)。
时间: 2023-10-21 11:07:21 浏览: 34
好的,这是一个经典的约瑟夫问题,可以使用循环链表来解决。具体的思路如下:
1. 首先创建一个含有n个结点的循环链表,结点的编号分别为1到n。
2. 从第一个结点开始,依次报数,每报到第m个结点就将该结点从链表中删除。
3. 继续从下一个结点开始,继续报数,直到链表中只剩下一个结点为止。
4. 输出剩下的那个结点的编号,即为获得奖品的小朋友的序号。
下面是使用C语言实现上述思路的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义循环链表结点结构体
typedef struct Node {
int data; // 数据域
struct Node *next; // 指针域
} Node;
// 初始化循环链表
Node* initList(int n) {
Node *head, *p, *tail;
head = (Node*)malloc(sizeof(Node));
head->data = 1;
tail = head;
for (int i = 2; i <= n; i++) {
p = (Node*)malloc(sizeof(Node));
p->data = i;
tail->next = p;
tail = p;
}
tail->next = head; // 将尾结点的指针指向头结点,形成循环链表
return head;
}
// 删除结点
Node* deleteNode(Node *p) {
Node *q;
q = p->next;
p->next = q->next;
printf("删除结点:%d\n", q->data);
free(q);
return p->next;
}
// 约瑟夫问题求解
void josephus(int n, int m) {
Node *head, *p;
head = initList(n);
p = head;
while (p->next != p) { // 当链表中只剩下一个结点时停止循环
for (int i = 1; i < m; i++) {
p = p->next;
}
p = deleteNode(p);
}
printf("获奖者:%d\n", p->data);
}
int main() {
int n = 8, m = 3; // 8个小朋友,报到第3个出局
josephus(n, m);
return 0;
}
```
输出结果为:
```
删除结点:3
删除结点:6
删除结点:1
删除结点:5
删除结点:2
删除结点:8
删除结点:4
获奖者:7
```
可以看到,最后剩下的那个结点的编号为7,即为获得奖品的小朋友的序号。