数据结构：约瑟夫环

约瑟夫环
问题描述：约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。程序思路：伪链表，即，用数组实现的链表。

约瑟夫环

问题描述：

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

程序思路：

伪链表，即，用数组实现的链表。

数据结构：约瑟夫环

#include<stdio.h>

#define PERSON_COUNT   100
#define DOOM_NUMBER   8  //每8个人杀一个

void main(void){
	int person[PERSON_COUNT];
	int pre = PERSON_COUNT - 1;
	int cur = 0;
	int doomNumber = 0;
	int i;
	int alives = PERSON_COUNT;

	for(i = 0; i < PERSON_COUNT; i++){    //数组初始化
		person[i] = (i+1) % PERSON_COUNT;
	}

	/*形式1
	for(cur = 0; alives > 0; cur = person[cur]){  //遍历数组
		if(++doomNumber == DOOM_NUMBER){
			printf("%2d被杀死\n", cur + 1);
			alives--;
			doomNumber = 0;               //重新数数
			person[pre] = person[cur];    //删除(杀人)
		}else{
			pre = cur;
		}		
	}
	*/

//形式2
	while(alives > 0){  //遍历数组
		if(++doomNumber == DOOM_NUMBER){   //数8个数
//此处用for和if的区别：如果用for，则表示相关操作要执行多次；但是此处操作只需执行一次，故用if
			printf("%2d被杀死\n", cur + 1);
			alives--;
			doomNumber = 0;               //重新数数
			person[pre] = person[cur];    //删除(杀人)
		}else{
			pre = cur;
		}	
		cur = person[cur];
	}
}

结果如下：

数据结构：约瑟夫环

约瑟夫环

相关推荐