dw建设网站,物流网站建设推广,北京信息,app如何推广题目描述
有#xff4e;个人依次围成一圈#xff0c;从第#xff11;个人开始报数#xff0c;数到第#xff4d;个人出列#xff0c;然后从出列的下一个人开始报数#xff0c;数到第#xff4d;个人又出列#xff0c;…#xff0c;如此反复到所有的人全部出列为止。…题目描述
有个人依次围成一圈从第个人开始报数数到第个人出列然后从出列的下一个人开始报数数到第个人又出列…如此反复到所有的人全部出列为止。设个人的编号分别为12…n打印出列的顺序。
输入
n和m。
输出
出列的顺序。
样例输入
4 17
样例输出
1 3 4 2
解决方案
一.使用队列
实现思路
建立队列。队列长度与圆圈人数相同。队列按顺序赋序号初值。
对每个人的编号都要做一个标记。这个标记可以用 0 和 1 。
0表示还没有出列1表示已经出列了。
从队首查询队列。取队列的第一个元素。如果这个元素的标记是0的话计数一次。
如果是1的话直接弹出。
对标记为0的情况进行更细致的讨论
如果当前计数不是出列数的倍数将队首元素追加在队尾同时弹出队首元素
如果当前计数是出列数的倍数将队首元素输出、追加在队尾并将元素编号对应的标记赋值为1同时弹出队首元素。
此处不用考虑某个编号是否已经出列、用不用追加在队尾直接追加在队尾就可以。因为对任意一个队首元素会先进行标记是否为0的判断。如果标记为0则做进一步处理如果为1则直接弹出。
判断查询这个循环终止的条件每次输出一个数另一个计数变量自加一下。当这个计数变量与总人数正好相等时说明所有人已经全部输出。循环结束。
代码部分
#include iostream
#include cstring
#include queue
using namespace std;
const int N 1e5;
int a[N];
int main()
{int n, m;cin n m;int cnt 0;//计数int cntsum 0;//已经出队的人数计数queueintq;//定义队列for (int i 1; i n; i)q.push(i);//队列赋值int head;//队首元素的定义方便书写while (!q.empty()){if (cntsum n)break;//如果已经出队的人数与总人数相等终止循环head q.front();//队首元素每次赋初值if (a[head] 0)//如果还未曾出队执行更精确的操作{cnt;//如果还未曾出队计数。if (cnt % m ! 0)//如果当前计数不是出队数的倍数{q.push(head);//将队首元素追加到队尾}else if (cnt % m 0)//如果当前计数是出队数的倍数{cout head ;//输出队首元素q.push(head);//将队首元素追加到队尾cnt 0;//计数重新开始a[head] 1;//编号已经出队做标记cntsum;//已经出队的人数计数。}}//如果出队了不执行if语句体直接弹出//如果没出队执行完更精确的操作之后也要弹出队首元素//综上不管编号是否出队都需要弹出队首元素。q.pop();}return 0;
}
