C语言经典算法问题 “约瑟夫环” 的个人理解与分享

这篇文章，是用来分享我自己对c语言一些经典的习题的理解，与解决方法 其实是作为练习笔记 而写，仅供参考

约瑟夫环问题

n个人围成一圈，从第一个人开始报数,数到 m的人出列，再由下一个人重新从1开始报数，数到 m的人再出圈，依次类 推，直到所有的人都出圈，请输出依次出圈人的编号。

这道题的解决思路，主要是通过大小为n的数组来表示n个人，并通过给每个数组元素来赋值0和1，来表示淘汰和存活的人员编号（若为1则淘汰，为0则存活），再建立一个元素（如 j）来表示当前淘汰的人数，后建立循环，直到仅剩一人存活后跳出

首先，建立一些元素和数组，用来表示人员总数，一次跳过的人数，与淘汰人数的记录

int a, b, i = 0, count = 1, j = 0; //count用来报数
scanf("%d %d", &a, &b); //a代表所有的人数，b代表一次跳过的人数
int s[a];

之后，使用for循环，将所有数组赋值为0（存活状态）

for (i = 0; i < a; i++) {
	s[a] = 0;
}
i = 0; //循环结束后将i重新赋值为0 ，以便后续的使用

接下来，使用while循环和if-else语句来进行对人员的循环淘汰

while (1) {
	if (j == a - 1)
		break; //当只剩下一个人时，跳出循环
	if (s[i] == 1)
		i++; //如果该人为淘汰的状态，则跳过该人
	else {
		if (count == b) { //满足被淘汰的条件
			s[i] = 1; //设置淘汰条件
			j++; //淘汰人数加一
			printf("%d ", i);
			count = 1; //重置
			i++; //移动至下一个人
		}
		else { //不满足被淘汰的状态
			count++;
			i++;
		}
	}
	if (i == a) //由于数组下标从0开始，所以当i=n时，就是移动到第一个人了
		i = 0;
}

最后，使用for循环，输出存活的人的代号，查询到后break跳出

for (i = 0;; i++) {
	if (s[i] == 0) {
		printf("%d", i);
		break;
	}
}

最终答案为

#include 
int main(void) {
	int a, b, i = 0, count = 1, j = 0;
	scanf("%d %d", &a, &b);//a代表所有的人数，b代表一次跳过的人数
	int s[a];
	for (i = 0; i < a; i++) {
		s[a] = 0;
	}
	i = 0;//将i重新赋值为0 ，以便后续的使用
	while (1) {
		if (j == a - 1)
			break;
		if (s[i] == 1)
			i++;
		else {
			if (count == b) {
				s[i] = 1;
				j++;
				printf("%d ", i);
				count = 1;
				i++;
			}
			else {
				count++;
				i++;
			}
		}
		if (i == a)
			i = 0;
	}
	printf("\n存活序号");
	for (i = 0;; i++) {
		if (s[i] == 0) {
			printf("%d", i);
			break;
		}
	}
	return 0;
}

注：在vs中，这串答案里的printf所输出的文字，在编译器上会以乱码形式出现，尚不清楚原因，不过答案没有任何差错