約瑟夫環問題
百度百科中寫道："約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數，第M個將被殺掉，最后剩下一個，其余人都將被殺掉，"
其可以理解成有一個[0..N-1]的陣列，從下標0開始，每次刪掉第m個數，下一輪從被刪掉的下一個數字開始，直至只剩下最后一個，那么最后剩下的一個是哪個數字？
我們以[0, 1, 2, 3, 4]，m = 3為例，
從下標0開始，刪掉第3個數，就是下標為m-1=2，那么刪掉后就是[0, 1, 3, 4]，下一次從3（下標為2）開始，
[0, 1, 3, 4]從3（下標2）開始就等價于[3, 4, 0, 1]從下標0開始，刪掉第3個：0，
以此類推，下一個陣列就是[1, 3, 4]，刪掉4，
再下一個陣列就是[1, 3]，刪掉第三個，由于陣列只有兩個，所以刪掉下標為 (2%2 = 0)，也就是刪掉1，
最后只剩下了數字3，
使用鏈表解決約瑟夫環問題
一個很自然的想法就是用回圈鏈表來模擬洗掉的程序，看最后剩下的是哪個數字，
我們將雙向回圈鏈表（定義為雙向回圈鏈表是為了方便洗掉當前節點）定義為：
struct bList {
bList(int val, std::shared_ptr<bList> backward = nullptr, std::shared_ptr<bList> forward = nullptr)
: val(val), forward(forward), backward(backward)
{}
int val;
std::shared_ptr<bList> forward;
std::shared_ptr<bList> backward;
};
使用雙向鏈表模擬洗掉的程序：
int process(int m) {
auto head = std::make_shared<bList>(0);
auto cur = head;
for (int idx = 1; idx < 5; ++idx) {
cur->forward = std::make_shared<bList>(idx, cur);
cur = cur->forward;
}
cur->forward = head;
head->backward = cur;
auto ls = head;
int idx = 0;
while (ls->forward != ls) {
if (idx == m-1) {
// 下標從0開始，當下標為m-1 = 3-1 = 2時洗掉當前節點
std::cout << "removed: " << ls->val << '\n';
ls->backward->forward = ls->forward;
ls->forward->backward = ls->backward;
ls = ls->forward;
idx = 1;
} else {
ls = ls->forward;
++idx;
}
}
ls->backward = ls->forward = nullptr;
return ls->val;
}
int main() {
std::cout << process(3) << '\n';
}
// Output:
// removed: 2
// removed: 0
// removed: 4
// removed: 1
// 3
使用遞推公式解決約瑟夫環問題
上面的解法雖然很簡單，只需要模擬即可，但時間消耗卻非常高，每查找一個數我們都需要遍歷m次，即便我們可以將m對鏈表size取模減小，但時間復雜度仍是非常高的，于是我們試圖找到一種更加高效的求解約瑟夫環的方法，
我們再回看我們手動解決例題的程序，其陣列變化程序如下：
- [0, 1, 2, 3, 4]
- [3, 4, 0, 1]
- [1, 3, 4]
- [1, 3]
- [3]
每次都洗掉第m個節點（下標為(m-1)%n，n為當前陣列長度），
可以確定地是最后幸存地數字在最后一個陣列中的下標為0，而且此時陣列的長度為1，
如果在我們知道第i+1個陣列中最后幸存者的下標和陣列長度的情況下，能夠求出第i個陣列中幸存者的下標和陣列長度，我們是不是就可以從最后一個陣列來倒推呢？第i個陣列長度很明顯是第i+1個陣列長度+1，如何推導第i個陣列中幸存者的下標呢？
首先我們假設第i+1個陣列長度為L, 第i個陣列長度為L+1；第i+1個陣列中幸存者的下標為IdxN(意為idx next)，第i個陣列中幸存者的下標為IdxP(意為idx previous)，
i+1個陣列中中幸存者的下標為N，那么必然有一個下表為0的節點，而該下標為0的節點在第i個陣列中下標必然是m%(L+1)(因為它的上一個節點被洗掉了，而被洗掉的節點的下標必然是(m-1)%(L+1)，那么被洗掉節點的下一個節點下標就是m%(L+1))，
我們就有如下等式：
IdxP - m = IdxN - 0 (mod L+1)
Idxp = IdxN + m (mod L+1)
（吐槽一下，博客園竟然不能顯示公式，）
$$
\begin{equation}
\begin{split}
IdxP - m &= IdxN - 0\ (mod\ L+1) \\
IdxP &= IdxN + m\ (mod\ L+1)
\end{split}
\end{equation}
$$
上面的公式中第一個公式表示是在兩個陣列中兩個數字的下標之差（距離）是相同的，因為被洗掉的數字在i[m%(L+1)]的緊貼著的左側，i[m%(L+1)]向右看必然先看到i[IdxP]，再看到i[(m-1)%(L+1)]；而且IdxN-0是必然小于L+1的，因為第i+1個陣列總長度只有L，
將第一個公式左邊的m移到右邊就得到了第二個公式，也就是從第i+1個陣列中幸存者的下標遞推出第i個陣列中幸存者的下標的遞推公式，其是第i個陣列長度L+1、往后數的個數m和第i個陣列中幸存者下標的函式，
將上述的程序轉化為代碼即為：
#include <iterator>
#include <memory>
#include <iostream>
#include <list>
// 這就是第二個公式，只是cnt表示的是L+1
// next是IdxN，m即為m
int process4_aux(int m, int next, int cnt) {
return (next + m)%cnt;
}
int process4(int m) {
int cnt = 1;
int next = 0;
while (cnt != 5) {
next = process4_aux(m, next, cnt+1);
++cnt;
std::cout << "at cnt = " << cnt << ", idx: " << next << '\n';
}
return next;
}
int main() {
std::cout << process4(3) << '\n';
}
// at cnt = 2, idx: 1
// at cnt = 3, idx: 1
// at cnt = 4, idx: 0
// at cnt = 5, idx: 3
// 3
關于網上的題解
我在百度上搜索約瑟夫環相關的問題時，LeetCode上的《約瑟夫環問題的三種解法講解》這個帖子排名很高，但他的代碼貌似有問題，其關于使用回圈鏈表解題的前兩個代碼好像都錯了，這里貼上我用C++寫的（我認為）正確的版本：
#include <iterator>
#include <memory>
#include <iostream>
#include <list>
struct bList {
bList(int val, std::shared_ptr<bList> backward = nullptr, std::shared_ptr<bList> forward = nullptr)
: val(val), forward(forward), backward(backward)
{}
int val;
std::shared_ptr<bList> forward;
std::shared_ptr<bList> backward;
};
class Solution {
public:
int process( std::shared_ptr<bList> ls,int m) {
int idx = 1;
while (ls->forward != ls) {
if (idx == m) {
std::cout << "removed: " << ls->val << '\n';
ls->backward->forward = ls->forward;
ls->forward->backward = ls->backward;
auto tmp = ls;
ls = ls->forward;
tmp->forward = tmp->backward = nullptr;
idx = 1;
} else {
ls = ls->forward;
++idx;
}
}
ls->forward = ls->backward = nullptr;
return ls->val;
}
int process2( std::shared_ptr<bList> ls,int m) {
int idx = 1;
auto cur = ls;
int n = 1;
while (cur ->forward != ls) {
++n;
cur = cur->forward;
}
while (ls->forward != ls) {
if (idx == ((m+n-1)%n+1)) {
std::cout << "removed: " << ls->val << '\n';
ls->backward->forward = ls->forward;
ls->forward->backward = ls->backward;
auto tmp = ls;
ls = ls->forward;
tmp->forward = tmp->backward = nullptr;
idx = 1;
--n;
} else {
ls = ls->forward;
++idx;
}
}
ls->forward = ls->backward = nullptr;
return ls->val;
}
int process3(int m) {
std::list<int> list;
for (int idx = 0; idx < 5; ++idx) {
list.push_back(idx);
}
int idx = 0;
while (list.size() > 1) {
idx = (idx+m-1)%list.size();
auto itr = list.cbegin();
std::advance(itr, idx);
std::cout << "remove: " << *itr << '\n';
list.erase(itr);
}
return list.front();
}
int process4(int m) {
int cnt = 1;
int next = 0;
while (cnt != 5) {
next = process4_aux(m, next, cnt+1);
++cnt;
std::cout << "at cnt = " << cnt << ", idx: " << next << '\n';
}
return next;
}
private:
int process4_aux(int m, int next, int cnt) {
return (next + m)%cnt;
}
};
int main() {
auto head = std::make_shared<bList>(0);
auto cur = head;
for (int idx = 1; idx < 5; ++idx) {
cur->forward = std::make_shared<bList>(idx, cur);
cur = cur->forward;
}
cur->forward = head;
head->backward = cur;
Solution s ;
std::cout << s.process2(head, 3) << '\n';
std::cout << s.process3(3) << '\n';
std::cout << s.process4(3) << '\n';
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539526.html
標籤：其他