今天看了一下约瑟夫问题，嗯，感觉自己智商欠费：( 还是来总结下好啦~
问题
约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后杀死所有人。
于是约瑟夫建议：每次由其他两人一起杀死一个人，而被杀的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在杀了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。
我们这个规则是这么定的：
在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。
按照如下规则去杀人：
所有人围成一圈
顺时针报数，每次报到q的人将被杀掉
被杀掉的人将从房间内被移走
然后从被杀掉的下一个人重新报数，继续报q，再清除，直到剩余一人
输入
人的个数 : n
每次报到q 就会被杀死 的 q
输出
最终能够活下来的人的下标
相关解析
1、https://blog.csdn.net/tingyun_say/article/details/52343897
2、http://www.cnblogs.com/kkrisen/p/3569281.html#undefined
分析
第一次报数杀掉的是下标为（q-1）人
q 0
q+1 1
: :
: :
n-1 n-q-1
0 n-q
1 n-q+1
: :
: :
q-2 n-2
由上述可见，杀掉一个人后，重新组成了一个约瑟夫环，重新组成的约瑟夫环的下标和之前的下标关系为 f(n)=(f(n-1)+q)%n。当最后只剩下一个人的时候，它的下标为0，我们可由上述的递推关系得到只剩下两个人时它的下标，然后再推得只剩下3个人时它的下标，一直推到最后有n个人时，它的下标，就得到了最终的结果。请注意，这样的解法所得到的坐标是从以0--(n-1)为基准的，如果想获得以1--n为基准下的，直接将所得的结果加1就好了，很直观的解释就是将下标值加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，这个题与经典约瑟夫问题的区别是，它要求第一个杀死的人下标为m,并且下标从1开始。对于这个问题的求解，我们可以按照原来方法去做，得到结果后再去移动下标。在原来的问题中，第一个杀死的人下标为q，我们想办法移动下标使得第一个杀死的人由q变为m，假如n=5,q=2,m=4, 那么原始序列为
1， 2， 3，4，5
如果使得第一次杀死的人为m, 那么序列应为
3 ， 4 ， 5 ，1 ， 2
那么由上面的如何得到下面的结果
f(下）= (f(上)+m-q)%n
// yuesefu.cpp : 定义控制台应用程序的入口点。
//
#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实现？
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])
