一个经典约瑟夫问题的分析与解答

                                            一个经典约瑟夫问题的分析与解答

一、约瑟夫问题的由来

　　约瑟夫问题（Josephus）是由古罗马的史学家约瑟夫（全名Titus Flavius Josephus）提出的。它是一个出现在计算机科学和数学中的经典问题。在计算机编程的算法中，类似问题又称为约瑟夫环。(更多内容，可参阅程序员在旅途)
　　Josephus是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。Josephus将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
　　约瑟夫问题的一般描述形式为：设有编号为1，2，……，n的N个人围成一个圈，从第1个人开始报数，报到M时停止报数，报M的人出圈，再从他的下一个人起重新报数，报到M时停止报数，报M的出圈，……，按照这个规则进行下来，直到所有人全部出圈为止。当任意给定N和M后，构建相关数据结构与算法求N个人出圈的次序。

二、典型例题

　　有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下来的是原来第几号的那个人。

三、分析解答

　　可以采用数组或者循环链表的数据结构来解答这道题目。各有优点。数组实现起来简单，但是逻辑上复杂。循环链接逻辑上简单，实现起来复杂。下面采用两种方法解答此题。

       3.1 采用数组存储数据

　　利用数组保存这N个人的序号，设计两个计数器，一个k作为报数计数器，一个m作为退出人数报数器。从第一个人开始计数（数组下标i=0），计数器k到3后清零，数组元素报到最后的时候再从第一个人开始。每退出一个人，相应的数组元素置0，报数计数时只对非0元素计数，当计数器m到n-1是说明只剩下一个人，这时候算法结束，输出剩下人的编号即可。

#include<stdio.h>
#define NMAX 50

int main(){

	//k 报数计数器
	//m 退出人数计数器
	int i,k,m,n,num[NMAX];

	scanf("%d",&n);

   //给N个人写上序号
	for(i=0;i<n;i++){
		num[i] = i+1;
	
	}

	i = k = m =0;
    // m = n-1  时说明只剩下一个人
	while(m < n -1){
	
		//当前位置的值不为0，则计数，为0代表退出了
		if(num[i] != 0){

			k++;
		}

	//计数器K=3的位置人数退出，退出的位置记为0。计数器归0重新计数。退出人数m+1；
		if(k == 3){
		
			num[i] = 0;
			m++;
			k = 0;
		}

		i++;

		if(i == n){
		
			i = 0;
		}
	}

	//输出最后留下来的那个数
	    i= 0;
		while(num[i] ==0){
		
			i++;
		}

		printf("Left is %d\n", num[i]);
	
		return 0;

}

       3.2 采用循环链表存储数据

　　利用循环链表存储N个人的序号。将报到k=3的节点从循环链表汇总移除，最后只剩下一个节点循环结束，输出剩下人的编号即可。（其中报数器K的值可以自定义）

#include<stdio.h>
#include<stdlib.h>

typedef struct Num_node{

	int data;
	struct Num_node  *next;

}Num_Node;

int main(){

    	//n 总人数，m退出的人数，k报数计数器
    	int n,k;
        Num_Node  *head = NULL , *tail =NULL,  *p = NULL;

		int i=0;
        //输入N，然后初始化链表
    	scanf("%d",&n);
		while(i++<n){
		
				//申请节点所占用的内存空间
				if( (p = (Num_Node *)malloc(sizeof(Num_Node))) == NULL){
				
					printf("memery is not available");
					exit(1);

				}

				p->data = i;
				p->next = NULL;

				//当前申请的是第一个节点
				if(head == NULL){

					head = tail = p;
			
				}else{
					//链尾插值
				
					tail->next = p;
					tail = p;
				
				}
				//如果是最后一个元素，让其指向head:这样就构成了循环链表
				if(i == n){
					tail->next = head;
				}
		}

		//凡是报到k=3的节点就从链表中去除。（这个k可以自己定义，只要K<N就行）
		k = 3;
		p = head;

        Num_Node  *pre_p = NULL; //p的前驱指针，删除p的时候，需要用到这个指针。

		while(p->next != p)  //直到p指向自己，说明只剩下一个元素了。
		{ 
				for(i = 1; i < k; i++)
				{
					pre_p = p;
					p = p->next;
				}
				pre_p->next = p->next;
				free(p);                      // 删除结点，从内存释放该结点占用的内存空间
				p = pre_p->next;      
		}


		printf("Left is %d \n",p->data);

       return 0;
}

三、总结

　　约瑟夫问题是一个经典的计算机与数学问题，由来已久，解法也各异。上面两种方法，分别利用了数组、循环链表数据结构来分析这个题目，虽然都可以解决，但是逻辑上的复杂性却有很大的差异。这其中就能够看出数据结构在解决问题过程中的重要性，合适的数据结构会大大降近解题的难度。