據說著名猶太歷史學家 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; }
