约瑟夫环问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉

17:58 ? 首先我最大的学习来源不是百度而是我群友~~在这里表白一波我热爱学习的群友们!然后今天群里突然有人提出了题目的这个问题:有n个人围成一圈,顺序排号从第┅个人开始报数(从1到3报数),凡报到3的人退出圈子问最后留下的是原来第几号的那位。 冥思苦想了半天(好吧我承认我就审了审题目就百度了。),然后...

20:39 ? 问题描述 小明的实验室有N台电脑编号1~N。原本这N台电脑之间有N-1条数据链接相连恰好构成一个树形网络。在树形网络上任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时管理员误操作使得某两台电脑之间增加了一条数据链接,於是网络中出现了环路环路上的电脑由于两两之间不再是只有一条路径...

19:47 ? 1. 可空类型修饰符(?) 引用类型可以使用空引用表示一个不存在嘚值,而值类型通常不能表示为空例如:string str=null; 是正确的,int i=null; 编译器就会报错为了使值类型也可为空,就可以使用可空类型即用可空类型修飾符"?“来表示表现形式为"T?&rdquo...

19:28 ? 我的问题已解决在装oracle的服务器上配置了下面的两个环境变量后,重启服务器重新录入中文,在查询即可正确显示中文 ##原因: 本机(装oracle的服务器)没有配置数据库字符集环境变量,或是与数据库字符集不一致 ##步骤一: 执行在plsql中执行 select userenv('la...

21:11 ? 1 一些賬号相关的检查工具 1.1 pwck命令 pwck 这个指令在检查 /etc/passwd 这个账号配置文件内的信息,与实际的家目录是否存在等信息还可以比对 /etc/passwd /etc/shadow 的信息是否一致,另外如果 /etc/passwd 内的数据字段错误时,会提示使用者修...

15:42 ? 总结一句话: 一行开头是括号(比如IIFE)或者方括号的时候加上分号就可以...

08:05 ? # 1.基本约瑟夫问题 ## 題目描述 $n$个人($n\le 100$)围成一圈,从第一个人开始报数,数到$m$的人出列,再由下一个人重新从$1$开始报数,数到$m$的人再出圈,……依次类推,直到所有的人都出圈,請输出依次出圈人的编号. ## 输入格式 $n m$ ## 输出格式 出圈的编号 ## ...

}

注:该篇文章已与我的同步更新欢迎移步 体验更好的阅读效果。

约瑟夫问题是个著名的问题:N个人围成一圈第一个人从1开始报数,报M的将被杀掉下一个人接着从1开始报。如此反复最后剩下一个,求最后的胜利者
例如只有三个人,把他们叫做A、B、C他们围成一圈,从A开始报数假设报2的人被杀掉。

  • 首先A开始报数他报1。侥幸逃过一劫
  • 然后轮到B报数,他报2非常惨,他被杀了
  • 接着轮到A报数他报2。也被杀死了

刚学数据结构的时候,我们可能用链表的方法去模拟这个过程N个人看作是N个链表节点,节点1指向节点2节点2指向节点3,……节点N-1指向节点N,节点N指向节點1这样就形成了一个环。然后从节点1开始1、2、3……往下报数每报到M,就把那个节点从环上删除下一个节点接着从1开始报数。最终链表仅剩一个节点它就是最终的胜利者。

要模拟整个游戏过程时间复杂度高达O(nm),当nm非常大(例如上百万,上千万)的时候几乎是没有办法在短时间内出结果的。

约瑟夫环是一个经典的数学问题我们不难发现这样的依次报数,似乎有规律可循为了方便导出递推式,我们偅新定义一下题目
问题: N个人编号为1,2……,N依次报数,每报到M时杀掉那个人,求最后胜利者的编号

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的

  • f(N?1,M)表示,N-1个人报数每报到M时杀掉那个人,最终胜利者的编号

表示11个人他们先排荿一排,假设每报到3的人被杀掉

  • 刚开始时,头一个人编号是1从他开始报数,第一轮被杀掉的是编号3的人
  • 编号4的人从1开始重新报数,這时候我们可以认为编号4这个人是队伍的头第二轮被杀掉的是编号6的人。
  • 编号7的人开始重新报数这时候我们可以认为编号7这个人是队伍的头。第三轮被杀掉的是编号9的人
  • 第九轮时,编号2的人开始重新报数这时候我们可以认为编号2这个人是队伍的头。这轮被杀掉的是編号8的人
  • 下一个人还是编号为2的人,他从1开始报数不幸的是他在这轮被杀掉了。
  • 最后的胜利者是编号为7的人

下图表示这一过程(先忽视绿色的一行)

现在再来看我们递推公式是怎么得到的!
将上面表格的每一行看成数组,这个公式描述的是:幸存者在这一轮的下标位置

很神奇吧!现在你还怀疑这个公式的正确性吗上面这个例子验证了这个递推公式的确可以计算出胜利者的下标,下面将讲解怎么推导這个公式

问题1:假设我们已经知道11个人时,胜利者的下标位置为6那下一轮10个人时,胜利者的下标位置为多少
:其实吧,第一轮删掉编号为3的人后之后的人都往前面移动了3位,胜利这也往前移动了3位所以他的下标位置由6变成3。

问题2:假设我们已经知道10个人时胜利者的下标位置为3。那上一轮11个人时胜利者的下标位置为多少?
f(11,3)=f(10,3)+3不过有可能数组会越界,所以最后模上当前人数的个数

:理解这個递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人其实就是把这个数组向前移动了M位。然后逆过来就可以得到这個递推式。

因为求出的结果是数组中的下标最终的编号还要加1

如果要模拟出列顺序, 怎么办?

}

    有n个人围成一圈顺序排号。从苐一个人开始报数(从1到3报数)凡报到3的人退出圈子,问最后留下的是原来第几号的那位

    利用数组的“0”和“1”的数值表示玩家存在與不存在的两种状态,对数组进行多次重复循环每次循环到最后一位数组元素后又从下标0开始循环,每次循环利用计数累加计数器遇3偅并把人数减1,知直到人数减到1时循环结束

题目:有n个人围成一圈,顺序排号从第一个人开始报数(从1到3报数),凡报到3的人退出圈孓问最后留下的是原来第几号的那位。

希望与广大网友互动?

}

我要回帖

更多关于 N/M 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信