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

记录创意的火花

天天学习,好好向上

 
 
 

日志

 
 

约瑟夫环O(n)复杂度的解法  

2012-10-04 10:46:32|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

约瑟夫环问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

        问题描述:n个人(编号0~(n-1)),从0开始报数,报到m-1的退出
  ,剩下的人继续从0开始报数。求胜利者的编号。
  我们知道第一个人(编号一定是(m-1)%n) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
  k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
  并且从k开始报0。
  现在我们把他们的编号做一下转换:
  k --> 0
  k+1 --> 1
  k+2 --> 2
  ...
  ...
  k-3 --> n-3
  k-2 --> n-2
  序列1: 0, 1, 2, 3 … n-2, n-1
  序列2: 0, 1, 2, 3 … k-1, k+1, …, n-2, n-1
  序列3: k, k+1, k+2, k+3, …, n-2, n-1, 1, 2, 3,…, k-2,
  序列4:0, 1, 2, 3 …, 5, 6, 7, 8, …, n-3, n-2
  变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解               吗?!!变回去的公式很简单,相信大家都可以推出来:
  ∵ k=m%n;
  ∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n
  ∴x'= (x+ m%n)%n = (x+m)%n
  得到 x‘=(x+m)%n
  如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下           面写递推公式:
  令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n].
  递推公式:
  f[1]=0;
  f[i]=(f[i-1]+m)%i; (i>1)
  有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结果是f[n]。我们输出f[n]由于是逐级递推,不需要保存每个,程序也是异常简单:(注意编号是0 -- n-1)
  #include <stdio.h>
  int main(void)
  {
  int n, m, i, s=0;
  printf ("N M = ");
  scanf("%d%d", &n, &m);
  for (i=2; i<=n; i++)
  s=(s+m)%i;
  printf ("The winner is %d\n", s);
  return 0 ;
  }
  时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题了。可见,适当地运用数学策略,不仅可以让编程变得简单,而且           往往会成倍地提高算法执行效率。
  参照上面提供的思路,我认为可以类似的得到一个更易于明白的方法,设有(1,2,3,……,k-1,k,k+1,……,n)n个数,当k出列时,那么有
  k+1 -->1
  k+2 -->2
  ...
  ...
  n -->n-k
  1 -->n-k+1
  ...
  ...
  k-1 -->n-1
  由上面一组式子可以推出,若知道新产生的n-1个数中某个数x,那么很显然可以推出x在原数列里的位置,即x‘=(x+k)%n,由此,我们可以得到一个递推公式
  f[1]=1
  f[n]=(f[n-1]+k)%n (n>1)
  如果你认为上式可以推出约瑟夫环问题的解,很不幸,你错了,上面的递推公式中,在某种情况下,f[n-1]+k会整除n,如n=2,k=3,这时我们修要对上式进行修正,
  f[n]=(f[n-1]+k)%n;if(f[n]==0)f[n]=n;
  问题得解。 程序代码如下:
  #include<stdio.h>
  int main()
  {
  int n,k,s=1;
  scanf("%d%d",&n,&k);
  for(int i=2;i<=n;i+=1)
  {
  s=(s+k)%i;
  if(s==0)s=i;
  }
  printf("ans=%d\n",s);
  return 0;
  }
  当然,我们还可以用递归方法解决此问题:
  #include<stdio.h>
  int main()
  {
  int jos(int n,int k);
  int n,k,s;
  scanf("%d%d",&n,&k);
  s=jos(n,k);
  printf("ans=%d\n",s);
  return 0;
  }
  int jos(int n,int k)
  {
  int x;
  if(n==1)x=1;
  else {x=(jos(n-1,k)+k)%n;if(x==0)x=n;}
  return x;
  }

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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