有n个小孩围成一圈,从1顺序排号。从第一个人开始报数(1~k报数),凡报到k的人退出圈子,问最后留下的人原来排在第几号。 输入:人数(不超过1000),以及报数的k(不超过3000),空格分隔。 输出:最后留下的人的编号
时间: 2024-03-02 12:50:57 浏览: 67
python 有n个人围成一圈,顺序排号,问最后留下的是原来第几号的那位。(示例)
5星 · 资源好评率100%
这个问题就是经典的约瑟夫问题,同样可以使用循环链表来模拟。
具体思路是,先创建一个循环链表,然后从头节点开始遍历,每经过 k 个节点就删除当前节点,直到只剩下一个节点为止。
以下是使用 C 语言实现的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
struct Node* next;
} Node;
// 创建指定数量的节点,并返回链表头节点
Node* createList(int n) {
Node* head = (Node*)malloc(sizeof(Node));
head->val = 1;
head->next = NULL;
Node* prev = head;
for (int i = 2; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->val = i;
node->next = NULL;
prev->next = node;
prev = node;
}
prev->next = head;
return head;
}
// 删除指定节点,并返回下一个节点
Node* deleteNode(Node* prev, Node* node) {
prev->next = node->next;
Node* next = node->next;
free(node);
return next;
}
// 模拟约瑟夫问题
int josephus(int n, int k) {
Node* head = createList(n);
Node* prev = head;
while (n > 1) {
// 遍历 k - 1 个节点
for (int i = 0; i < k - 1; i++) {
prev = prev->next;
}
Node* node = prev->next;
prev = deleteNode(prev, node);
n--;
}
int result = prev->val;
free(prev);
return result;
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
int result = josephus(n, k);
printf("%d\n", result);
return 0;
}
```
在这个示例代码中,我们定义了一个 `Node` 结构体表示链表节点,然后使用 `createList` 函数创建了循环链表。在 `josephus` 函数中,我们使用循环和 `deleteNode` 函数模拟了约瑟夫问题的求解过程。最后,在 `main` 函数中读取了用户输入的参数,并调用 `josephus` 函数求解问题。
阅读全文