题解 | 约瑟夫问题No.2

题目：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。写程序实现上述过程。

测试用例：

输入n,p,m：

8 3 4

0 0 0

输出(数到m的那个人出列):

6,2,7,4,3,5,1,8

利用队列的先进后出的公平的顺序，实现循环报数，比如3号开始报1，报完数后出队，因为3号人报的数不是m，则把3号入队等次报数。

#include<stdio.h>
#include<queue>
using namespace std;

int main() {
	int n, p, m;
	while (scanf("%d %d %d\n", &n, &p, &m) != EOF) {
		if (n == 0 && p == 0 && m == 0)return 0;
		//新建队列存n个小孩编号,从开始报数的小孩编号开始
		queue<int> child;
		int childno = p;
		for (int i = 0; i < n; i++) {
			child.push(childno);
			childno++;
			if (childno > n)childno = 1;//编号不能超过n
		}
		//开始报数
		int say = 1;
		while (1) {
			int temp = child.front();//取出队头元素
			child.pop();//报完数就出队
			if (say == m) {
				say = 1;//重置报数
				if (child.empty()) {//如果是最后一个
					printf("%d\n", temp);
					break;
				}
				printf("%d,", temp);
			
			}
			else {
				say++;
				child.push(temp);//入队

			}
			

		}
	}

	return 0;
}