在?？途W(wǎng)上做到一道題，是約瑟夫環(huán)的變型，所以借此學(xué)習(xí)一下新知識(shí)，并且鞏固一下對(duì)題目意思的理解，這一篇僅作約瑟夫環(huán)問題的解釋，下一篇再寫題目：

##1.首先，我們先來了解一下什么是約瑟夫環(huán)問題：
講一個(gè)比較有意思的故事：約瑟夫是猶太軍隊(duì)的一個(gè)將軍，在反抗羅馬的起義中，他所率領(lǐng)的軍隊(duì)被擊潰，只剩下殘余的部隊(duì)40余人，他們都是寧死不屈的人，所以不愿投降做叛徒。一群人表決說要死，所以用一種策略來先后kill所有人。
于是約瑟夫建議：每次由其他兩人一起kill一個(gè)人，而被kill的人的先后順序是由抽簽決定的，約瑟夫有預(yù)謀地抽到了最后一簽，在kill了除了他和剩余那個(gè)人之外的最后一人，他勸服了另外一個(gè)沒死的人投降了羅馬。

我們這個(gè)規(guī)則是這么定的：
在一間房間總共有n個(gè)人（下標(biāo)0～n-1），只能有最后一個(gè)人活命。

按照如下規(guī)則去排除人：

所有人圍成一圈順時(shí)針報(bào)數(shù)，每次報(bào)到q的人將被排除掉被排除掉的人將從房間內(nèi)被移走然后從被kill掉的下一個(gè)人重新報(bào)數(shù)，繼續(xù)報(bào)q，再清除，直到剩余一人

你要做的是：當(dāng)你在這一群人之間時(shí)，你必須選擇一個(gè)位置以使得你變成那剩余的最后一人，也就是活下來。

##2.這就是約瑟夫環(huán)問題，接下來我們說個(gè)特例初步了解下這種問題的求解思路：

特例：2，當(dāng)q = 2時(shí)候，是一個(gè)特例，能快速求解
特例還分兩種

###1.思路：注意這里的前提是n = 2^k(也就是2的冪次個(gè)人，其他數(shù)另外討論)

如果只有2個(gè)人，顯然剩余的為1號(hào)

如果有4個(gè)人，第一輪除掉2,4，剩下1,3，3死，留下1

如果是8個(gè)人，先除去2,4,6,8,之后3,7，剩下1,5，除去5，又剩下1了

定義J(n)為n個(gè)人構(gòu)成的約瑟夫環(huán)最后結(jié)果，則有j(2^k) = 1

J(n) = 2^k – 2^k-1 = 2^k-1     				n=2^k

J(n) = 2^k-1 – 2^k-2 = 2^k-2    			n=2^k-1

………

J(2^2) = 2^2 – 2^1 = 2^1 					n=2^2

遞推得到如上結(jié)果，起始我們仔細(xì)分析也就是每次除去一半的元素，然后剩余的一半繼續(xù)重復(fù)之前的策略，再除去一半。（可想到遞歸）

結(jié)合：J(2) = 1 我知道兩個(gè)數(shù)，從1開始，肯定是2先死，剩下1.

得到：j(2^k) = 1

###2.but當(dāng)n 不等于 2^k時(shí)候，比如9,11這種：

n 不等于 2^k時(shí)，就不存在這樣的easy的規(guī)律了，重新分析：

假設(shè)n = 9，這時(shí)候如圖下：

能看出來，我們干掉第一個(gè)人也就是2，之后就只剩下8個(gè)人了，又回到J(2^k)上了，這時(shí)候我們需要的是找到當(dāng)前的1號(hào)元素。
見圖下：

這時(shí)候，我們從3號(hào)開始，就成了另外一個(gè)規(guī)模小1的約瑟夫問題（恰好為2^k的特例）。
這時(shí)候，我們可以把3號(hào)看成新的約瑟夫問題中的1號(hào)位置：
J(8) = J(2^3) = 1，也就是說這里的1代表的就是上一個(gè)問題中的3號(hào)

So：J(9) = 3
答案為3號(hào)

####同理可知所有的非2^k的數(shù)都是這樣：
假設(shè)n = 2^k + t，t可以隨意取，比如1，2，3…….

假設(shè)n = 11，這時(shí)候n = 2^3 + 3，也就是說t = 3，所以開始剔除元素直到其成為2^k問題的約瑟夫問題。
So，我們?cè)谔蕹藅（3）個(gè)元素之后（分別是2,4,6），此時(shí)我們定格在2t+1（7）處，并且將2t+1（7）作為新的一號(hào)，而且這時(shí)候的約瑟夫環(huán)只剩下23，也就是J(23 + 3) = 2*3 + 1 = 7，答案為7

總結(jié)一下這個(gè)規(guī)律：
J(2^k + t) = 2t+1

