`
yuelven
  • 浏览: 8361 次
  • 性别: Icon_minigender_1
  • 来自: 广州
最近访客 更多访客>>
社区版块
存档分类
最新评论

约瑟夫问题的数学方法

阅读更多

转自http://www.608088.com/show-1476-1.html

无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达 O(nm),当n,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号,而不是 要读者模拟整个过程。因此如果要追求效率,就要打破常规,实施一点数学策略。

为了讨论方便,先把问题稍微改变一下,并不影响原意:

问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的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-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'=(x+k)%n

如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

递推公式
f[1]=0;
f=(f[i-1]+m)%i;  (i>1)

有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1

由于是逐级递推,不需要保存每个f,程序也是异常简单:

#include <stdio.h>

main()
{
  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 %dn", s+1);
}

 

这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题了。可见,适当地运用数学策略,不仅可以让编程变得简单,而且往往会成倍地提高算法执行效率。

分享到:
评论

相关推荐

    约瑟夫问题的数学解决方法

    约瑟夫问题的数学解决方法,可以输出淘汰的人的顺序和最后的赢家。

    【约瑟夫问题c++】约瑟夫问题与因式分解小学生数学故事.docx

    【约瑟夫问题c++】约瑟夫问题与因式分解小学生数学故事.docx

    POJ 1012 约瑟夫问题的数学解法及分析

    POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析

    用单链表解决约瑟夫环问题

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

    约瑟夫环是一个数学的应用问题.doc

    ~~~~~~~~约瑟夫环是一个数学的应用问题.doc

    约瑟夫问题(猴子选大王)数学解法

    约瑟夫问题是一个经典问题(猴子选大王) 有循环链表等多种解法,这里提供的是最简单的数学解法数学解法。

    约瑟夫环问题用C++代码实现

    8. 【题目】约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又...

    约瑟夫环(一个数学的应用问题)

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

    python实现约瑟夫问题

    约瑟夫问题(Josephus Problem)是一个古老的数学和计算机科学问题,它描述了一个古老的传说。问题的描述如下: 在古代,有N个人(编号从1到N)站成一圈。从编号为1的人开始,按照顺时针方向数到第M个人,然后将他...

    PHP实现约瑟夫环问题的方法分析

    先来看看网上比较常见的约瑟夫环问题描述:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1...

    现代应用数学方法

    一批又一批的工科研究生通过这门课程的学习,使自己的数学修养得到了显著的提高,并学到了许多在理论与实践中应用现代数学方法解决工程技术领域问题的基本方法。 本人首先建立了“高等分析”课程的框架并主讲该课程。...

    循环链表实现约瑟夫环问题

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

    约瑟夫问题代码

    约瑟夫问题代码 有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)

    Java递归实现约瑟夫环应用问题

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

    约瑟夫环问题C++源代码

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

    约瑟夫出圈问题

    约瑟夫问题: 这是 17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事: 15 个教徒和 15 个 非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个 办 法: 30 个人围成一...

    约瑟夫环问题

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

    约瑟夫问题+理论+应用+实现.zip

    约瑟夫问题,也被称为约瑟夫斯问题、约瑟夫环、约瑟夫游戏,是一个古老的数学和计算机科学问题。问题的背景源自传说中的犹太历史,讲述了约瑟夫和他的40个朋友在面对罗马士兵的时候,决定采用自杀的方式来避免被捕。...

    约瑟夫环问题的解决方案(C++版)

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

    acm约瑟夫问题教程

    约瑟夫问题

Global site tag (gtag.js) - Google Analytics