C語言-有趣的約瑟夫問題及解決辦法

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

首先來個(gè)解釋吧，約瑟夫問題，有時(shí)也稱為約瑟夫置換，是一個(gè)出現(xiàn)在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的問題。特別是對(duì)于學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)的人來說，在書上看到解決這個(gè)問題的題目，可能都不下5遍吧。在計(jì)算機(jī)編程的算法中，類似的問題又稱為約瑟夫環(huán)或者丟手絹問題。

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

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

約瑟夫問題并不難，求解的方法也非常的多，我這里提供一個(gè)循環(huán)鏈表的解決方法，為什么用循環(huán)鏈表，因?yàn)槲铱茨莻€(gè)故事里面的人都是手拉手圍成一個(gè)圓圈的嘛。

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

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

#include
#include

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

typedefintElementType;
typedefstructCycleListNodeNode;
typedefstructCycleListNode*ptrNode;

structCycleListNode//循環(huán)鏈表結(jié)點(diǎn)
{
ElementTypedata;//數(shù)據(jù)區(qū)
ptrNodenext;//指向下一個(gè)結(jié)點(diǎn)
};

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

//創(chuàng)建循環(huán)鏈表頭結(jié)點(diǎn)
intCycleList_CreateNode(ptrNode*list);

//初始化循環(huán)鏈表,并且最后丟掉鏈表頭結(jié)點(diǎn),鏈表的數(shù)據(jù)為1->length
voidCycleList_Init(ptrNode*list,intlength);

//刪掉循環(huán)鏈表中從表頭數(shù)的第position個(gè)位置的數(shù)據(jù)
//最終將頭結(jié)點(diǎn)變?yōu)閯h除前那個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
voidCycleList_Delete(ptrNode*list,intposition);

//查找循環(huán)鏈表中數(shù)據(jù)元素是Start的結(jié)點(diǎn)的位置,并且將該節(jié)點(diǎn)設(shè)為新的起始結(jié)點(diǎn)s
voidCycleList_Find(ptrNode*list,ElementTypeStart);

//打印循環(huán)鏈表中的數(shù)據(jù)
voidPrin_CycleList(ptrNodelist,intlength);

intmain(void)
{
intStart=1;//起始計(jì)數(shù)位置
intCount=3;//第Count個(gè)位置的結(jié)點(diǎn)出局
intlength=41;//循環(huán)鏈表的長(zhǎng)度
ptrNodelist;

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

while(1)
{
}

return0;
}

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

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

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

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

//創(chuàng)建循環(huán)鏈表頭結(jié)點(diǎn)
intCycleList_CreateNode(ptrNode*list)
{
*list=(ptrNode)malloc(sizeof(structCycleListNode));
if(*list==NULL)
{
printf("OutofSpace...
");
returnerror;
}

(*list)->next=NULL;

returnok;
}//初始化循環(huán)鏈表,并且最后丟掉鏈表頭結(jié)點(diǎn),鏈表的數(shù)據(jù)為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;
}

//刪掉循環(huán)鏈表中從表頭數(shù)的第position個(gè)位置的數(shù)據(jù)
//最終將頭結(jié)點(diǎn)變?yōu)閯h除前那個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
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;
}
}

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

//打印循環(huán)鏈表中的數(shù)據(jù)
voidPrin_CycleList(ptrNodelist,intlength)
{
inti=1;

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

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

printf("
結(jié)束打印
");
}

下面是程序的運(yùn)行結(jié)果：

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