NOIP 提高 2014 第一轮 第 26 题：约瑟夫问题输出出圈顺序

题目

```cpp
#include <cstdio>
const int	SIZE = 100;
int		alive[SIZE];
int		n;
int next( int num )
{
	do
	{
		num++;
		if ( num > n )
			num = 1;
	}
	while ( alive[num] == 0 );
	return(num);
}

int main()
{
	int m, i, j, num;
	scanf( "%d%d", &n, &m );
	for ( i = 1; i <= n; i++ )
		alive[i] = 1;
	num = 1;
	for ( i = 1; i <= n; i++ )
	{
		for ( j = 1; j < m; j++ )
			num = next( num );
		printf( "%d ", num );
		alive[num] = 0;
		if ( i < n )
			num = next( num );
	}
	printf( "\n" );
	return(0);
}
```
输入： 11     3  
输出：_________

请写出程序的输出结果。

答案

3691510411827

题解

考点定位

本题考「约瑟夫问题模拟」,对应大纲 4.2.1 约瑟夫（难度【3】）。

解题过程

n=11 人围圈、每数 m=3 个出圈。next(num) 找下一个存活者，主循环逐个淘汰并输出：

出圈顺序 3,6,9,1,5,10,2,8,4,11,7（手工模拟约瑟夫 J(11,3)）。

答案：3691510411827（按官方答案连写）。

易错提醒

① alive[] 标记存活、next 跳过死者；② 每轮数 m−1 次 next 后输出并标记；③ 首个出圈是 3（从 1 起数）。