首页 > 代码库 > POJ读书笔记6.1 - 约瑟夫问题 2746

POJ读书笔记6.1 - 约瑟夫问题 2746

http://blog.csdn.net/pipisorry/article/details/39271139

问题描述:

约瑟夫生死问题的描述有三:

【其一】据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

【其二】17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。

【其三】个人,编号,从0开始报数,报到的退出,通常取。剩下的人继续从0开始报数,报到的退出,如此往复。求最终胜利者的编号。

 

解决算法:

循环链表算法原理:

题目中个人围成一圈,因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员,其一为指向下一个节点的指针,以构成环形的链;其二为该节点在最初环中的序号标记。从第一个节点处开始计数,每数到时,将当前节点删除,表示该人已被扔下海了。这样循环计数直到有最后一个节点为止。

顺序表算法原理:

为了节省空间复杂度,采用线性表来实现。以动态数组元素代替循环链表节点的算法实现。考虑:动态数组的申请、使用、回收三原则。用个元素数组来存放结果,初始化全为1,如果这个人被丢到海里了,就把对应位置的元素置为0;用一个变量依次对数组里不为0的元素计数,数到则把对应位置的数组元素置0。循环控制可以用取余预算实现。

低复杂度算法原理

无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(mn)。我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程。稍微改变问题描述:n个人,编号0~n-1,从0开始报数,报到m-1的退出,剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人,编号一定是(m-1)%n,出列之后,剩下的n - 1个人组成了一个新的约瑟夫环,以编号为k  = m%n的人开始:


并且从开始报0。把编号做一下转换:

                

变换后就完完全全成为了n - 1个人报数的子问题,那么根据上面这个表把这个变回去则刚好就是n个人情况的解。(如果一个人在n-1时的报数为x,则他在n时的报数为x’)

如何知道n个人报数的问题的解?只要知道n-1个人的解就行了。n-1个人的解?当然是先求n-2的情况。这显然就是一个倒推问题。

递推公式:令表示个人玩游戏报退出最后胜利者的编号,最后的结果自然是f[n]。

递推公式


         


code:

/*	数组算法(有删除元素)	O(mn)	*/
static int jonseArray(int n, int m) {
	int *jones = new int[n];
	for(int i=0; i<n; i++)
		jones[i]=i+1;
	int t=0;
	for(int left=n; left>=1; left--) {			//剩余人数
		t=(t+m-1)%left;							//将要除去的编号
		//printf("%d ", jones[t]);
		for(int j=t+1; j<=left-1; j++)
			jones[j-1]=jones[j];
	}
	return jones[0];
}

/*	数组算法(无删除元素)	O(mn)	*/
static int jonseArray2(int n, int m){
	int *a = (int *)malloc(sizeof(int) * n);
	for(int i = 0; i < n; i++)
		a[i] = 1;

	int current = 0;
	for(int lose_cnt = 0; lose_cnt < n - 1; lose_cnt++){
		int call_num = 1;										//重新报数
		while(call_num < m){
			current = (current + 1) % n;
			while(a[current] == 0)								//跳过已划出的
				current = (current + 1) % n;
			call_num++;
		}
		a[current] = 0;											//划出一个
		current = (current + 1) % n;							//current指向下一个
		while(a[current] == 0)
			current = (current + 1) % n;
	}

	for(int i = 0; i < n; i++){
		if(a[i] == 1)
			return i + 1;
	}
}
/*	数组算法(无删除元素)	O(mn)	*/
static int jonseArray3(int n,int m){
	int a[300];
	for(int i=0;i<n;i++)
		a[i]=1;

	int i = 0, j = 0, k = 0;
	while(k!=n-1){
		if(a[i]==1){
			j=j+1;
			if(j==m){
				a[i]=0;
				k++;
				j=0;
			}
		}
		i = (i + 1) % n;
	}
	for(int i=0;i<n;i++){
		if(a[i]==1)
			return i + 1;
	}
}
/*	链表算法(双循环链表)	O(mn)	*/
typedef struct jonseNode{
	int code;									//编号(从0开始)
	struct jonseNode *next;
	struct jonseNode *pre;
}jonseNode;
static int jonseList(int n, int m){
	jonseNode *jonseMaxNum;						//最大code值的点作为头结点
	assert(jonseMaxNum = (jonseNode *)malloc(sizeof(jonseNode)));
	jonseMaxNum->code = n - 1;
	jonseMaxNum->next = jonseMaxNum;
	jonseMaxNum->pre = jonseMaxNum;

	for(int i = n - 2; i >= 0; i--){			//头插法插入其它结点
		jonseNode * jonseI;
		assert(jonseI = (jonseNode *)malloc(sizeof(jonseNode)));
		jonseI->code = i;
		jonseI->next = jonseMaxNum->next;
		jonseMaxNum->next = jonseI;
	}

	jonseNode *current_pre = jonseMaxNum;
	jonseNode *current;
	for(int i = 1; i <= n - 1; i++){			//每次除去一个,共除去n-1个
		int call_num = 1;
		current = current_pre->next;
		while(call_num++ < m){
			current_pre = current;
			current = current->next;
		}
		current_pre->next = current->next;
		//printf("%d\n", current->code);
		free(current);
	}

	return current_pre->code + 1;
}
/*	最优算法(低复杂度算法)	*/
static int jonseOptimal(int n, int m){
	int final = 0;
	for(int total = 2; total <= n; total++)	//total个人时的winner为final
		final = (final + m) % total;
	return final + 1;
}

测试:

/****************************************************************************/
/*	POJ读书笔记6.1 - 约瑟夫问题 2746	皮皮 2014-9-14		*/
/****************************************************************************/
#include <assert.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>

int main(){
	int n, m;

	//assert(freopen("simulation\\Jonse.in", "r", stdin));
	while(1){
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)
			break;
		printf("%d\n", jonseArray(n, m));
	}
	printf("\n");
	
	//assert(freopen("simulation\\Jonse.in", "r", stdin));
	while(1){
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)
			break;
		printf("%d\n", jonseArray2(n, m));
	}
	printf("\n");
	
	//assert(freopen("simulation\\Jonse.in", "r", stdin));
	while(1){
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)
			break;
		printf("%d\n", jonseArray3(n, m));
	}
	printf("\n");

	//assert(freopen("simulation\\Jonse.in", "r", stdin));
	while(1){
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)
			break;
		printf("%d\n", jonseList(n, m));
	}
	printf("\n");
	
	assert(freopen("simulation\\Jonse.in", "r", stdin));
	while(1){
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)
			break;
		printf("%d\n", jonseOptimal(n, m));
	}
	printf("\n");

	fclose(stdin);
	return 0;
}

测试案例:

5 3
6 2
12 4
8 3
0 0


output:
4
5
1
7


from:

http://blog.csdn.net/pipisorry/article/details/39271139


POJ读书笔记6.1 - 约瑟夫问题 2746