C语言,有n个人围成一圈,,顺序排号,从第r个人开始 报数(从1到m报数),凡是报m的人退出圈子 ,如此循环; 输入n,r,m,(以空格区分) 要求输出最后剩下的是原来第几号哪位。
时间: 2024-02-24 11:00:08 浏览: 20
这是一个经典的约瑟夫问题,可以使用循环链表来解决。具体的算法流程如下:
1. 创建一个循环链表,链表中的每个节点表示一个人,初始时链表中有n个节点,节点的编号从1到n。
2. 找到从第r个人开始报数的节点,并将其设为当前节点。
3. 从当前节点开始,依次报数,每报数到m时,将当前节点从链表中删除。
4. 如果链表中只剩下一个节点,那么这个节点就是最后剩下的人,其编号即为答案。
5. 如果链表中还有多个节点,那么将当前节点移动到链表中下一个节点,然后重复步骤3。
以下是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义循环链表的节点结构体
typedef struct Node {
int num; // 节点编号
struct Node* next; // 指向下一个节点的指针
} Node;
int main() {
int n, r, m;
scanf("%d %d %d", &n, &r, &m);
// 创建循环链表
Node* head = (Node*) malloc(sizeof(Node));
head->num = 1;
Node* tail = head;
for (int i = 2; i <= n; i++) {
Node* node = (Node*) malloc(sizeof(Node));
node->num = i;
tail->next = node;
tail = node;
}
tail->next = head;
// 找到从第r个人开始报数的节点,并将其设为当前节点
Node* cur = head;
for (int i = 1; i < r; i++) {
cur = cur->next;
}
// 依次报数,并将报到m的节点从链表中删除,直到只剩下一个节点
while (cur->next != cur) {
for (int i = 1; i < m; i++) {
cur = cur->next;
}
Node* del = cur->next;
cur->next = del->next;
printf("删除编号为%d的人\n", del->num);
free(del);
}
// 输出最后剩下的节点编号
printf("最后剩下的是原来第%d号哪位\n", cur->num);
// 释放链表内存
Node* p = head;
while (p->next != head) {
Node* del = p;
p = p->next;
free(del);
}
free(p);
return 0;
}
```
注意:以上代码中的链表是循环链表,即链表的最后一个节点的指针指向链表的头节点。这样可以方便地实现从链表末尾删除节点的操作。