约瑟夫环（Josephus Circle）

一、问题描述

所以出圈的顺序是：2，5，8，1，6，0，7，4，9。最终剩下 3 号，3 号是胜利者。

二、用数组求解

#include <stdio.h>

#define N 100000  // 最大数

// 用一维数组 is_out 来标识这 N 个人的状态，0 表示没有出圈，1 则表示出圈了。
int is_out[N] = { 0 };  

int main()
{
	int n = 0;  // 游戏参与的人数
	int m = 0;  // 数到 m 时出圈
	scanf("%d%d", &n, &m);
	int count = 0;  // 出圈的人数
	int num = 0;  // 报数器，当报到数字 m 时出圈
	int i = 0;  // 从编号为 0 的人开始报数
	// 一、淘汰 n - 1 个人
	while (count < n - 1)  
	{
		if (is_out[i] == 0)  // 未出圈的人报数
		{
			num++;  
			if (num == m)  // 报到数字 m 的人出圈
			{
				printf("%d ", i);
				is_out[i] = 1;
				count++;
				num = 0;  // 有人出圈后，报数器重置为 0
			}
		}
		// i = (i + 1) % n;  // i + 1，并保证 i 的取值范围是：0 ~ n-1
		// 或者：
		i++;
		if (i > n - 1)
			i = 0;
	}
	printf("\n");
	// 二、输出胜者的编号
	for (i = 0; i < n; i++)
	{
		if (is_out[i] == 0)
			printf("The winner is %d\n", i);
	}
	return 0;
}

三、用递归求解 

定义递归函数：josephus(int n, int m, int i)，它表示在有 n 人的圆桌中，报到数字 m，第 i 个人出圈的编号。

第 1 个人出圈的编号是 (m - 1) % n，因为编号从 0 开始，且有 m <= n 和 m > n 的两种情况。

当第 i 个人出圈后，剩下的 n - i 个人就组成了新的约瑟夫环。

#include <stdio.h>

int josephus(int n, int m, int i)
{
	if (i == 1)
		return (m - 1) % n;
	else
		return (m + josephus(n - 1, m, i - 1)) % n;
}

int main()
{
	int n = 0;
	int m = 0;
	scanf("%d%d", &n, &m);
	int i = 0;
	// 淘汰 n - 1 个人
	for (i = 1; i < n; i++)
	{
		printf("%d ", josephus(n, m, i));
	}
	// 输出胜利者的编号
	printf("\n");
	printf("The winner is %d\n", josephus(n, m, i));
	return 0;
}