C++代码题目:N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。 请按退出顺序输出每个退出人的原序号。 输入格式: 输入只有一行,包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。 输出格式: 按退出顺序输出每个退出人的原序号,数据间以一个空格分隔,但行尾无空格。 输入样例: 在这里给出一组输入。例如: 7 3 输出样例: 3 6 2 7 5 1 4
时间: 2023-03-29 22:02:50 浏览: 88
我可以回答这个问题。这是一个经典的约瑟夫问题,可以使用循环链表来解决。具体实现可以参考以下代码:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int num;
struct Node *next;
} Node;
int main() {
int n, p;
scanf("%d %d", &n, &p);
// 创建循环链表
Node *head = (Node*)malloc(sizeof(Node));
head->num = 1;
Node *cur = head;
for (int i = 2; i <= n; i++) {
Node *node = (Node*)malloc(sizeof(Node));
node->num = i;
cur->next = node;
cur = node;
}
cur->next = head;
// 开始报数并删除节点
while (cur != cur->next) {
for (int i = 1; i < p; i++) {
cur = cur->next;
}
printf("%d ", cur->next->num);
Node *tmp = cur->next;
cur->next = tmp->next;
free(tmp);
}
printf("%d\n", cur->num);
return ;
}
阅读全文