如何編寫約瑟夫環(huán)問題

這篇文章主要講解了“如何編寫約瑟夫環(huán)問題”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何編寫約瑟夫環(huán)問題”吧！

  約瑟夫環(huán)問題的原來描述為，設(shè)有編號為1，2，……，n的n(n>0)個(gè)人圍成一個(gè)圈，從第1個(gè)人開始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，再從他的下一個(gè)人起重新報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的出圈，……，如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。  稍微簡化一下。

        問題描述：n個(gè)人（編號0~(n-1))，從0開始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼續(xù)從0開始報(bào)數(shù)。求勝利者的編號。 

        思路：容易想到的就是用環(huán)鏈表來做，構(gòu)建一個(gè)環(huán)鏈表，每個(gè)結(jié)點(diǎn)的編號為0, 1, ...... n-1。每次從當(dāng)前位置向前移動m-1步，然后刪除這個(gè)結(jié)點(diǎn)。最后剩下的結(jié)點(diǎn)就是勝利者。給出兩種方法實(shí)現(xiàn)，一種是自定義鏈表操作，另一種用是STL庫的單鏈表。不難發(fā)現(xiàn)，用STL庫可以提高編寫速度。

struct ListNode
{
    int num;        //編號
    ListNode *next; //下一個(gè)
    ListNode(int n = 0, ListNode *p = NULL) 
    { num = n; next = p;}
};
 
//自定義鏈表實(shí)現(xiàn)
int JosephusProblem_Solution1(int n, int m)
{
    if(n < 1 || m < 1)
        return -1;
 
    ListNode *pHead = new ListNode(); //頭結(jié)點(diǎn)
    ListNode *pCurrentNode = pHead;   //當(dāng)前結(jié)點(diǎn)
    ListNode *pLastNode = NULL;       //前一個(gè)結(jié)點(diǎn)
    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)
    {
        //前進(jìn)m - 1步
        for(i = 0; i < m-1; i++)
        {
            pLastNode = pCurrentNode;
            pCurrentNode = pCurrentNode->next;
        }
        //刪除報(bào)到m - 1的數(shù)
        pLastNode->next = pCurrentNode->next;
        delete pCurrentNode;
        pCurrentNode = pLastNode->next;
    }
    //釋放空間
    int result = pCurrentNode->num;
    delete pCurrentNode;
 
    return result;
}

//使用標(biāo)準(zhǔn)庫
int JosephusProblem_Solution2(int n, int m)
{
    if(n < 1 || m < 1)
        return -1;
 
    list<int> listInt;
    unsigned i;
    //初始化鏈表
    for(i = 0; i < n; i++)
        listInt.push_back(i);
 
    list<int>::iterator iterCurrent = listInt.begin();
    while(listInt.size() > 1)
    {
        //前進(jìn)m - 1步
        for(i = 0; i < m-1; i++)
        {
            if(++iterCurrent == listInt.end())
                iterCurrent = listInt.begin();
        }
        //臨時(shí)保存刪除的結(jié)點(diǎn)
        list<int>::iterator iterDel = iterCurrent;
        if(++iterCurrent == listInt.end())
            iterCurrent = listInt.begin();
        //刪除結(jié)點(diǎn)
        listInt.erase(iterDel);
    }
 
    return *iterCurrent;
}

       上述方法的效率很低，其時(shí)間復(fù)雜度為O(mn)。當(dāng)n和m很大時(shí)，很難在短時(shí)間內(nèi)得出結(jié)果。不過好處就是可以給出n個(gè)人出圈的次序。只要在刪除前保存一下即可。

       下面利用數(shù)學(xué)推導(dǎo)，如果能得出一個(gè)通式，就可以利用遞歸、循環(huán)等手段解決。下面給出推導(dǎo)的過程：

        （1）第一個(gè)被刪除的數(shù)為 (m - 1) % n。

        （2）假設(shè)第二輪的開始數(shù)字為k，那么這n - 1個(gè)數(shù)構(gòu)成的約瑟夫環(huán)為k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一個(gè)簡單的映射。

             k         ----->  0 
             k+1    ------> 1 
             k+2    ------> 2 
               ... 
               ... 
             k-2    ------>  n-2 

        這是一個(gè)n -1個(gè)人的問題，如果能從n - 1個(gè)人問題的解推出 n 個(gè)人問題的解，從而得到一個(gè)遞推公式，那么問題就解決了。假如我們已經(jīng)知道了n -1個(gè)人時(shí)，最后勝利者的編號為x，利用映射關(guān)系逆推，就可以得出n個(gè)人時(shí)，勝利者的編號為 (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）第二個(gè)被刪除的數(shù)為(m - 1) % (n - 1)。

        （4）假設(shè)第三輪的開始數(shù)字為o，那么這n - 2個(gè)數(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 

         這是一個(gè)n - 2個(gè)人的問題。假設(shè)最后的勝利者為y，那么n -1個(gè)人時(shí)，勝利者為 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
         要得到n - 1個(gè)人問題的解，只需得到n - 2個(gè)人問題的解，倒推下去。只有一個(gè)人時(shí)，勝利者就是編號0。下面給出遞推式：

          f [1] = 0; 
          f [ i ] = ( f [i -1] + m) % i; (i>1) 

        有了遞推公式，實(shí)現(xiàn)就非常簡單了，給出循環(huán)的兩種實(shí)現(xiàn)方式。再次表明用標(biāo)準(zhǔ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]其實(shí)用不到的
 
    for(unsigned i = 2; i <= n; i++)
        f[i] = (f[i-1] + m) % i; //按遞推公式進(jìn)行計(jì)算
 
    int result = f[n];
    delete []f;
 
    return result;
}

int JosephusProblem_Solution4(int n, int m)
{
    if(n < 1 || m < 1)
        return -1;
 
    vector<int> 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)過本文的學(xué)習(xí)后，相信大家對如何編寫約瑟夫環(huán)問題這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！