[C/C++]約瑟夫問題變形-求最小m值

題目說明:

(參考網址: http://openhome.cc/Gossip/AlgorithmGossip/JosephusProblem.htm)

據說著名猶太歷史/數學家約瑟夫（Josephus）有過以下的故事：在羅馬人佔領喬塔帕特後，40個猶太士兵與約瑟夫躲到一個洞中，眼見脫逃無望，一群人決定集體自殺，然而私下約瑟夫與某個傢伙並不贊成，於是約瑟夫建議自殺方式，41個人排成圓圈，由第1個人開始報數，每報數到3的人就必須自殺，然後由下一個重新報數，直到所有人都自殺身亡為止。約瑟夫與不想自殺的那個人分別排在第16個與第31個位置，於是逃過了這場死亡遊戲。

一般來說的問題是求出最後一個活著的編號，在文章內有提到這有一個遞迴定義式:

$g(1, k) = 0 g(n, k) = (g(n - 1, k) + k) % n -$

接下來要說一個相關的變形題:

給予k個好人與壞人(0<k<13)排成圓圈，編號一開始先排k個好人，再來是k個壞人，求出最小的m使得在壞人都死光前沒有好人被殺死。

如果按造題意，用最直白的寫法會是:

建好circular link list
m = 1開始算起，從編號1依序刪除第m個點，如果刪掉壞人則繼續，直到所有壞人被刪光為止
刪到好人則m = m+1重新計算

以下是一些提升效率的優化

m必為k+1開始(好人一定不會被刪到)
設置bool變數去儲存是否被刪除，取代link list的delete node
用餘數運算子去計算要走的步數:例如要走7步，有三個點，7%3 = 1，實際上只須走一步即可。

加上第三點後效率會大大提升，我估計時間複雜度會從原本的O(n*m)變成O(k*m)(不知是否有錯…)

實測沒加第三點時跑k = 13要花20分鐘以上，優化後k = 13花不到1秒多。

以下是優化後的程式碼:

document.write('
DATA HOSTED WITH ♥ BY PASTEBIN.COM - DOWNLOAD RAW - SEE ORIGINAL
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
class people
{
public:
    people()
    {
        this->is_badman = false;
        this->is_delect = false;
        this->num = 0;
        this->next = NULL;
    }
    people(int k)
    {
        head = new people();//用個開頭節點設置link list
        ptr = head;
        for(int i = 1 ; i <= k ; ++i)//設置好人
        {
            people *n = new people();
            n->num = i;
            n->is_badman = false;
            ptr->next = n;
            ptr = ptr->next;
        }
        for(int i = k+1 ; i <= 2*k ; ++i)//設置壞人
        {
            people *n = new people();
            n->num = i;
            n->is_badman = true;
            ptr->next = n;
            ptr = ptr->next;
        }
        ptr->next = head->next;//把link list串成環狀，head重新指向有值得第一個
        head = head->next;
    }
    int solve(int k)
    {
        int n = k+1;//答案必是最小k+1開始找
        int run = n;//走的步數
        int alive = 2 * k;//目前的node數
        int temp = 0;//已刪掉的壞人數
        ptr = head;
        while(temp != k)//如果所有壞人被刪掉就離開
        {
            run = (n-1) % alive;//把走n-1次(不包含自己)，優化成(n-1)%alive
            for(int i = 0 ; i < run ; )
            {
                ptr = ptr->next;
                if(ptr->is_delect)continue;//刪過的點就不算
                else
                {
                    ++i;
                }
            }
            if(!(ptr->is_badman))//該點是好人則不是解，直接跳下個n
            {
                n++;
                //初始化設定
                alive = 2 * k;
                temp = 0;
                ptr = head;
                while(ptr->next != head)//把刪除過的點還原
                {
                    ptr->is_delect = false;
                    ptr = ptr->next;
                }
                ptr->is_delect = false;//最後一個沒被初始化到，另外寫
                ptr = head;//重設ptr指向開頭
            }
            else//壞人
            {
                ptr->is_delect = true;//刪掉
                while(ptr->next->is_delect)//跳下一個沒被刪過的點
                {
                    ptr = ptr->next;
                }
                ptr = ptr->next;
 
                alive--;//現存node數-1
                temp++;
            }
        }
        return n;
    }
//member
    int num;
    bool is_badman;
    bool is_delect;
    people *next;
private:
    people *head;
    people *ptr;
};
 
int main()
{
    int k = 0;
    cin >> k;
    people p(k);
    cout << p.solve(k) << endl;
    return 0;
}
');