约瑟夫问题

今天看了一下约瑟夫问题，嗯，感觉自己智商欠费：( 还是来总结下好啦~

问题

约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队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])