欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

经典算法--约瑟夫环问题的三种解法

程序员文章站 2022-04-21 19:04:55
...

约瑟夫环问题,这是一个很经典算法,处理的关键是:伪链表

问题描述:N个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,报到m的人出圈;如此往复,直到所有人出圈。(模拟此过程,输出出圈的人的序号)

在数据结构与算法书上,这个是用链表解决的。我感觉链表使用起来很麻烦,并且这个用链表处理起来也不是最佳的。

我画了一个图用来理解:

经典算法--约瑟夫环问题的三种解法

有如下问题需要首先考虑:

1、“圈”怎样形成?

    以上图为例:下标从0开始,当下标为11的时候,在加1,就应该回到0。

    index = (index+1) % count;

2、怎样处理?数组or链表or其他方法?

    链表使用起来很笨重,我们有循环数组的方法。

解法一程序分析:

循环的开始和结束:循环的结束取决于圈内是否还有“人”,可以用一个变量alive表示初始人数,每一次出圈,alive-1.判断alive是否非0即可。

    while(alive > 0)

每一次循环,就是“过”一个人,但是,这个人有两种不同的状态:在圈内和不在圈内;在圈内就报数,number+1,不在圈内就不参与报数,number不变。

假设有N个int元素的数组,每一个int元素表示一个“人”;并且,取值为0和1, 1表示在圈内,0表示不在圈内,所以,如果这个人在圈内,number+1;如果这个人不在圈内,number+0。那么,在报数的时候,不需要考虑这个人在不在圈内就行(每一个人都需要加1或加0,所以,可以在这块优化一下程序)。

void joseph(int count, int doom) {
	int alive = count;		//幸存人数 
	int number = 0;			//计数,当number==doom时,淘汰这个人 
	int index = 0;			//下标,为总人数-1 
	int *circle = NULL;		//根据需求设为循环数组,存储每个人 

	//用calloc()函数申请得到的空间,自动初始化每个元素为0
	//所以,0表示在这个人在约瑟夫环内,1表示这个人出圈,即“淘汰” 
	circle = (int *) calloc(sizeof(int), count);

	//只要幸存人数大于0,则一直进行循环 
	while(alive > 0) {
		number += 1- circle[index];	//每轮到一个人报数,不管是"0"还是"1"都进行计数 
		if(number == doom) {		//当number==doom时,就要淘汰当前这个人
			/*
				淘汰一个人需要做四步操作:
					1、输出这个人的位置 
					2、把这个人的状态从在圈内"0"改为不在圈内"1" 
					3、幸存人数alive-- 
					4、 计数器number归零 
			*/ 
			alive == 1 ? printf("%d", index+1) : printf("%d,", index+1);
			circle[index] = 1;
			alive--;
			number = 0;
		}
		//与总人数count取余,则可以使index在0~count-1之间 一直循环,达到循环数组的目的 
		index = (index +1) % count;	
	}
	printf("\n");

	free(circle);		//结束后一定要释放circle所申请的空间 
}

经典算法--约瑟夫环问题的三种解法

解法二程序分析:

解法二在解法一的基础上进行了优化,对出圈的人的节点进行删除,可以减少时间复杂度。

假设,要删除的节点下标为curIndex,其前驱节点下标为preIndex;

    circle[preIndex] = circle[curIndex];

    假设要删除的节点下标curIndex=3,那么circle[2] = circle[3] ,circle[2]  = 4,circle[2]之前等于3,现在等于4。即下标为3的第四个人已经被删除了。

怎样遍历?

    preIndex = curIndex;

    curIndex = circle[curIndex];

但是,在出圈的时候,curIndex 和preIndex 的变化有别于上面的操作:

出圈时,curIndex 需要后移,preIndex 应该不动!

每次循环,直接报数,因为被删除的人(例如上面的第四个人)不可能进行报数了。

void joseph(int count, int doom) {
int alive = count;				// 幸存人数
	int number = 0;				// 报数的数
	int curIndex = 0;			// 当前人下标
	int preIndex = count - 1;   // 前一个人下标
	int *circle = NULL;
	int index;

	circle = (int *) malloc (sizeof(int) * count);
	//对circle数组进行初始化 
	for(index = 0; index < count; index++) {
		circle[index] = (index + 1) % count;
	}

	while(alive > 0) {
		number++;
		if(number == doom) {
			alive == 1 ? printf("%d", curIndex+1) : printf("%d,", curIndex+1); 
			alive--;
			number = 0;
			circle[preIndex] = circle[curIndex];	//出圈操作 
		} else {
			preIndex = curIndex;	//处理下一个人 
		}
		curIndex = circle[curIndex];
	}

	free(circle);
}

经典算法--约瑟夫环问题的三种解法

解法三程序分析:

解法三里没有进行number报数,而是直接计算出需要移动的人数,然后定位到要出圈的人。

num = doom % alive - 1;

for(index = 0; index < (num == -1 ? alive - 1 : num); index++) {
preIndex = curIndex;
curIndex = circle[curIndex];
}

void joseph(int count, int doom) {
	int alive = count;	// 幸存人数
	int curIndex = 0;			// 当前人下标
	int preIndex = count - 1; // 前一个人下标
	int *circle = NULL;
	int index;
	
	circle = (int *) malloc(sizeof(int) * count);
	for(index = 0; index < count; index++) {
		circle[index] = (index + 1) % count;	// 初始化链表
	}
	
	while(alive > 0) {	// 只要还有幸存者,就继续“杀”
		int num = doom % alive - 1; // 直接计算出需要移动的人数,
		// 直接定位到要出圈的人
		for(index = 0; index < (num == -1 ? alive - 1 : num); index++) {
			preIndex = curIndex;
			curIndex = circle[curIndex];
		}
		// 该人出圈!
		alive == 1 ? printf("%d", curIndex+1) : printf("%d,", curIndex+1);  
		alive--;
		circle[preIndex] = circle[curIndex]; // 真正的出圈操作!
		curIndex = circle[curIndex]; // 继续处理下一个人
	}
	// 这个算法比normalJoseph.c效率提高30%!
	
	free(circle);
}

经典算法--约瑟夫环问题的三种解法

GitHub源码地址:

https://github.com/yangchaoy259189888/JosephRing/

相关标签: 约瑟夫环 算法