约瑟夫环问题,n个人围成一圈,依次按1、2.....m来报数,报数值为m的人出圈,求最后出圈的人和出圈的序列

标签: 算法题

约瑟夫环问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.),也就是如下图这个样子:

在这里插入图片描述
简单来讲就是n个人围成一圈,依次按1、2…m来报数,报数到m的出圈,当第一个人出圈后,那么出圈的下一个人则又按1、2…m来报数,如此在一个圈内循环报数,直到全部的人都出去圈。

首先我们定义一个数组num以及n,m; n的数值是圈子人的个数,num数组是用来存储每个人的编号如:1、2、3、4…n,而m则是报数值;比如当j报数值为m时,将其num[j]的值赋为0表示已经出圈,后面再次循环时便通过判断跳过值为0的。
废话不多说先放出主函数的代码部分:

#include <stdio.h>
#define N 100


int main() {

	int num[N];
	int n, m;
	printf("请输入总人数和报数值:");
	scanf("%d%d", &n, &m);
	
	//给每个数组赋上编号的值
	for(int i = 0; i < n; ++i) {
		num[i] = i+1;
	}
	
	printf("依次出环的顺序为:");
	
	//josef就是实现的关键函数,函数有一个返回值返回最后出圈的人的编号值,在函数内也实现了打印每个出队的编号
	int final = josef(num, n, m);
	
	printf("\n最后出的人为原先的%d号", final);
    return 0;
}

下面给出josef函数的实现:

int josef(int num[],int n,int m)
{
	//定义最后一个出圈人的编号值final
	int final;

	int count, i , j = 0;
	
	
	//最外层的循环:每一次循环便实现出圈一个人,直到全部出圈,并且每次将出圈人的编号打印出
	for(count = 0; count < n; ++count) {
		i = 1;
		
		// 每次while一次循环表示报一次数,i来记录报数值,当遇到报数值为m的时候跳出循环
		while(i < m) {
			while(!num[j])   j=(++j)%n; //判断是否为0
			
			i++;
			j = (++j)%n;//
		}
		
		while(!num[j])   j=(++j)%n; 
		
		printf("%d ", num[j]);
		if(count == n-1) {
			final = num[j];	
		}
		//在设置为0的之前,先将其打印出,并且判断是不是最后一个出圈
		
		num[j] = 0;
	}
	return final;
}

比如我我们输入n和m的值分别为 53 来模拟一次输出:
在这里插入图片描述
一次循环后(置为0的表示已出圈):
在这里插入图片描述
每循环一次置报数为3的为0, 当到第三次循环时,由2开始从1报数:
在这里插入图片描述
直到后面第4、5次循环结束都为0,最后输出结果就是:
在这里插入图片描述
比如我们在输入100 9:
在这里插入图片描述

版权声明:本文为qq_39414417原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39414417/article/details/104987018