約瑟夫問題又稱為“約瑟夫置換”或者“約瑟夫環(huán)”，是一個(gè)出現(xiàn)在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的問題
歷史背景：
版本一：這個(gè)問題是以[弗拉維奧·約瑟夫]命名的诊霹，他是1世紀(jì)的一名猶太歷史學(xué)家。他在自己的日記中寫道，他和他的40個(gè)戰(zhàn)友被羅馬軍隊(duì)包圍在洞中懂酱。他們討論是自殺還是被俘，最終決定自殺誊抛，并以抽簽的方式?jīng)Q定誰殺掉誰列牺。約瑟夫斯和另外一個(gè)人是最后兩個(gè)留下的人。約瑟夫斯說服了那個(gè)人拗窃，他們將向羅馬軍隊(duì)投降瞎领，不再自殺。約瑟夫斯把他的存活歸因于運(yùn)氣或天意随夸，他不知道是哪一個(gè)
版本二：Josephus有過的故事：39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中九默，39個(gè)猶太人決定寧愿死也不要被敵人抓。于是決定了自殺方式宾毒，41個(gè)人排成一個(gè)圓圈驼修，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺伍俘。然后下一個(gè)重新報(bào)數(shù)邪锌，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從癌瘾，Josephus要他的朋友先假裝遵從觅丰，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過了這場死亡游戲
【ps：發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)&算法何其偉大妨退，關(guān)乎到生死存亡呀哈哈哈】
應(yīng)用問題轉(zhuǎn)化：
【N個(gè)人圍繞在一個(gè)圓桌子上玩報(bào)數(shù)游戲妇萄，報(bào)到N這個(gè)數(shù)字蜕企，淘汰，然后從下一個(gè)人繼續(xù)開始報(bào)數(shù)冠句，報(bào)到N淘汰轻掩，循環(huán)下去，最后剩余2個(gè)人懦底，也
可以循環(huán)唇牧，最終只會(huì)有一個(gè)人勝出】
言歸正傳：怎么使用循環(huán)鏈表來描述這個(gè)問題？可直接參考如下代碼
/*****************************************循環(huán)鏈表*******************************************/
void circularLinkedList(int M,int N){
PersonListNode *head = (PersonListNode *)malloc(sizeof(PersonListNode));//定義一個(gè)頭結(jié)點(diǎn)
head ->next = head;
head ->num = 1;
PersonListNode *temp = head; //將頭結(jié)點(diǎn)復(fù)制給temp
for (int i = 2; i<= N; i++) {//構(gòu)建循環(huán)鏈表聚唐，
temp ->next = (PersonListNode *)malloc(sizeof(PersonListNode)); // 當(dāng)i=2時(shí)丐重，temp->next為開始結(jié)點(diǎn)，也就是頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
temp = temp->next; // 當(dāng)i=2時(shí)杆查，將開始結(jié)點(diǎn)賦值給temp
temp->num = i;
temp->next = head; // 將當(dāng)前結(jié)點(diǎn)指向頭結(jié)點(diǎn)扮惦，循環(huán)結(jié)束時(shí)，temp指向的是尾結(jié)點(diǎn)
}
while (temp != temp ->next) {//循環(huán)開始時(shí)亲桦，temp指向的是尾結(jié)點(diǎn)
for (int j=1; j<M; j++) {
temp =temp->next;//此時(shí)在M的間隔中間崖蜜，只需要完成結(jié)點(diǎn)替代、遍歷
}
//執(zhí)行完for時(shí)就說明此時(shí)j=M客峭，該俘虜需要自殺豫领，for循環(huán)執(zhí)行完，當(dāng)前temp的下一個(gè)人就是目標(biāo)俘虜
PersonListNode *targetPersonNode = temp->next;
cout<<"編號(hào)為"<<targetPersonNode->num<<"的俘虜自殺"<< endl;
//此時(shí)需要將自殺俘虜之后俘虜與自殺俘虜之前的俘虜進(jìn)行關(guān)聯(lián)舔琅，此時(shí)的temp為自殺前一個(gè)俘虜?shù)慕Y(jié)點(diǎn)
temp->next = temp->next->next;
free(targetPersonNode);//將當(dāng)前自殺的俘虜移除氏堤，重新來過
}
cout<<"此時(shí)勝出俘虜編號(hào)為"<< temp->num<<endl;
}
int main()
{
int M,N;//M 規(guī)則（隔M個(gè)數(shù)） N 人數(shù)（N個(gè)人）
cout << "輸入俘虜人數(shù)N " <<endl;
cin >> N;
cout << "輸入規(guī)則M間隔數(shù)"<<endl;
cin >> M;
//單鏈表實(shí)現(xiàn)思路[目前有點(diǎn)問題，待完善]
// singleLinkedList(M, N);
//循環(huán)鏈表實(shí)現(xiàn)思路搏明。M為3 N為8 此時(shí)7號(hào)俘虜勝出
circularLinkedList(M,N);
return 0;
}
待完善【單鏈表解法、數(shù)組解法 及其對(duì)比】
