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
时间: 2024-03-25 08:41:55 浏览: 7
好的,这是一个经典的约瑟夫环问题,可以用循环链表或数组来解决。我可以给你一个基于循环链表的解法。
首先,我们可以创建一个循环链表,将N个人的编号依次插入到链表中。然后,从头节点开始,每个人依次报数,当报数为p时,将该节点从链表中删除,直到链表中只剩下一个节点。
具体的实现方法如下:
1. 创建循环链表,并依次插入N个人的编号。
2. 从头节点开始,每个人依次报数,当报数为p时,删除该节点。
3. 重复步骤2,直到链表中只剩下一个节点为止。
4. 输出每个退出人的原序号。
代码示例:(使用C++实现)
```cpp
#include <iostream>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
int main() {
int n, p;
cin >> n >> p;
// 创建循环链表
Node *head = new Node(1);
Node *cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new Node(i);
cur = cur->next;
}
cur->next = head; // 将链表首尾相连
// 开始报数并删除节点
while (cur->next != cur) {
for (int i = 1; i < p; i++) {
cur = cur->next;
}
Node *pNode = cur->next;
cur->next = pNode->next;
cout << pNode->val << " ";
delete pNode;
}
cout << cur->val << endl;
return 0;
}
```