P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友，而该题是全部出圈。
输入格式
输入两个整数 n,m。
输出格式
输出一行 n 个整数，按顺序输出每个出圈人的编号。
输入输出样例
输入
10 3
输出
3 6 9 2 7 1 8 5 10 4
说明/提示
1≤m,n≤100
//下面四篇博客和此题有一定联系。
猴子选大王_猴子选大王 go_星河欲转。的博客-CSDN博客
//下面为大家提供六种解决办法，除第一种外，其他都参考自罗勇军《算法竞赛》一书。
//总的来说，此题考的是模拟，第一种方法比较简单易理解，其他的采用了链表知识,可以在草稿纸上推演一下过程就能更好的理解。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,i,x=0,y=0;
map<int,int>a;//可以用数组，不过记得初始化。
cin>>n>>m;
while(y!=n){
for(i=1;i<=n;i++){
if(a[i]==0){
x++;
}
if(x==m){
x=0;
if(y)cout<<" ";
cout<<i;
a[i]=1;y++;
}
}
}
return 0;
}//动态链表
#include<bits/stdc++.h>
using namespace std;
struct node{//定义链表节点
int data;//节点的值
node *next;//单向链表，只有一个next指针
};
int main(){
int n,m;
cin>>n>>m;
node *head,*p,*now,*prev;//定义变量
head=new node;head->data=1;head->next=NULL;//分配第1个节点，数据置为1
now=head;//当前指针是头
for(int i=2;i<=n;i++){
p=new node;p->data=i;p->next=NULL;//p是新节点
now->next=p;//把申请的新节点连到前面的链表上
now=p;//尾针后移一个
}
now->next=head;//尾指针指向头：循环链表建立完成
//以上是建立链表，下面是此题的逻辑和流程，后面4种代码与下面的逻辑流程完全一致。
now=head,prev=head;//从第1个开始数
while((n--)>1){
for(int i=1;i<m;i++){//数到m停下
prev=now;//记录上一个位置，用于下面跳过第m个节点
now=now->next;
}
printf("%d ",now->data);//输出第m个节点
prev->next=now->next;//跳过这个节点
delete now;//释放这个节点
now=prev->next;//新的一轮
}
printf("%d",now->data);//打印最后一个节点
delete now;//释放最后一个节点
return 0;
}//用结构体数组实现单向静态链表
#include<bits/stdc++.h>
using namespace std;
const int N=105;//定义静态链表的空间大小
struct node{//单向链表
int id,nextid;//单向指针
//int data;//如有必要，定义一个有意义的数据
}nodes[N];//定义在全局的静态分配
int main(){
int n,m;
cin>>n>>m;
nodes[0].nextid=1;
for(int i=1;i<=n;i++){
nodes[i].id=i;nodes[i].nextid=i+1;
}
nodes[n].nextid=1;//循环链表：尾针向头
int now=1,prev=1;//从第1个节点开始
while((n--)>1){
for(int i=1;i<m;i++){//数到m停下
prev=now;now=nodes[now].nextid;
}
printf("%d ",nodes[now].id);//打印
nodes[prev].nextid=nodes[now].nextid;//跳过now节点，即删除
now=nodes[prev].nextid;//新的now
}
printf("%d",nodes[now].nextid);//打印最后一个节点
return 0;
} //用结构体数组实现双向静态链表
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{//双向链表
int id;//节点编号
//int data;
int preid,nextid;//前后节点
}nodes[N];
int main(){
int n,m;
cin>>n>>m;
nodes[0].nextid=1;
for(int i=1;i<=n;i++){//建立链表
nodes[i].id=i;
nodes[i].preid=i-1;//前节点
nodes[i].nextid=i+1; //后节点
}
nodes[n].nextid=1;//循环链表：尾针向头
nodes[1].preid=n;//循环链表：头指向尾
int now=1;//从第1个节点开始
while((n--)>1){
for(int i=1;i<m;i++)now=nodes[now].nextid;//数到m停下
printf("%d ",nodes[now].id);//打印
int prev=nodes[now].preid,next=nodes[now].nextid;
nodes[prev].nextid=nodes[now].nextid;//删除now
nodes[next].preid=nodes[now].preid;//新的开始
now=next;
}
printf("%d",nodes[now].nextid);//打印
return 0;
}#include<bits/stdc++.h>
using namespace std;
int nodes[150];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n-1;i++)nodes[i]=i+1;//下一个节点
nodes[n]=1;//循环链表：尾指向头
int now=1,prev=1;//从第1个节点开始
while((n--)>1){
for(int i=1;i<m;i++){//数到m停下
prev=now;now=nodes[now];//下一个节点
}
printf("%d ",now);
nodes[prev]=nodes[now];//跳过now节点
now=nodes[prev];//新的now节点
}
printf("%d ",now);
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
list<int>node;
for(int i=1;i<=n;i++)node.push_back(i);//建立链表
list<int>::iterator it=node.begin();
while((n--)>1){//list的大小由STL自己管理
for(int i=1;i<m;i++){//数到m
it++;
if(it==node.end())it=node.begin();//循环：到末尾再回头
}
cout<<*it<<' ';
list<int>::iterator next=++it;
if(next==node.end())next=node.begin();//循环链表
node.erase(--it);//删除这个节点，node.size()自动减1
it=next;
}
cout<<*it;
return 0;
}