题目描述:
假设共有number个人围成一个“环”,编号分别为1,2,3,……,number;假设开始报数的人的编号为start,报数为k的人 出圈;然后再从他的下一个人起重新报数,报数为k的人出圈;如此循环下去,直到所有人全部出圈为止。当任意给定人数number、起始报号的人的编号为start,报号为k的人出圈,设计算法求number个人出圈的次序。
示例
输入:number = 10,start = 3,k = 7;
输出:9,6,4,3,5,8,2,7,10,1;
思路
所有人排成一排,每次由站在(最左边)排头的人报数(若不是站在派头的人报数,比如由站在第n位的人报数,则把前面n-1个人按照次序放到队伍的最后面), 若站在排头的人不符合出圈的要求,就把排头的人出队列,并站在队尾,队列全部前移一个位置。再由排头的人进行报数,以此类推。
code(主要代码片段)
vector<int> Joseph_Ring(int number, int start, int k) //约瑟夫环
{
vector<int> ans;
deque<int> que;
for (int i = 1; i <= number; ++i) //将number个人依次放入一个deque队列中
{
que.emplace_back(i);
}
int count = 1;
while (count < start)
{
//只要还没有达到第start个人,就依次把最前面的元素放到最后面去
que.emplace_back(que.front());
que.pop_front();
++count;
}
while (que.size() != 0)
{
int step = 1;
while (step < k)
{
//只要还没报数报到第k个,就把当前的元素放到que的最后面去
que.emplace_back(que.front());
que.pop_front();
++step;
}
ans.emplace_back(que.front()); //某个元素报数为k,将其添加到答案中,
que.pop_front(); //将其在队列中删除
}
}
版权声明:本文为wk131421原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。