大家有沒有聽過約瑟夫環這個問題呢？我們先來看看它是一個什么樣的問題~

約瑟夫環（Josephus）問題是由古羅馬的史學家約瑟夫（Flavius Josephus）提出的。該問題的說法不一，傳說他參加并記錄了公元66—70年猶太人反抗羅馬的起義。約瑟夫作為一個將軍，設法守住了裘達伯特城達47天之久，在城市淪陷之后，他和40名死硬的將士在附近的一個洞穴中避難。在那里，這些叛亂者表決說“要投降毋寧死”。于是，約瑟夫就想出來一個方法。

現在房間內共有n個人，將按下面的規則去殺人：

1、所有的人圍成一圈；

2、順時針報數，每次報到q的人將被殺掉；?

3、 被殺掉的人將從房間內移走；

4、然后從被殺掉的下一個人重新報數，直到剩余一人。

最終聰明的約瑟夫活了下來。

這就是著名的約瑟夫環問題。

下面我們來看一下這個問題是如何拿鏈表實現的呢？

下面我們就用代碼實現一下吧~我們只寫約瑟夫環這一部分，鏈表插刪等操作上節中講過啦！就不重復寫了。

pNode JosephCircle(pNode *pHead,int M)
{assert(pHead);pNode pCur = *pHead;pNode pPcur = *pHead;int count = M;if(*pHead == NULL || M <= 0)              //邊界檢測，M指報數的退出號return NULL;while (pCur->next)                        //找到最后一個節點，使它構成環{pCur = pCur->next;}pCur->next = *pHead;while(pPcur->next != pPcur)               {int count = M;while(--count)                     //報到第M個節點，則刪除{pPcur = pPcur->next;}if(pPcur == *pHead){*pHead = (*pHead)->next;}DeleteListNotTail(pHead,pPcur);}return pPcur;
}

返回值就是最后留下的那個人。出函數之后可以取節點的data知道里邊的內容。這就是簡單的約瑟夫環問題。

點擊繼續鏈表題哦>>