约瑟夫环经典问题（c语言利用数组和指针解决）

问题描述

现在有m个人首尾相连围成一圈将他们一次编号为：1，2，3…n,然后从编号为1的人开始报数 1、2、3…n,报到n的这个人将离开队列，然后按照循环队列从下一个人从新按照以上规则报数。

如此循环下去求最后获胜者的编号是多少？并讲每次出列的人的编号一次打印出来。

举一个简单的例子：现在有6个人围成一圈，依次编号为：1、2、3、4、5、6，按照1、2、3报数。

那么出队的顺序就是：3、6、4、2、5。

最后留下的就是1号。

解题方法

c语言数组解决代码以及思想如下：

int main()
{
		int people[128] = { 0 };//创建一个数组 初始化值都为0
		int m, remain, num_now = 0, n;//m 总人数 
		// remain 剩余人数 
		// num_now 目前报的数字
		int* p = people;//p工作指针 初始指向第一个人
		printf("请输入总人数m和报数循环n;\n");
		scanf("%d%d", &m, &n);
		remain = m;
		for (int i = 0; i < m; i++) {//给n个人编号 1 2 3 4 ... m
			people[i] = i + 1;//编号
		}
		while (remain > 1) {//只要剩下的人数大于1就仍然循环报数
			p = people;//每次循环完都从第一个人开始
			while (p != &(people[m])) {//p指针不指向最后一个人就沿着数组地址空间遍历
				if (*p == 0) {//当前位置的人已经被逻辑删除
					p++;//工作指针直接后移 不报数
				}
				else {//当前位置有人
					num_now++;//报数
					if (num_now == n) {//报数报到n
						num_now = 0;//报数置零，下一个重新从1报数
						printf("%d出列  ", *p);//打印出列人的序号
						*p = 0;//当前位置的人作逻辑删除
						remain--;//剩余人数-1
					}
					p++;//工作指针后移
				}

			}
		}
		printf("  最后剩余的人的编号是：");
		for (int i = 0; i < m; i++) {//便利数组中没有被逻辑删除的人的序号并打印出来
			if (people[i] != 0) {
				printf("%d", people[i]);
				break;
			}
		}
		return 0;
}

运行结果

总结

以上只是我用c语言数组以及指针的思想解决的步骤，希望能够在c语言学习中帮助到大家。

当然学过数据结构的小伙伴还可以尝试用循环链表来解决，解题过程可能会更加直观。