##3.說完了特例，現(xiàn)在說說q 不等于2的情況下：

當(dāng)q ≠ 2：

我們假定：

• n — n人構(gòu)成的約瑟夫環(huán)
• q — 每次移除第q個(gè)人
  約定：
• Jq(n)表示n人構(gòu)成的約瑟夫環(huán)，每次移除第q個(gè)人的解
• n個(gè)人的編號(hào)從0開始至n-1

我們沿用之前特例的思想：能不能由Jq(n+1)的問題縮小成為J(n)的問題（這里的n是n+1規(guī)模的約瑟夫問題消除一個(gè)元素之后的答案），Jq(n)是在Jq(n+1)基礎(chǔ)上移除一個(gè)人之后的解。也就是說，我們能由Jq(n)得到Jq(n+1)。

規(guī)律：Jq(n+1) = ( Jq(n) + q ) / (n+1)
詳細(xì)推導(dǎo)過程見這篇博文

大致是如下這樣：

0 1 2 3 4 5 ......  n-1       總共n人
設(shè)第q個(gè)人也就是下標(biāo)為q-1的那位，kill：

剩下n-1個(gè)人，如下：
q q+1 q+2 ...... n-2  n-1   0  1  2   ......  q-2     (這里是除去q-1這位兄臺(tái)的剩余n-1人)

這時(shí)，又來重復(fù)我們的老套路：將新的被kill的后一個(gè)人作為新的0號(hào)，于是新的如下：
0  1  2   ......     ..........     ........  n-2

其實(shí)就是從q開始，到之前最大數(shù)n-1，每個(gè)數(shù)都減去q,從0開始之后接著n-1這個(gè)新的值每次往后加1，直到加到n-1（這個(gè)下標(biāo)）
舉個(gè)例子：

J4(9) :
0 1 2 3 4 5 6 7 8    消去3-->    0 1 2 4 5 6 7 8( 0 1 2)
				  對(duì)應(yīng)的新值：	      0 1 2 3 4  5 6 7

其中：q=4，從3之后第一個(gè)數(shù)4開始：每個(gè)數(shù)5-q=1,6-q=2,7-q=3，8-q=4，因?yàn)槭莻€(gè)環(huán)，0-q=-4,1-q=-3 ....直到加到n-1=7 

這就相當(dāng)于一個(gè)限定范圍內(nèi)的數(shù)的相對(duì)位置，-1代表的是最后一個(gè)元素，也就是之前的8
（-2就代表7,-3代表6,-4代表5.....-9代表0，從后面開始數(shù)過來第9位）

大致過程如圖下：

那么我們知道是這么得到的新的隊(duì)列，那么也很容易知道怎么反推了：
反觀如上的變化情況，都是減去一個(gè)q，所以：
變回去的公式如下：old = (new + q) % n
這里的old和new指的是下標(biāo)，n指的是總共有多少人

知道了怎么推出之前的下標(biāo)，那么也就可以一步步遞推回去得到開始的隊(duì)列或者從小推到大得到最后剩余的結(jié)果。

##最后再做一道實(shí)際點(diǎn)的例子，求J2(4):
J2(1) = 0
J2(2) = (J2(1) + 2) % 2 = 0
J2(3) = (J2(2) + 2) % 3 = 2
J2(4) = (J2(3) + 2) % 4 = 0
…
這樣一步步求就能得到所有的給出n和q條件的答案了。

#include<iostream>
#include<stdio.h>
using namespace std;

int yuesefu(int n,int m){
        if(n == 1){
                return 0; //這里返回下標(biāo),從0開始，只有一個(gè)元素就是剩余的元素0
        }
        else{
                return (yuesefu(n-1,m) + m) % n; //我們傳入的n是總共多少個(gè)數(shù)
        }
}
int main(void){
        int a,b;
        cin>>a>>b;
        cout<<yuesefu(a,b)<<endl;

		//或者，直接循環(huán)迭代，求出來的result如上
		int result = 0;
        for(int i = 2;i <= a;i++){
                result = (result+b) %i;
        }
        cout<<"result = "<<result<<endl;
        return 0;
}

##總結(jié)：
在遇上包含特殊的出隊(duì)規(guī)則相關(guān)的題目時(shí)，應(yīng)該聯(lián)想到是否是約瑟夫環(huán)問題，方便求解。
此文章重新整理在約瑟夫環(huán)問題詳解里了，修改了之前寫過程中存在的一些錯(cuò)誤，并添加了一些新的推導(dǎo)過程，謝謝指出錯(cuò)誤之處.

到此這篇關(guān)于C++ 約瑟夫環(huán)問題案例詳解的文章就介紹到這了,更多相關(guān)C++ 約瑟夫環(huán)問題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論