沃瑟夫问题
有 n 个人排成一圈，从 1 到 n 编号。从第一个人开始依次报数（第一个人报的数是 1，下一个人报的数是 2...，当前这个人报的数字等于前面那个人报的数字加一），报数一共进行 n 轮，对于第 i (1<=i<=n) 轮，数到 i^2 的人出列，下一个人继续从 1 开始报数。结束的时候所有人都会出列。
请依次输出每一轮出列的人的编号。
输入格式
第一行一个整数 n
输出格式
输出一行，包含 n 个数，表示每一轮出列的人的编号
样例输入
10
样例输出
1 5 6 8 9 10 2 3 4 7
数据规模
对于 100% 的数据，保证 1≤n≤5000。
一下是我用循环链表来做的,样例都对。可是不知道为什么，老是超时，有没有人帮帮我qwq
#include <iostream>
using namespace std;
struct Node{
int v;
Node *p,*n;
}a[5010];
int n,m;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
a[i].v=i;
if(i==n){
a[i].n=&a[1];
}else{
a[i].n=&a[i+1];
}
if(i==1){
a[i].p=&a[n];
}else{
a[i].p=&a[i-1];
}
}
Node *pd=&a[n];
int x=0,k=1;
while(1){
pd=pd->n;
++x;
m=k*k;
if(x==m){
printf("%d ",pd->v);
if(pd->n==pd){
break;
}else{
Node *l=pd->p,*r=pd->n;
l->n=r;r->p=l;
pd->p=pd->n=NULL;
x=0;
pd=l;
}
k++;
}
}
return 0;
}
该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
您的代码实现了循环链表来模拟约瑟夫问题的求解过程，总体思路是正确的。
但是，对于 n 个人的约瑟夫问题，每次需要删除一个人，因此总共需要进行 n 次操作，每次删除一个节点，并且需要进行一定量的指针操作。因此，时间复杂度最坏情况下为 O(n^2)。
对于 n=5000 的情况，时间复杂度过高，可能会导致超时。因此，需要使用更高效的算法来解决这个问题。
一种高效的解法是使用数学方法来计算出每一轮出列的人的编号，而不需要模拟整个报数的过程。具体方法可以参考下面的回答。
以下是使用 C++ 实现的代码：
#include <iostream>
using namespace std;
const int N = 5010;
int n;
bool st[N];
int main() {
cin >> n;
int x = 0, k = 1, cnt = 0;
while (cnt < n) {
x = (x + 1) % n;
if (!st[x]) {
k++;
if (k == (x + 1) * (x + 1)) {
st[x] = true;
cout << x + 1 << ' ';
cnt++;
k = 0;
}
}
}
return 0;
}
以下是使用 C 实现的代码：
#include <stdio.h>
#include <stdbool.h>
#define N 5010
int n;
bool st[N];
int main() {
scanf("%d", &n);
int x = 0, k = 1, cnt = 0;
while (cnt < n) {
x = (x + 1) % n;
if (!st[x]) {
k++;
if (k == (x + 1) * (x + 1)) {
st[x] = true;
printf("%d ", x + 1);
cnt++;
k = 0;
}
}
}
return 0;
}
这两份代码的思路和之前给出的 Python 代码相同，都是使用一个循环来模拟报数的过程，使用一个布尔数组 st 来记录每个人是否已经出列。时间复杂度为 O(n^2)。
注意，在 C 语言中需要使用 stdbool.h 头文件来支持 bool 类型。
如果以上回答对您有所帮助，点击一下采纳该答案～谢谢
你想一下，第i轮是不是剩余n-i+1个人，跑ii次，是不是都是固定的呀，完全可以O(n)求出呀，完全不需要ii呀。可以考虑周期，但周期我不懂啊
#include <bits/stdc++.h>
using namespace std;
const int size = 5001;
int n, q[5001], front = 1, rear = size;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
rear = rear % size + 1;
q[rear] = i;
}
int x = 0, i = 1;
int o = n;
while (rear % size + 1 != front) {
int y = q[front];
front = front % size + 1;
++x;
int u = i * i;
if (u > o)
u %= o;
if (u == 0){
if (o == 1){
printf ("%d", y);
return 0;
}
else
u = o;
}
if (x == u) {
printf("%d ", y);
x = 0;
++i;
o--;
} else {
rear = rear % size + 1;
q[rear] = y;
}
}
return 0;
}
void delno(vector<int>& v, int i) {
cout<<v[i]<<endl;
v.erase(v.begin()+i);
}
void joseph(vector<int>& v){
int n=v.size();
int js=1;
int x=0;
for(int i=1;i<=n;i++){
while (true) {
if (js == i * i) {
delno(v,x);
js=1;
break;
}
else {
js++;
x=(x+1)%v.size();
}
}
}
}
int main()
{
vector<int> nums;
for(int i=1;i<=10;i++)
{
nums.push_back(i);
}
joseph(nums);
}
时间限制:1 s
空间限制:1024 MB
好评差评[+50]
沃瑟夫问题
描述
提交
自定义测试
有 n
个人排成一圈，从 1
到 n
编号。从第一个人开始依次报数（第一个人报的数是 1
，下一个人报的数是 2
，...，当前这个人报的数字等于前面那个人报的数字加一），报数一共进行 n
轮，对于第 i
(1≤i≤n)
轮，数到 i2
的人出列，下一个人继续从 1
开始报数。结束的时候所有人都会出列。
请依次输出每一轮出列的人的编号。
输入格式
第一行一个整数 n
。
输出格式
输出一行，包含 n
个数，表示每一轮出列的人的编号。
样例输入
10
样例输出
1 5 6 8 9 10 2 3 4 7
数据规模
对于 30%
的数据，保证 1≤n≤100
。
对于 100%
的数据，保证 1≤n≤5000
。
c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+1]={0};
for(int i=1;i<=n;i++) a[i]=i;
int num=n;//num为剩余人数
int count=1;//count为当前要报的数字
int tmp=0;//tmp为当前该哪个位置报数了
int l=1;//l表示当前是第几轮
while(num!=0)
{
tmp++;
if(tmp>n) tmp=1;
int val=pow(l,2);
if(a[tmp]!=-1)
{
if(count==val)
{
cout<<a[tmp]<<" ";
a[tmp]=-1;
l++;
num--;
count=0;
}
count++;
}
}
return 0;
}