N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。 请按退出顺序输出每个退出人的原序号。 输入格式: 输入只有一行,包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。 输出格式: 按退出顺序输出每个退出人的原序号,数据间以一个空格分隔,但行尾无空格。用c语言做出来并附带详细解析
时间: 2024-03-15 14:45:39 浏览: 46
这道题是经典的约瑟夫问题,可以使用循环链表来解决。
首先,我们需要创建一个循环链表,节点的值为对应的编号。
然后,我们从头节点开始遍历链表,每次遍历p-1个节点,将第p个节点删除,并记录其编号。
接下来,从第p个节点的下一个节点开始继续遍历,重复上述步骤,直到链表中只剩下一个节点为止。
最后,输出记录的所有编号,即为退出顺序。
下面是具体的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构体
typedef struct Node {
int val; // 节点的值,即对应的编号
struct Node* next; // 指向下一个节点的指针
} Node;
// 创建循环链表
Node* createList(int n) {
Node* head = NULL;
Node* cur = NULL;
for (int i = 1; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->val = i;
if (head == NULL) {
head = node;
} else {
cur->next = node;
}
cur = node;
}
cur->next = head; // 将最后一个节点的next指向头节点,形成循环链表
return head;
}
// 删除链表中的节点
Node* deleteNode(Node* node, int p) {
for (int i = 1; i < p - 1; i++) {
node = node->next;
}
Node* delNode = node->next;
node->next = delNode->next;
int val = delNode->val;
free(delNode);
printf("%d ", val); // 输出删除的节点的值,即对应的编号
return node->next;
}
// 约瑟夫问题求解函数
void josephus(int n, int p) {
Node* head = createList(n);
Node* cur = head;
while (cur->next != cur) {
cur = deleteNode(cur, p);
}
printf("%d", cur->val); // 输出最后剩下的节点的值,即对应的编号
}
int main() {
int n, p;
scanf("%d%d", &n, &p);
josephus(n, p);
return 0;
}
```
时间复杂度为O(n*p),空间复杂度为O(n)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)