约瑟夫环问题

一般约瑟夫环问题：N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。

实际上对于约瑟夫环问题，最常见的有2种解法。

第一种就是直接暴力模拟链表，当然这种做法的时间复杂度很高，而且实现起来还很麻烦。第二种方法就是利用递推关系，有f[1] = 0,f[i] = (f[i-1] + K) % i;一个递推就完成，时间复杂度为O(n)。

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        int ans = 0;
        for(int i=2;i<=n;i++)
            ans = (ans + k) % i;
        cout<<ans+1<<endl;
    }
    return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2211

题意：对于约瑟夫环问题，我们一般求的是最后一个幸存者，而本题题意是求最后一个被杀者的编号。

分析：设f(N,K)表示N个人每第K个出列的最后取出的编号。那么f(N,K)进行第一次选取后，剩下N-N/K个人，这剩下的人里最后取出的编号为f(N-N/K,K)，简记为x，那么它在前一次队列里的编号为x+(x-1)/(K-1)，所以f(N,K)=(x-1)/(K-1)+x，其中x=f(N-N/K,K)。

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

int Work(int n,int k)
{
    if(n == k) return k;
    int t = Work(n-n/k,k);
    return (t-1)/(k-1) + t;
}

int main()
{
    int T,N,K;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&K);
        printf("%d\n",Work(N,K));
    }
    return 0;
}

好了，现在我们来看一下约瑟夫环问题的升级版：

N个人坐成一个圆环（编号为1 - N），从第K个人开始报数，数到M的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。例如：N = 3，M = 2，K = 1。2号先出列，然后是1号，最后剩下的是3号。

对于这个问题，我们同样有递推求解方法：

LL Josephus(LL n,LL m,LL k) //参数分别为：人数，步长，起始报数位置
{
    for(LL i=1; i<=n; i++)
        k = (k + m - 1) % i + 1;
    return k;
}

这个算法的时间复杂度为O(n)。

事实上，如果我们观察上述算法中的变量k，他的初始值为第一个出圈人的编号，但在循环的过程中，我们会发现它常常处在一种等差递增的状态，我来看这个式子：k = (k + m - 1) % i +  1，可以看出，当i比较大而k+m-1比较小的时候，k就处于一种等差递增的状态，这个等差递增的过程并不是必须的，可以跳过。

我们设一中间变量 x，列出等式：k + m * x – 1 = i + x，解出x，令k = k + m * x，将i + x直接赋值给i，这样就跳过了中间共x重的循环，从而节省了等差递增的时间开销。可是其中求出来的x + i可能会超过n，这样的结果事实上已经告诉我们此时可以直接结束算法了，即：

k = k + m * (n - i) ;
i = n;

结 束。
另外对于m = 1的情况可以单独讨论：
当k == 1时，最终结果就是n；
当k != 1时，最终结果就是(k + n -  1) % n。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3089

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

LL Work(LL n,LL m,LL k)
{
    if(m == 1)
        k = (k == 1 ? n:(n+k-1)%n);
    else
    {
        for(LL i=1; i<=n; i++)
        {
            if(k + m < i)
            {
                LL x = (i-k+1)/(m-1) - 1;
                if(i + x < n)
                {
                    i += x;
                    k += m*x;
                }
                else
                {
                    k += m*(n-i);
                    i = n;
                }
            }
            k = (k+m-1)%i+1;
        }
    }
    return k;
}

int main()
{
    LL n,k;
    while(cin>>n>>k)
        cout<<Work(n,k,1)<<endl;;
    return 0;
}