程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言單向循環鏈表解決約瑟夫問題

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

編輯:關於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;
}

運行實例:


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved