问题描述：
有n个人，编号为1~n，按顺序围成一圈，从第一个人开始报数，到第m个人出列，再由下一个人重新从1开始报数，数到m再出列，直到所有人都出列，依次输出所有出列的人的编号。
输入：两个整数n，m，1<=m,n<=100
输出：n个整数，按顺序输出编号
动态链表
点击查看代码
#include <bits/stdc++.h>
struct node{
int data;
node* next;
};
int main(){
int n,m; scanf("%d %d", &n, &m);
node* head, *now, *p, *prev;
head = new node; head->data=1; head->next=NULL;
now = head;
for(int i=2;i<=n;i++){
p = new node; p->data=i; p->next=NULL;
now->next = p;
now = p;
}
now->next = head;
now = head;
while((n--)>1){
for(int i=1;i<m;i++){
prev = now;
now = now->next;
}
printf("%d ", now->data);
prev->next = now->next;
delete now;
now = prev->next;
}
printf("%d", now->data);
delete now;
return 0;
}
静态链表
用结构体实现单向静态链表
点击查看代码
#define N 100
#include <bits/stdc++.h>
struct node{
int id, nextid;
}nodes[N];
int main(){
int n,m; scanf("%d %d", &n,&m);
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;
while((n--)>1){
for(int i=1;i<m;i++){
prev=now;
now=nodes[now].nextid;
}
printf("%d ", nodes[now].id);
nodes[prev].nextid = nodes[now].nextid;
now=nodes[prev].nextid;
}
printf("%d", nodes[now].id);
return 0;
}
用结构体实现双向静态链表
点击查看代码
#define N 100
#include <bits/stdc++.h>
struct node{
int id;
int previd, nextid;
}nodes[N];
int main(){
int n,m; scanf("%d %d", &n,&m);
for(int i=1;i<=n;i++){
nodes[i].id=i;
nodes[i].previd=i-1;
nodes[i].nextid=i+1;
}
nodes[n].nextid = 1;
nodes[1].previd = n;
int now = 1;
while((n--)>1){
for(int i=1;i<m;i++){
now = nodes[now].nextid;
}
printf("%d ", nodes[now].id);
nodes[nodes[now].previd]=nodes[now].nextid;
nodes[nodes[now].nextid]=nodes[now].previd;
now = nodes[now].nextid;
}
printf("%d", nodes[now].id);
return 0;
}
用一维数组实现静态链表
点击查看代码
#include <bits/stdc++.h>
int nodes[101];
int main(){
for(int i=1;i<=n-1;i++){
nodes[i]=i+1;
}
nodes[n]=1;
int now=1, prev=1;
while((n--)>1){
for(int i=1;i<m;i++){
prev=now;
now = nodes[now];
}
printf("%d ", now);
nodes[prev] = nodes[now];
now = nodes[prev];
}
printf("%d", now);
return 0;
}
STL list
点击查看代码
#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.emplace_back(i);}
list<int>::iterator it = node.begin();
while(node.size()>1){
for(int i=1;i<m;i++){
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);
it = next;
/*
erase后，当前的iter会失效，要么新建一个iterator来保存下一个iter如上面
要么在erase时保留当前iter的自增值
it++的情况下，it本身已经指向下一个有效的iter
node.erase(it++);
if(it==node.end()) it=node.begin();
*/
}
cout<<*it;
return 0;
}