循环报数问题,有n个人围成一圈,顺序编号。从第一个人开始从1到m报数,凡报m的人退出圈子,请编程计算最后留下的那个人的初始编号是什么,c语言
时间: 2023-12-23 19:14:50 浏览: 46
好的,这里是使用 C 语言实现的代码,同样是使用循环链表来模拟报数的过程:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
typedef struct Node {
int value;
struct Node *next;
} Node;
// 创建链表
Node* createList(int n) {
Node *head = (Node*) malloc(sizeof(Node));
head->value = 1;
head->next = NULL;
Node *cur = head;
for (int i = 2; i <= n; i++) {
Node *node = (Node*) malloc(sizeof(Node));
node->value = i;
node->next = NULL;
cur->next = node;
cur = node;
}
cur->next = head; // 将最后一个节点的 next 指针指向头节点,形成循环链表
return head;
}
// 删除节点
void deleteNode(Node *cur) {
Node *temp = cur->next;
cur->next = temp->next;
free(temp);
}
// 解决约瑟夫问题
int josephus(int n, int m) {
Node *head = createList(n); // 创建循环链表
Node *cur = head;
while (cur->next != cur) { // 只有一个节点时跳出循环
for (int i = 1; i < m; i++) {
cur = cur->next;
}
deleteNode(cur); // 删除节点
}
int result = cur->value; // 最后剩下的节点就是答案
free(cur);
return result;
}
int main() {
int n, m;
printf("请输入 n 和 m:");
scanf("%d%d", &n, &m);
int result = josephus(n, m);
printf("最后留下的人的编号是:%d\n", result);
return 0;
}
```
注意:在上面的代码中,我们同样是使用一个循环链表来模拟报数的过程,为了方便起见,我们在创建链表时,将最后一个节点的 next 指针指向了头节点,这样就形成了一个循环链表。同时,我们需要注意,在删除节点时,需要将被删除节点的内存空间释放。