c c++

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

Posted by John on 2016-04-28
Words 991 and Reading Time 4 Minutes
Viewed Times

題目說明:

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

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

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

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

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

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

  1. 建好circular link list

  2. m = 1開始算起,從編號1依序刪除第m個點,如果刪掉壞人則繼續,直到所有壞人被刪光為止

  3. 刪到好人則m = m+1重新計算

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

  1. m必為k+1開始(好人一定不會被刪到)

  2. 設置bool變數去儲存是否被刪除,取代link list的delete node

  3. 用餘數運算子去計算要走的步數:例如要走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;
}
');


>