C/C++經典算法之約瑟夫問題詳解
什麼是約瑟夫問題？
約瑟夫問題：n個人圍成一圈，初始編號從1~n排列，從約定編號為x的人開始報數，數到第m個人出圈，接著又從1開始報數，報到第m個數的人又退出圈，以此類推，最後圈內隻剩下一個人，這個人就是贏傢，求出贏傢的編號。
是不是有點點復雜，其實該問題歸結為模擬類型的算法題，根據題目要求模擬即可。
我說，一行代碼解決約瑟夫問題！
？？？我去
別著急，我們一步一步學習
方法一：數組
在第一次遇到這個題的時候，我是用數組做的，我猜絕大多數人也都知道怎麼做。方法是這樣的：
用一個數組來存放 1，2，3 … n 這 n 個編號，如圖（這裡我們假設n = 6, m = 3）
然後不停著遍歷數組，對於被選中的編號，我們就做一個標記，例如編號 arr[2] = 3 被選中瞭，那麼我們可以做一個標記，例如讓 arr[2] = -1，來表示 arr[2] 存放的編號已經出局的瞭。
然後就按照這種方法，不停著遍歷數組，不停著做標記，直到數組中隻有一個元素是非 -1 的，這樣，剩下的那個元素就是我們要找的元素瞭。我演示一下吧：
這種方法簡單嗎？思路簡單，但是編碼卻沒那麼簡單，臨界條件特別多，每次遍歷到數組最後一個元素的時候，還得重新設置下標為 0，並且遍歷的時候還得判斷該元素時候是否是 -1。用這種數組的方式做，千萬不要覺得很簡單，編碼這個過程還是挺考驗人的。
這種做法的時間復雜度是 O(n * m), 空間復雜度是 O(n);
下面給出數組方法的參考代碼：
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int a[1001]={0}; //初始化化數組作為環
int n,m;//n代表總的人數，m代表報數到幾退出
cin>>n>>m;
int count=0;//記錄退出的個數
int k=-1;//這裡假定開始為第一個人，下標為0，編號為1，如需從編號x開始，則k=x-2
while(count<n-1){ //總共需要退出n-1個人
int i=0;//記錄當前報數編號
while(i<m){
k=(k+1)%n; //循環處理下標
if(a[k]==0){
i++;
if(i==m){
a[k]=-1;
count++;
}
}
}
}
for(int i=0;i<n;i++){
if(a[i]==0){
printf("%d\n",i+1);
break;
}
}
return 0;
}
方法二：環形鏈表
學過鏈表的人，估計都會用鏈表來處理約瑟夫環問題，用鏈表來處理其實和上面處理的思路差不多，隻是用鏈表來處理的時候，對於被選中的編號，不再是做標記，而是直接移除，因為從鏈表移除一個元素的時間復雜度很低，為 O(1)。當然，上面數組的方法你也可以采用移除的方式，不過數組移除的時間復雜度為 O(n)。所以采用鏈表的解決方法如下：
1、先創建一個環形鏈表來存放元素：
2、然後一邊遍歷鏈表一遍刪除，直到鏈表隻剩下一個節點，我這裡就不全部演示瞭
感興趣的友友可以自己實現以下代碼，這裡就不放瞭
下面我們來看看，是如何一行代碼實現約瑟夫問題！
方法三：遞歸
其實這道題還可以用遞歸來解決，遞歸是思路是每次我們刪除瞭某一個人之後，我們就對這些人重新編號，然後我們的難點就是找出刪除前和刪除後編號的映射關系。
我們定義遞歸函數 f(n，m) 的返回結果是存活士兵的編號，顯然當 n = 1 時，f(n, m) = 1。假如我們能夠找出 f(n，m) 和 f(n-1，m) 之間的關系的話，我們就可以用遞歸的方式來解決瞭。我們假設人員數為 n, 報數到 m 的人就自殺。則剛開始的編號為
… 1 … m – 2
m – 1
m
m + 1
m + 2 … n …
進行瞭一次刪除之後，刪除瞭編號為 m 的節點。刪除之後，就隻剩下 n – 1 個節點瞭，刪除前和刪除之後的編號轉換關系為：
刪除前 — 刪除後
… — …
m – 2 — n – 2
m – 1 — n – 1
m —- 無(因為編號被刪除瞭)
m + 1 — 1(因為下次就從這裡報數瞭)
m + 2 —- 2
… —- …
新的環中隻有 n – 1 個節點。且刪除前編號為 m + 1, m + 2, m + 3 的節點成瞭刪除後編號為 1， 2， 3 的節點。
假設 old 為刪除之前的節點編號， new 為刪除瞭一個節點之後的編號，則 old 與 new 之間的關系為 old = (new + m – 1) % n + 1。
註：有些人可能會疑惑為什麼不是 old = (new + m ) % n 呢？主要是因為編號是從 1 開始的，而不是從 0 開始的。如果 new + m == n的話，會導致最後的計算結果為 old = 0。所以 old = (new + m – 1) % n + 1. 這樣，我們就得出 f(n, m) 與 f(n – 1, m)之間的關系瞭，而 f(1, m) = 1.所以我們可以采用遞歸的方式來做。
代碼如下：
int f(int n, int m){
return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
臥槽，以後有人讓你手寫約瑟夫問題，你就扔這一行代碼給它。
總結
到此這篇關於C/C++經典算法之約瑟夫問題的文章就介紹到這瞭,更多相關C/C++約瑟夫問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！