今天給大家講講約瑟夫問題是什么，并且我提供了一種約瑟夫問題的解決辦法。對于不知道約瑟夫是誰的人來說，就更不用提什么是約瑟夫問題了。那么問題來了，約瑟夫是誰，約瑟夫問題又是個什么東西。

首先來個解釋吧，約瑟夫問題，有時也稱為約瑟夫置換，是一個出現在計算機科學和數學中的問題。特別是對于學習過數據結構的人來說，在書上看到解決這個問題的題目，可能都不下5遍吧。在計算機編程的算法中，類似的問題又稱為約瑟夫環或者丟手絹問題。

約瑟夫(Josephus)是誰，約瑟夫是著名的猶太歷史學家，那么約瑟夫問題又是個什么東西呢。其實我并不太清楚約瑟夫的什么生平經歷，但是關于約瑟夫問題，倒是有一個小故事給大家講一講，這個故事就是約瑟夫問題的原型。好了，下面來個大家講故事了，據說在羅馬人占領喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

從上面的故事，大家至少可以知道，約瑟夫雖然是個歷史學家，但是他的數學學的也不賴嘛。

約瑟夫問題并不難，求解的方法也非常的多，我這里提供一個循環鏈表的解決方法，為什么用循環鏈表，因為我看那個故事里面的人都是手拉手圍成一個圓圈的嘛。

下面是我寫的程序源代碼，大家看看，就知道是怎么解決的了：

注：可以通過修改mian()函數中的Start，Count，length這3個參數來改變游戲的規則，大家可以試試。

#include
#include

/*
*功能:約瑟夫問題解決辦法(循環鏈表解決)
*By:AilsonJack
*Date:2014.05.24
*/
#defineerror0
#defineok1

typedefintElementType;
typedefstructCycleListNodeNode;
typedefstructCycleListNode*ptrNode;

structCycleListNode//循環鏈表結點
{
ElementTypedata;//數據區
ptrNodenext;//指向下一個結點
};

//函數聲明
//約瑟夫問題解決辦法(循環鏈表解決)
voidJosephus(ptrNodelist,intstart,intcount,intlength);

//創建循環鏈表頭結點
intCycleList_CreateNode(ptrNode*list);

//初始化循環鏈表,并且最后丟掉鏈表頭結點,鏈表的數據為1->length
voidCycleList_Init(ptrNode*list,intlength);

//刪掉循環鏈表中從表頭數的第position個位置的數據
//最終將頭結點變為刪除前那個結點的下一個結點
voidCycleList_Delete(ptrNode*list,intposition);

//查找循環鏈表中數據元素是Start的結點的位置,并且將該節點設為新的起始結點s
voidCycleList_Find(ptrNode*list,ElementTypeStart);

//打印循環鏈表中的數據
voidPrin_CycleList(ptrNodelist,intlength);

intmain(void)
{
intStart=1;//起始計數位置
intCount=3;//第Count個位置的結點出局
intlength=41;//循環鏈表的長度
ptrNodelist;

CycleList_CreateNode(&list);
CycleList_Init(&list,length);
Prin_CycleList(list,length);
Josephus(list,Start,Count,length);

while(1)
{
}

return0;
}

//約瑟夫問題解決辦法(循環鏈表解決)
voidJosephus(ptrNodelist,intstart,intcount,intlength)
{
inti=1;

CycleList_Find(&list,start);
printf("
約瑟夫問題解決開始....
");

while(i<=?length)
????{
????????CycleList_Delete(&list,count);
i++;
}

printf("
約瑟夫問題解決結束
");
}

//創建循環鏈表頭結點
intCycleList_CreateNode(ptrNode*list)
{
*list=(ptrNode)malloc(sizeof(structCycleListNode));
if(*list==NULL)
{
printf("OutofSpace...
");
returnerror;
}

(*list)->next=NULL;

returnok;
}//初始化循環鏈表,并且最后丟掉鏈表頭結點,鏈表的數據為1->length
voidCycleList_Init(ptrNode*list,intlength)
{
inti=1;
ptrNodenewNode;
ptrNodeFirstNode;
FirstNode=*list;

while(i<=?length)//i從1到length
{
newNode=(ptrNode)malloc(sizeof(structCycleListNode));
newNode->data=i;
(*list)->next=newNode;
(*list)=newNode;
i++;
}

(*list)->next=FirstNode->next;
*list=FirstNode->next;
}

//刪掉循環鏈表中從表頭數的第position個位置的數據
//最終將頭結點變為刪除前那個結點的下一個結點
voidCycleList_Delete(ptrNode*list,intposition)
{
inti=1;
ptrNodetmp;

if(position==1)
{
tmp=*list;
while(tmp->data!=(*list)->next->data)
{
*list=(*list)->next;
}
printf("%d",(*list)->next->data);
(*list)->next=tmp->next;
*list=tmp->next;
free(tmp);
tmp=NULL;
}
else
{
while(i-1))
{
(*list)=(*list)->next;
i++;
}

tmp=(*list)->next;
printf("%d",tmp->data);
(*list)->next=(*list)->next->next;
free(tmp);
tmp=NULL;
*list=(*list)->next;
}
}

//查找循環鏈表中數據元素是Start的結點的位置,并且將該節點設為新的起始結點
voidCycleList_Find(ptrNode*list,ElementTypeStart)
{
while((*list)->data!=Start)
{
*list=(*list)->next;
}
}

//打印循環鏈表中的數據
voidPrin_CycleList(ptrNodelist,intlength)
{
inti=1;

printf("打印循環鏈表...
");

while(i<=?length)
????{
????????printf("%d",list->data);
list=list->next;
i++;
}

printf("
結束打印
");
}

下面是程序的運行結果：

以上就是對約瑟夫問題的解決方法啦，大家有不明白的可以留言喲。