NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 26 题

#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 输出：_________

约瑟夫环n=11,m=3出列顺序：3 6 9 1 5 10 4 11 8 2 7。

next函数跳过已出列(alive[num]==0)的人，形成循环。

约瑟夫环

n=11,m=3：从1开始每数到3的人出列。 手动模拟过程(用数组标记已出列)： 3,6,9,1,5,10,4,11,8,2,7 输出：3 6 9 1 5 10 4 11 8 2 7