C語言單向循環鏈表解決約瑟夫問題

據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人抓到，於是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友並不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），並殺掉第k個人。接著，再越過k-1個人，並殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什麼地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡游戲。 17世紀的法國數學家加斯帕在《數目的游戲問題》中講了這樣一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免於難，於是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數，每數到第九個人就將他扔入大海，如此循環進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。 *問題分析與算法設計 約瑟夫問題並不難，但求解的方法很多；題目的變化形式也很多。這裡給出一種實現方法。 題目中30個人圍成一圈，因而啟發我們用一個循環的鏈來表示。可以使用結構數組來構成一個循環鏈。結構中有兩個成員，其一為指向下一個人的指針，以構成環形的鏈；其二為該人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數，每數到9時，將結構中的標記改為0，表示該人已被扔下海了。這樣循環計數直到有15個人被扔下海為止。 約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數，第M個將被殺掉，最後剩下一個，其余人都將被殺掉。例如N=6，M=5，被殺掉的人的序號為5，4，6，2，3。最後剩下1號。 假定在圈子裡前K個為好人，後K個為壞人，你的任務是確定這樣的最少M，使得所有的壞人在第一個好人之前被殺掉。 解決方案：

/*************************************************************************
	> File Name: josefu.c
	> Author: Baniel Gao
	> Mail: [email protected] 
	> Blog: blog.csdn.net/createchance 
	> Created Time: Thu 19 Dec 2013 03:08:21 PM CST
 ************************************************************************/
#include 
#include 

typedef struct josefu
{
	int data;
	struct josefu *next;
} josefu_list;

josefu_list *josefu_init(int num);
josefu_list *josefu_begin(josefu_list *list, int rule);
josefu_list *josefu_node(int num);
int josefu_free(josefu_list *list);

int main(void)
{
	josefu_list *list;
	int num, rule;
	
	puts("Please input number and rules: ");
	scanf("%d%d", &num, &rule);
	list = josefu_init(num);
	list = josefu_begin(list, rule);

	josefu_free(list);

	return 0;
}

josefu_list *josefu_init(int num)
{
	int i;
	josefu_list *new;
	josefu_list *list = josefu_node(1);

	for(i = num; i > 1; i--) {
		new = josefu_node(i);
		new->next = list->next;
		list->next = new;
	}

	return list;
}

josefu_list *josefu_node(int num)
{
	josefu_list *p = NULL;

	p = (josefu_list *)malloc(sizeof(josefu_list));
	p->data = num;
	p->next = p;

	return p;
}

josefu_list *josefu_begin(josefu_list *list, int rule)
{
	int counter;
	josefu_list *tmp = NULL;

	for(counter = 1; list->next != list; counter++) {
		if(counter == rule - 1) {
			tmp = list->next;
			list->next = tmp->next;
			free(tmp);
			counter = 0;
			josefu_show(list);
		}
		list = list->next;
	}

	return list;
}

int josefu_show(josefu_list *list)
{
	josefu_list *p = list;

	if(list == NULL)
		return 0;

	do {
		printf("%5d",p->data);
		p = p->next;
	} while(list != p);
	putchar('\n');
}

int josefu_free(josefu_list *list)
{
	free(list);

	return 0;
}

運行實例：