這篇文章主要講解了“如何編寫約瑟夫環(huán)問題”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何編寫約瑟夫環(huán)問題”吧！
專業(yè)從事網(wǎng)站設(shè)計制作、網(wǎng)站建設(shè),高端網(wǎng)站制作設(shè)計,成都微信小程序,網(wǎng)站推廣的成都做網(wǎng)站的公司。優(yōu)秀技術(shù)團隊竭力真誠服務(wù)，采用H5頁面制作+CSS3前端渲染技術(shù)，響應(yīng)式網(wǎng)站建設(shè)，讓網(wǎng)站在手機、平板、PC、微信下都能呈現(xiàn)。建站過程建立專項小組，與您實時在線互動，隨時提供解決方案，暢聊想法和感受。
約瑟夫環(huán)問題的原來描述為，設(shè)有編號為1，2，……，n的n(n>0)個人圍成一個圈，從第1個人開始報數(shù)，報到m時停止報數(shù)，報m的人出圈，再從他的下一個人起重新報數(shù)，報到m時停止報數(shù)，報m的出圈，……，如此下去，直到所有人全部出圈為止。當任意給定n和m后，設(shè)計算法求n個人出圈的次序。 稍微簡化一下。
問題描述：n個人（編號0~(n-1))，從0開始報數(shù)，報到(m-1)的退出，剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
思路：容易想到的就是用環(huán)鏈表來做，構(gòu)建一個環(huán)鏈表，每個結(jié)點的編號為0, 1, ...... n-1。每次從當前位置向前移動m-1步，然后刪除這個結(jié)點。最后剩下的結(jié)點就是勝利者。給出兩種方法實現(xiàn)，一種是自定義鏈表操作，另一種用是STL庫的單鏈表。不難發(fā)現(xiàn)，用STL庫可以提高編寫速度。
重慶分公司
重慶分公司
struct ListNode
{
int num; //編號
ListNode *next; //下一個
ListNode(int n = 0, ListNode *p = NULL)
{ num = n; next = p;}
};
//自定義鏈表實現(xiàn)
int JosephusProblem_Solution1(int n, int m)
{
if(n < 1 || m < 1)
return -1;
ListNode *pHead = new ListNode(); //頭結(jié)點
ListNode *pCurrentNode = pHead; //當前結(jié)點
ListNode *pLastNode = NULL; //前一個結(jié)點
unsigned i;
//構(gòu)造環(huán)鏈表
for(i = 1; i < n; i++)
{
pCurrentNode->next = new ListNode(i);
pCurrentNode = pCurrentNode->next;
}
pCurrentNode->next = pHead;
//循環(huán)遍歷
pLastNode = pCurrentNode;
pCurrentNode = pHead;
while(pCurrentNode->next != pCurrentNode)
{
//前進m - 1步
for(i = 0; i < m-1; i++)
{
pLastNode = pCurrentNode;
pCurrentNode = pCurrentNode->next;
}
//刪除報到m - 1的數(shù)
pLastNode->next = pCurrentNode->next;
delete pCurrentNode;
pCurrentNode = pLastNode->next;
}
//釋放空間
int result = pCurrentNode->num;
delete pCurrentNode;
return result;
}
//使用標準庫
int JosephusProblem_Solution2(int n, int m)
{
if(n < 1 || m < 1)
return -1;
list listInt;
unsigned i;
//初始化鏈表
for(i = 0; i < n; i++)
listInt.push_back(i);
list::iterator iterCurrent = listInt.begin();
while(listInt.size() > 1)
{
//前進m - 1步
for(i = 0; i < m-1; i++)
{
if(++iterCurrent == listInt.end())
iterCurrent = listInt.begin();
}
//臨時保存刪除的結(jié)點
list::iterator iterDel = iterCurrent;
if(++iterCurrent == listInt.end())
iterCurrent = listInt.begin();
//刪除結(jié)點
listInt.erase(iterDel);
}
return *iterCurrent;
} 上述方法的效率很低，其時間復雜度為O(mn)。當n和m很大時，很難在短時間內(nèi)得出結(jié)果。不過好處就是可以給出n個人出圈的次序。只要在刪除前保存一下即可。
下面利用數(shù)學推導，如果能得出一個通式，就可以利用遞歸、循環(huán)等手段解決。下面給出推導的過程：
（1）第一個被刪除的數(shù)為 (m - 1) % n。
（2）假設(shè)第二輪的開始數(shù)字為k，那么這n - 1個數(shù)構(gòu)成的約瑟夫環(huán)為k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一個簡單的映射。
k -----> 0
k+1 ------> 1
k+2 ------> 2
...
...
k-2 ------> n-2
這是一個n -1個人的問題，如果能從n - 1個人問題的解推出 n 個人問題的解，從而得到一個遞推公式，那么問題就解決了。假如我們已經(jīng)知道了n -1個人時，最后勝利者的編號為x，利用映射關(guān)系逆推，就可以得出n個人時，勝利者的編號為 (x + k) % n。其中k等于m % n。代入(x + k) % n <=> (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n
（3）第二個被刪除的數(shù)為(m - 1) % (n - 1)。
（4）假設(shè)第三輪的開始數(shù)字為o，那么這n - 2個數(shù)構(gòu)成的約瑟夫環(huán)為o, o + 1, o + 2,......o - 3, o - 2.。繼續(xù)做映射。
o -----> 0
o+1 ------> 1
o+2 ------> 2
...
...
o-2 ------> n-3
這是一個n - 2個人的問題。假設(shè)最后的勝利者為y，那么n -1個人時，勝利者為 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
要得到n - 1個人問題的解，只需得到n - 2個人問題的解，倒推下去。只有一個人時，勝利者就是編號0。下面給出遞推式：
f [1] = 0;
f [ i ] = ( f [i -1] + m) % i; (i>1)
有了遞推公式，實現(xiàn)就非常簡單了，給出循環(huán)的兩種實現(xiàn)方式。再次表明用標準庫的便捷性。
int JosephusProblem_Solution3(int n, int m)
{
if(n < 1 || m < 1)
return -1;
int *f = new int[n+1];
f[0] = f[1] = 0; //f[0]其實用不到的
for(unsigned i = 2; i <= n; i++)
f[i] = (f[i-1] + m) % i; //按遞推公式進行計算
int result = f[n];
delete []f;
return result;
}
int JosephusProblem_Solution4(int n, int m)
{
if(n < 1 || m < 1)
return -1;
vector f(n+1,0);
for(unsigned i = 2; i <= n; i++)
f[i] = (f[i-1] + m) % i;
return f[n];
} 感謝各位的閱讀，以上就是“如何編寫約瑟夫環(huán)問題”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對如何編寫約瑟夫環(huán)問題這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！
