#include <bits/stdc++.h>
using namespace std;
const int se = 5001;
int n, m, q[se + 1], front = 1, rear = se;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
rear = rear == se ? 1 : rear + 1;
q[rear] = i;
}
int x = 0, k = 1;
while (rear != front) {
int current_rear = rear;
int psum = n - k + 1;
++x;
int y = q[front];
front = front == se ? 1 : front + 1;
m = k * k % psum;
if (m == 0) {
printf("%d ", q[front]);
++k;
} else {
if (x == m) {
printf("%d ", y);
x = 0;
++k;
} else {
rear = rear == se ? 1 : rear + 1;
q[rear] = y;
}
}
rear = current_rear;
}
}
输入：10
输出：1 5 6 8 9 10 2 3 4 7
有 n
个人排成一圈，从 1
到 n
编号。从第一个人开始依次报数（第一个人报的数是 1
，下一个人报的数是 2
，...，当前这个人报的数字等于前面那个人报的数字加一），报数一共进行 n
轮，对于第 i
(1≤i≤n)
轮，数到 i2
的人出列，下一个人继续从 1
开始报数。结束的时候所有人都会出列。
请依次输出每一轮出列的人的编号。
你得说下你怎么一个拓展，你的问题和标准约瑟夫问题的区别是什么
【以下回答由 GPT 生成】
优化约瑟夫问题拓展的C++代码如下：
#include <iostream>
#include <vector>
using namespace std;
vector<int> josephus(int n, int m) {
vector<int> result;
vector<int> people(n);
// 初始化编号
for (int i = 0; i < n; i++) {
people[i] = i + 1;
}
int index = 0;
while (n > 0) {
index = (index + m - 1) % n; // 找到要出列的人的索引
result.push_back(people[index]); // 将该人的编号加入结果数组
people.erase(people.begin() + index); // 从people数组中删除该人
n--; // 总人数减一
}
return result;
}
int main() {
int n, m;
cout << "请输入要求解的正整数n：";
cin >> n;
cout << "请输入每次数m个人：";
cin >> m;
vector<int> result = josephus(n, m);
cout << "按顺序出列的人的编号为：";
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
输入：
请输入要求解的正整数n：10
请输入每次数m个人：3
输出：
按顺序出列的人的编号为：3 6 9 2 7 1 8 5 10 4
【相关推荐】