OJ刷题记录：约瑟夫环问题 题目编号:657

约瑟夫环问题 题目编号: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

解题思路： 重点在得对数组进行环状的循环遍历，并且已经出队的人不在进行判断。 首先使用输入的总人数 n 声明一个长度为 n 的数组，将数组中的元素赋值为 1 ~ n 。对数组进行首尾循环的遍历。定义一个计数器 count ，用来记录当前报数的人的位置，若等于 m , 则将数组元素输出，此时将计数器 count 重置为 0 ，因为接下来要从下一个人重新开始报数，并且将数组元素赋值为 -1 ，表示此人已经出列，总人数 n 也减少 1 ，在接下来的循环中遇到 -1 则 continue , 不再进行判断。直到 n 为 0 ，退出循环。出列顺序输出完成。 数组环状循环遍历实现： 使用循环变量 index , 如果 index 小于数组最大下标值，则 index 加 1，往后遍历；若 index 大于或者等于数组最大下标值，则将其取最大下标的余，计算出数组环状时此时应该到达的下标值。

通关代码：

#include <iostream>

using namespace std;

int main() {
	int n, m, count = 0, index = 0;
	
	cin >> n >> m;
	
	const int LEN = n;
	int arr[LEN];
	
	for (int i = 0; i < LEN; i++) {
		arr[i] = i + 1;
	}
	
	while (n > 0) {
		if (index >= LEN) {
			index = index % LEN;
		}
		
		if (arr[index] != -1) {
			count++;
		}
		if (count == m) {
			count = 0;
			cout << arr[index] << ' ';
			arr[index] = -1;
			n--;
		}
		
		index++;
	}
	
	return 0;
} 

毕。