如何編寫約瑟夫環問題

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

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

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

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

struct ListNode
{
    int num;        //編號
    ListNode *next; //下一個
    ListNode(int n = 0, ListNode *p = NULL) 
    { num = n; next = p;}
};
 
//自定義鏈表實現
int JosephusProblem_Solution1(int n, int m)
{
    if(n < 1 || m < 1)
        return -1;
 
    ListNode *pHead = new ListNode(); //頭結點
    ListNode *pCurrentNode = pHead;   //當前結點
    ListNode *pLastNode = NULL;       //前一個結點
    unsigned i;
 
    //構造環鏈表
    for(i = 1; i < n; i++)
    {
        pCurrentNode->next = new ListNode(i);
        pCurrentNode = pCurrentNode->next;
    }
    pCurrentNode->next = pHead;
 
    //循環遍歷
    pLastNode = pCurrentNode;
    pCurrentNode = pHead;
 
    while(pCurrentNode->next != pCurrentNode)
    {
        //前進m - 1步
        for(i = 0; i < m-1; i++)
        {
            pLastNode = pCurrentNode;
            pCurrentNode = pCurrentNode->next;
        }
        //刪除報到m - 1的數
        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<int> listInt;
    unsigned i;
    //初始化鏈表
    for(i = 0; i < n; i++)
        listInt.push_back(i);
 
    list<int>::iterator iterCurrent = listInt.begin();
    while(listInt.size() > 1)
    {
        //前進m - 1步
        for(i = 0; i < m-1; i++)
        {
            if(++iterCurrent == listInt.end())
                iterCurrent = listInt.begin();
        }
        //臨時保存刪除的結點
        list<int>::iterator iterDel = iterCurrent;
        if(++iterCurrent == listInt.end())
            iterCurrent = listInt.begin();
        //刪除結點
        listInt.erase(iterDel);
    }
 
    return *iterCurrent;
}

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

       下面利用數學推導，如果能得出一個通式，就可以利用遞歸、循環等手段解決。下面給出推導的過程：

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

        （2）假設第二輪的開始數字為k，那么這n - 1個數構成的約瑟夫環為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 個人問題的解，從而得到一個遞推公式，那么問題就解決了。假如我們已經知道了n -1個人時，最后勝利者的編號為x，利用映射關系逆推，就可以得出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）第二個被刪除的數為(m - 1) % (n - 1)。

        （4）假設第三輪的開始數字為o，那么這n - 2個數構成的約瑟夫環為o, o + 1, o + 2,......o - 3, o - 2.。繼續做映射。

             o         ----->  0 
             o+1    ------> 1 
             o+2    ------> 2 
               ... 
               ... 

             o-2     ------>  n-3 

         這是一個n - 2個人的問題。假設最后的勝利者為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) 

        有了遞推公式，實現就非常簡單了，給出循環的兩種實現方式。再次表明用標準庫的便捷性。

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<int> f(n+1,0);
    for(unsigned i = 2; i <= n; i++)
        f[i] = (f[i-1] + m) % i;
 
    return f[n];
}

感謝各位的閱讀，以上就是“如何編寫約瑟夫環問題”的內容了，經過本文的學習后，相信大家對如何編寫約瑟夫環問題這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！