[C++知识库]约瑟夫环问题

最近为了教学妹C语言，重新写了一下约瑟夫环问题。
结合代码讲解一下设计思路。

题目描述：
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 num 个人（以编号1，2，3…num分别表示）围坐在一张圆桌周围。从编号为 1 的人开始报数，数到 k 的那个人出圈；他的下一个人又从 1 开始报数，数到 k 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

代码设计思路：写一个传入两个参数的函数，num表示参与游戏的总人数，k表示数到k的幸运儿惨遭淘汰。

核心的循环代码为：

	for (i = 0; counter < num - 1; i++) {
		if (i == num) {
			i = 0;
		}
		if (a[i] == 1) {	// 报数轮到第i人且未被淘汰
			j++;			// 有效人数加一
			if (j == k) {	// 数到第k个活人时
				a[i] = 0;		// 淘汰i号人
				counter++;		// 淘汰人数+1
				j = 0;			// 有效人数归零
				printf("杀死%d\t",i);
			}
		}
	}

这个循环的功能是不断地进行报数，知道出现死者数量达到num-1时跳出循环。此时最后一个生还者即为胜利者。
初始时a[i]均为1，当被淘汰时就将该人状态置为0。此时将不参与报数。
j用来记录现在报的数字，每有一个人报数就进行j++。当j与k相等时进行淘汰。

#include<stdlib.h>
int main() {
	int JosephRing(int a, int b);  // 函数声明
	printf("%d", JosephRing(6, 4));
	return 0;
}


int JosephRing(int num, int k) {
	int a[100];
	int i, j = 0, ans=-1,counter=0;
	for (i = 0; i < num; i++) {
		a[i] = 1;
	}

	for (i = 0; counter < num - 1; i++) {
		if (i == num) {
			i = 0;
		}
		if (a[i] == 1) {	// 第 i人活着
			j++;			// 有效人数加一
			if (j == k) {	// 数到第k个活人时
				a[i] = 0;		// 杀死i号人
				counter++;		// 死人数+1
				j = 0;			// 有效人数归零
				printf("杀死%d\t",i);
			}
		}
	}
	for (i = 0; i < num; i++) {
		if (a[i] == 1) {
			ans = i;
		}
	}
	return ans;
}

以上为完整代码，复制即可运行。

这种做法不一定是最高效的，但我认为是非常符合正常的思维逻辑。有不少变量，编写代码时要明确每个变量的功能。作为C语言初学者入门题比较适合。