目录
一、问题描述
二、用数组求解
三、用递归求解
一、问题描述
约瑟夫环（Josephus Circle）是一个数学的应用问题：已知 n 个人（分别用编号 0, 1, 2, …, n – 1 表示）围坐在一张圆桌周围。从编号为 0 的人开始报数，数到 m 的那个人出圈，他的下一个人又从 1 开始报数，数到 m 的那个人又出圈，依次规律重复下去，直到剩余最后一个胜利者。例如，有 10 个人围成一圈进行此游戏，每个人的编号为 0 ~ 9，规定数到 3 的人出圈，则游戏过程如下所示：
0，1，[2]，3，4，5，6，7，8，9
0，1，[2]，3，4，[5]，6，7，8，9
0，1，[2]，3，4，[5]，6，7，[8]，9
0，[1]，[2]，3，4，[5]，6，7，[8]，9
0，[1]，[2]，3，4，[5]，[6]，7，[8]，9
[0]，[1]，[2]，3，4，[5]，[6]，7，[8]，9
[0]，[1]，[2]，3，4，[5]，[6]，[7]，[8]，9
[0]，[1]，[2]，3，[4]，[5]，[6]，[7]，[8]，9
[0]，[1]，[2]，3，[4]，[5]，[6]，[7]，[8]，[9]
所以出圈的顺序是：2，5，8，1，6，0，7，4，9。最终剩下 3 号，3 号是胜利者。
二、用数组求解
#include #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)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 的两种情况。
当第 i 个人出圈后，剩下的 n – i 个人就组成了新的约瑟夫环。
#include int josephus(int n, int m, int i){if (i == 1)return (m - 1) % n;elsereturn (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;}