今天看了一下約瑟夫問題，嗯，感覺自己智商欠費(fèi)：( 還是來總結(jié)下好啦~
問題
約瑟夫是猶太軍隊(duì)的一個將軍，在反抗羅馬的起義中，他所率領(lǐng)的軍隊(duì)被擊潰，只剩下殘余的部隊(duì)40余人，他們都是寧死不屈的人，所以不愿投降做叛徒。一群人表決說要死，所以用一種策略來先后殺死所有人。
于是約瑟夫建議：每次由其他兩人一起殺死一個人，而被殺的人的先后順序是由抽簽決定的，約瑟夫有預(yù)謀地抽到了最后一簽，在殺了除了他和剩余那個人之外的最后一人，他勸服了另外一個沒死的人投降了羅馬。
我們這個規(guī)則是這么定的：
在一間房間總共有n個人（下標(biāo)0～n-1），只能有最后一個人活命。
按照如下規(guī)則去殺人：
所有人圍成一圈
順時針報數(shù)，每次報到q的人將被殺掉
被殺掉的人將從房間內(nèi)被移走
然后從被殺掉的下一個人重新報數(shù)，繼續(xù)報q，再清除，直到剩余一人
輸入
人的個數(shù) : n
每次報到q 就會被殺死 的 q
輸出
最終能夠活下來的人的下標(biāo)
相關(guān)解析
1、https://blog.csdn.net/tingyun_say/article/details/52343897
2、http://www.cnblogs.com/kkrisen/p/3569281.html#undefined
分析
第一次報數(shù)殺掉的是下標(biāo)為（q-1）人
q ? ? ? 0
q+1 ? ? 1
: ? ??? :
: ? ? ?? :
n-1 ? ? n-q-1
0 ? ?? n-q
1 ? ?? n-q+1
: ? ? ?? :
: ? ? ?? :
q-2 ? ? n-2
由上述可見，殺掉一個人后，重新組成了一個約瑟夫環(huán)，重新組成的約瑟夫環(huán)的下標(biāo)和之前的下標(biāo)關(guān)系為 f(n)=(f(n-1)+q)%n。當(dāng)最后只剩下一個人的時候，它的下標(biāo)為0，我們可由上述的遞推關(guān)系得到只剩下兩個人時它的下標(biāo)，然后再推得只剩下3個人時它的下標(biāo)，一直推到最后有n個人時，它的下標(biāo)，就得到了最終的結(jié)果。請注意，這樣的解法所得到的坐標(biāo)是從以0--(n-1)為基準(zhǔn)的，如果想獲得以1--n為基準(zhǔn)下的，直接將所得的結(jié)果加1就好了，很直觀的解釋就是將下標(biāo)值加1。
另一個解釋：
f（1， 1） = 1；
f（n， k） = （f（n-1， k） + k - 1）%n + 1；
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
if (n == 0)
return 0;
int result = 0;
for (int i = 2; i <= n; i++)
result = (result + q ) % i;
return result+1;
}
變型問題
poj上有個變型問題，題目鏈接：http://poj.org/problem?id=3517，這個題與經(jīng)典約瑟夫問題的區(qū)別是，它要求第一個殺死的人下標(biāo)為m,并且下標(biāo)從1開始。對于這個問題的求解，我們可以按照原來方法去做，得到結(jié)果后再去移動下標(biāo)。在原來的問題中，第一個殺死的人下標(biāo)為q，我們想辦法移動下標(biāo)使得第一個殺死的人由q變?yōu)閙，假如n=5,q=2,m=4, 那么原始序列為
1， 2， 3，4，5
如果使得第一次殺死的人為m, 那么序列應(yīng)為
3 ， 4 ， 5 ，1 ， 2
那么由上面的如何得到下面的結(jié)果
f(下）= (f(上)+m-q)%n
// yuesefu.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
int n, q, m;
cin >> n >> q>> m;
if (n == 0)
return 0;
int mid = 0;
for (int i = 2; i <= n; i++)
mid = (mid + q ) % i;
int result = 0;
result = (mid + 1 + m - q) % n;
if (result < 0) result = result + n;
return result;
}
留個坑
1、打印每次淘汰的人
https://blog.csdn.net/coder_pig/article/details/50268099
2、如何用python實(shí)現(xiàn)？
index, step = 0, 3
while len(a) > 1:
index = (index + step - 1) % len(a)
print('kill No.', a[index])
del a[index]
print('\nWinner is', a[0])
