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

约瑟夫问题的N种解法

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

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

 模拟实现

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

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

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

简单的编码如下:

根据上面的说法,可以得出下面公式:
 
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);

假设最后剩下的人,在第(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;}