注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

约瑟夫问题  

2012-12-02 13:36:04|  分类: ACM-Steps |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
约瑟夫问题,很经典的问题~
昨天做了一题约瑟夫的问题,研究了下,感觉很不错,总结一下:

约瑟夫问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。问n个人,第m个被杀,一直杀到最后一人,问最后一人的初始编号。

用链表或者数组模拟的方法就不再赘述了,不难写出,但是不够高效,复杂度达到了O(nm)。
分析下,最后只需求得最后被杀人的初始编号,不需要知道整个模拟过程。需要进行优化:

百度百科里有详细的方法进行优化,优化到O(n),简单说下:
先把题目变为:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号
第一个人出列后,剩下的n-1人重新组成约瑟夫环,从k=m%n开始报数:k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
将剩下的重新编号,k为0,k+1为1……k-2为n-2,依次进行编号。
变换后原问题成为了(n-1)个人的子问题,假如我们知道这个子问题的解,就可以推出原问题的解:例如x是子问题的解,则原问题的解x‘=(x+k) mod n,(n-1)的问题又可以推到(n-2)的问题……
依次类推,可以得到递推公式:
设f[i]为i个人的解,则有 f[i]=(f[i-1]+m)%i (i>1),f[1]=1;
用这个公式遍可求得f[n],因假设的编号是从0到n-1,而问题中的编号是从1到n,所以最后的结果为f[n]+1
这样的效率可达到O(n)。

#include<iostream>
using namespace std;
int main()
{
int n,i,s;
while(scanf("%d",&n)!=EOF)
{
for(i=2,s=0;i<=n;i++)
s=(s+2)%i;
printf("%d\n",s+1);
}
return 0;
}



上面的优化一般都能想到,昨天遇到的一题,比较特殊,m为2,O(n)的效率过不了,还需要进行改进:
因为m为2,n个人从1到n杀完一轮后,剩下n/2个人或者是n/2-1个人,所以可以判断出f[n]和f[n/2]肯定存在某种关系,
通过前30个数打表发现规律,可得状态转移方程如下:
f[i]=f[i/2]*2-1,i%2==0;
f[i]=f[i/2]*2+1,i%2==1;
通过这个公式,将原问题进行了进一步的优化,复杂度到了O(log n)。

#include<iostream>
using namespace std;
int f(int a)
{
if(a==1)
return 1;
if(a%2==0)
return f(a/2)*2-1;
return f(a/2)*2+1;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
printf("%d\n",f(n));
return 0;
}

其实,还可以优化到O(1)的效率,按上面推出来的状态转移方程推导公式即可;或者可以打表,把前30个打表出来,规律很明显就能找到,找到的公式如下:
f[n]=(n-2^(log2(n)))*2+1
如果觉得复杂的话,这个公式还可以演变为:
把二进制n的最左侧的1移到最右边。用上面的公式也很好解释,最左边的1的系数相当于log2(n),移除相当于n-2^(log2(n)),然后
把式子左移一位,相当于*2,最后加在最后边,相当于+1

  评论这张
 
阅读(105)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018