有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。 输入格式: 正整数 M和两个报数。 输出格式: 每个测试用例结果占一行,每个编号占4位。 输入样例: 10 3 5 输出样例: 在这里给出相应的输出。例如: 7 4 1 6 10 5 3 2 8 9
时间: 2024-03-15 14:43:56 浏览: 87
BaoShu.rar_MáS_m baoshu
这是一个经典的约瑟夫环问题。我们可以使用循环链表来模拟这个过程。先创建一个包含所有人的循环链表,然后从第一个人开始报数,每数到第 N 个人就将其删除,直到链表中只剩下一个人。接着再次从第一个人开始报数,每数到第 K 个人就将其删除,直到链表中只剩下一个人。最后输出每个人的编号即可。
以下是实现这个算法的 C++ 代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
Node *createList(int n) {
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; // 将链表首尾相连
return head;
}
vector<int> josephus(Node *head, int n, int m, int k) {
vector<int> res;
Node *p1 = head;
for (int i = 1; i < m; i++) { // 找到起始节点
p1 = p1->next;
}
while (n--) { // 模拟约瑟夫环
for (int i = 1; i < k; i++) {
p1 = p1->next;
}
res.push_back(p1->val);
Node *p2 = p1->next;
p1->val = p2->val;
p1->next = p2->next;
delete p2;
}
return res;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
Node *head = createList(n);
vector<int> res1 = josephus(head, n, m, n);
vector<int> res2 = josephus(head, n, k, n - 1);
for (int i = 0; i < res1.size(); i++) {
cout << res1[i] << " ";
}
cout << endl;
for (int i = 0; i < res2.size(); i++) {
cout << res2[i] << " ";
}
cout << endl;
return 0;
}
```
在这个程序中,我们首先定义了一个链表节点结构体 `Node`,包含一个值和一个指向下一个节点的指针。然后定义了 `createList()` 函数来创建一个包含所有人的循环链表,其中的 `n` 参数表示总人数。
接着定义了 `josephus()` 函数来模拟约瑟夫环。其中的 `m` 参数表示起始报数的人的编号,`k` 参数表示每次报数的最大值。函数返回一个包含出列人员编号的数组。
在 `main()` 函数中,我们首先读入输入的三个参数。然后调用 `josephus()` 函数两次,分别模拟第一次和第二次出列的过程。最后输出每个人的编号即可。
注意,在第二次出列时,链表中已经只剩下一个人了,因此 `k` 的值应该为 `n-1`。
阅读全文