站成一圈,从1报数,报数为m则出列,求出列序列
1.循环链表
设计思路
用循环链表实现逻辑结构
让从第一个开始遍历,
每来到一个人
报数count++
若报m即count%m=0,则删除这个人
来到下一个人
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
}*Pointer;
int main(int argc, char** argv) {
int n=0,m=0;
cin>>n>>m;//n个人,报数m
//头节点
Node* head=NULL;
head=new Node;
Node* p=head;
//链表赋值
for(int i=0;i<n;i++){
p->next=new Node;
p=p->next;
p->data=i+1;
}
//头尾相连
p->next=head->next;
int countDeath=0;
int i=1;
Node* q=NULL;
//p指向报数者前一个节点 ,q指向出列者
while(n-countDeath>0){
if(i%m==0){
cout<<p->next->data<<" ";
q=p->next;
p->next=q->next;
delete q;
countDeath++;
}else{
p=p->next;}
i++;
}
return 0;
}
2.顺序表(数组实现)
设计思路
用一个数组储存n个人
用模运算,将这个长度为n的数组想象成一个圆环。
1,2,3,4,···,n,1,2,3,···n,···
数组下标是
k
k
k,考虑成 (k%m),代表
k
k
k号人
其中储存1或0,1代表有人,0代表出列。
i用来记录报数。
每来到一个人a[k%m]==1
报数i++
如果
i
=
=
m
i==m
i==m,出列,a[k%m]=0;
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
int n=0,m=0;
cin>>n>>m;
int* a=new int[n];
//一个一个站成一圈
int i=1;
for(i=0;i<n;i++){
a[i]=i+1;
}
i=1;
int k=0;
int death=0;
while(death<n){
if(k==n)k=0;//索引模运算
if(k<n){
if(a[k]!=0){
if(i%m==0){
cout<<a[k]<<" ";
a[k]=0;
death++;
}
i++;//报数
k++;
}else{//走了的人不报数
k++;
}
}
}
return 0;
}