D-OJ刷题日记：约瑟夫环问题 题目编号:657

设有编号为1，2，…，n的n个人围成一个圈，给定一个密码m，从第一个人开始报数，报到m是停止报数，报m的人出圈，再从他的下一个起重新报数，报到m时停止报数，报m的出圈，…，如下下去，直到所有人全部出圈为止。键盘输入n和m的值，请设计程序输出n个人出圈的次序。

输入初始圈中的人数n，占一行
输入密码m，占一行

输出出圈的n个人的次序，以空格隔开，最后一个元素后有空格

10
3

3 6 9 2 7 1 8 5 10 4 

思路：

看图

程序代码：

#include
#define MAXSIZE 100
using namespace std;
int main()
{
	int cirArr[MAXSIZE] = {0};//数组初始化
	int n;//人数
	int m;//密码
	cin >> n;
	cin >> m;
	for (int i = 0; i < n; i++)
		cirArr[i] = i + 1;//存入原始序号
	int i = 0;//i代表数组下标的起始位置
	while (n > 1)
	{
		//1、计算出圈人下标
		i = (i + m - 1) % n;//数组中出圈人的下标
		cout << cirArr[i]<<' ';
		//2、删除出圈元素，总人数减一
		for (int j = i + 1; j < n; j++)
		{
			cirArr[j - 1] = cirArr[j];//前移删除a[i]
		}
		n--;
		//3、形成循环数组
		if (i == n)
		{
			i = 0;//如果到达数组末端就从头开始
		}
	}
	cout << cirArr[i]<<' ';//输出最后一个人位置
	return 0;
}