约瑟夫问题的N种解法
有n个囚犯站成一个圆圈，准备处决。首先从一个人开始报数,报到k的人被处死,剩下n-1个人继续这个过程,直到最终只剩下一个人留下.
问题是，给定了n和k，一开始要站在什么地方才能避免被处决？
模拟实现
我们利用计算机来模拟这个过程,可以得到最后的结果.
具体的编码中,考虑到每次要随机删除一个人,用链表实现比较方便.然后又是一个圈,可以考虑用循环链表.
指针从头到尾遍历到k,删去节点,直到只剩下一个节点为止.
简单的编码如下:
[cpp]
#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为偶数: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);
[cpp]
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).
[cpp]
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,开始编码:
[cpp]
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;
}
补充：软件开发 , C++ ,
