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