文档章节

约瑟夫环

mskk
 mskk
发布于 2017/03/20 22:41
字数 987
阅读 20
收藏 0

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

 

    可以把问题转换成:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。则所得的解加1即为原问题的解;

      一般我们采用一个循环队列来模拟约瑟夫环的求解过程,但是如果n比较大的时候,采用模拟的方式求解,需要大量的时间来模拟退出的过程,而且由于需要占用大量的内存空间来模拟队列中的n个人,并不是一个很好的解法。
在大部分情况下,我们仅仅需要知道最后那个人的编号,而不是要来模拟一个这样的过程,在这种情况下,可以考虑是否存在着一种数学公式能够直接求出最后那个人的编号。

    我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
我们先看第一个人出列后的情况,显而易见,第一个出列的人的编号一定是m%n-1,这个人出列后,剩下的n-1个人组成了一个新的约瑟夫环,这个约瑟夫环的第一个人在最开始的环中的编号是k=m%n(就是第一个出列的人的下一个)
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
    事实上,第一个出列的人的编号 m%n-1==k-1,在他被出列后,剩下的人又映射成为一个新的环:

   原编号   新编号
    k   ---   0
    k+1 ---   1
    k+2 ---   2
     ...  ....

   n-1  --- n-k-1

    0   ---  n-k

    1   --- n-k+1

        ...  ...

   k-3 ---   n-3

   k-2 ---  n-2

  (k-1已经被出列)

--------------------------------------------------一个循环

    可以看出,这就是原问题中把n替换成n-1的情况,设最终胜利的那个人在这种编号环境里(已经出列一个元素,编号范围为0 ------- n-2)的编号为x,则我们可以求出这个人在原编号环境(初始编号范围 0----n-1)下的编号(x+k)%n.

    我们用f(n)表示n个人的情况(编号环境)下的胜利者的编号,则我们要求的为f(n);

    那么如何知道n-1个人下面的这个x呢,yes,就是n-2个人情况下得到的x'倒推回去,那么如何知道n-2情况下的x'呢,当然是求n-3个人,这就是一个递归的过程  f(n) = (f(n-1)+m)%n.

    当最后剩下一个人(最新编号为0)的时候,无论m为几,这个人总是胜利者,即f(1)=0;

    根据以上推理可以得到递推式
        f(1) = 0
        f(n) = (f(n-1)+m)%n
    那么我们要求f(n),就从f(1)倒推回去即可.

(注意,我们这个算法是把编号为1---n 用 0----n-1替换的,所以最后求出来的编号+1才是最初问题的解,即f(n)+1).

  1.  int f(int n, int m)  
  2.    {  
  3.        int r = 0;//即f(1)=0;  
  4.        for(int i = 2; i <= n; i++)  
  5.            r = (r + m) % i;//即f(i)=[f(i-1)+m]%n;  
  6.        return r + 1; //即f(n)=1;  
  7.     }</span>  

 

       这种方法比模拟的方法快多了,我们在碰到问题的时候,可以想一想是否有数学公式来求解 。

       参考出处:Jackie`s blog

本文转载自:

mskk
粉丝 4
博文 207
码字总数 10348
作品 0
昆山
程序员
私信 提问

暂无文章

32位与64位Linux系统下各类型长度对比

64 位的优点:64 位的应用程序可以直接访问 4EB 的内存和文件大小最大达到4 EB(2 的 63 次幂);可以访问大型数据库。本文介绍的是64位下C语言开发程序注意事项。 1. 32 位和 64 位C数据类型...

mskk
25分钟前
6
0
Vue 实现点击空白处隐藏某节点(三种方式:指令、普通、遮罩)

在项目中往往会有这样的需求: 弹出框(或Popover)在 show 后,点击空白处可以将其 hide。 针对此需求,整理了三种实现方式,大家按实际情况选择。 当然,我们做项目肯定会用到 UI 框架,常...

张兴华ZHero
32分钟前
7
0
SpringBoot激活profiles你知道几种方式?

多环境是最常见的配置隔离方式之一,可以根据不同的运行环境提供不同的配置信息来应对不同的业务场景,在SpringBoot内支持了多种配置隔离的方式,可以激活单个或者多个配置文件。 激活Profi...

恒宇少年
33分钟前
7
0
PDF修改文字的方法有哪些?怎么修改PDF文件中的文字

PDF修改文字一直以来都是一个难以解决的问题,很多的办公族在办公的时候会有修改PDF文件中的文字的需要,可是PDF文件一般是不能进行编辑和修改的,难道就没有什么办法解决这个问题了嘛?不要...

趣味办公社
36分钟前
5
0
企业组织中采用服务网格的挑战

作者:Christian Posta 译者:罗广明 原文:https://blog.christianposta.com/challenges-of-adopting-service-mesh-in-enterprise-organizations/ 编者按 本文作者介绍了企业组织采用服务网...

jimmysong
46分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部