约瑟夫有关问题的N种解法

约瑟夫问题的N种解法

有n个囚犯站成一个圆圈，准备处决。首先从一个人开始报数,报到k的人被处死,剩下n-1个人继续这个过程,直到最终只剩下一个人留下.

问题是，给定了n和k，一开始要站在什么地方才能避免被处决？

模拟实现

我们利用计算机来模拟这个过程,可以得到最后的结果.

具体的编码中,考虑到每次要随机删除一个人,用链表实现比较方便.然后又是一个圈,可以考虑用循环链表.

指针从头到尾遍历到k,删去节点,直到只剩下一个节点为止.

简单的编码如下:

#include<iostream>
using namespace std;
int *A;
int f(int n,int k)
{
    int p=1;int q=n;
    int count=n;
    while(count--)
    {
        for(int i=0;i<k-1;i++)
        {
            q=p;
            p=A[p];
        }
        A[q]=A[p];
        p=A[p];
    }
    return p;
}
int main()
{
    int n,k;
    cin>>n>>k;
    A=new int[n+1];
    for(int i=1;i<n;i++)
    {
        A[i]=i+1;
    }A[n]=1;
    cout<<f(n,k)<<endl;
    return 0;
}

数学解法

因为k==2的时候有较多的研究,也有较直观和简单,简单到位级别的算法,我们先来考虑k==2的情况.

当k==2时,所有的偶数哥死掉了.剩下基数们,重新排列后,原来位置是x的哥,排到了(x+1)/2的位置(有兴趣的可以自己画画图).

用函数f(n)表示,当序列还有n个人的时候幸存者的位置.如下图：

约瑟夫有关问题的N种解法

根据上面的说法,可以得出下面公式:

N为偶数:f(N)=2*f(N/2)+1;

N为基数:f(N)=2*f((N-1)/2)+1; (1)

幸存者一直活到N=1的时候,即

f(1)=1; (2)

根据上面(1)(2),我们可以写出简单的递推方法,

F (1) = 1;

f (2n) = 2f (n) - 1; 当 n>1;

f (2n + 1) = 2f (n) + 1; 当 n>1;

从1->N递推,时间复杂度为O(N);

A[1]=1;
int f(int n)
{
    for(int i=2;i<=n;i++)
        A[i]=i&1?((A[i>>1]<<1)+1):(((A[i>>1])<<1)-1);
    return A[n];
}

或者用递归函数,从N->1,时间复杂度为O(logN).

int f(int n)
{
    if(!(n^1))
        return 1;
    if(n&1)
        return 2*f((n-1)/2)+1;
    else
        return 2*f(n/2)-1;
}

接着我们要推出更简洁的方法.

列出的f(N)与N如下:

N 1, 2 3 4, 5 6 7 8, 9 10 11 12 13 14 15 16,

F(N)1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

通过观察我们能够发现,f(N)是一个基数的循环,以2^m为开头,即:

如果N=2^m+L,(0<=L<2^m),那么f(N)=2*L+1;

当然,看到2^m,我们很自然地想到要用位操作解决.

2^m,即m+1位为1;如2^3=8的二进制数就是1000.

N 的二进制表示为:N=b0b1b2b3….,其中b0表示非0的最高位.

那么2^m<N的最大2^m为b0,000000,(N-2^m)*2+1=b1b2…..b0.

也就是f(b0b1b2..)=b1b2..b0;

OK,开始编码:

int f(int n)
{
    int pos=1;int temp=1;
    for(int i=0;i<31;i++)
    {
        if(n&pos)
            temp=pos;
        pos=(pos<<1);
    }
    return ((n-temp)<<1)+1;
}

K的一般解法

之所以k==2单独拉出来讨论,是由于其简单好理解.再加上二进制的妙用简化了计算.

下面是k的一般解法.

我们考虑如下过程

1 2 3 4 5 6 ….. k-1 k k+1 … n-1 n

第一次编号为k的哥挂掉,然后剩下n-1个人,从k+1号继续.

k+1 k+1 ….n-1 n 1 2 3 4 5 6 ,序号全部-k,得到如下序列:

1 2 3 4 5 6….. n-1也就是n-1个人的情况.

图示如下：

约瑟夫有关问题的N种解法

假设最后剩下的人,在第(n-1)人的序列中的编号是f(n-1),那么他在n个人的序列中,编号为(k+f(n-1))%n,也就得到了我们的递推公式:

f(n)=(k+f(n-1))%n;

f(1)=1;

递推算法的时间复杂度为O(N),编码如下:

int *A;
int f(int n,int k)
{
    A[1]=0;
    for(int i=2;i<=n;i++)
    {
        A[i]=(A[i-1]+k)%i;
    }
    return A[n]+1;
}

约瑟夫有关问题的N种解法

相关推荐