`
索菲亚.  ぅ
  • 浏览: 16410 次
  • 性别: Icon_minigender_2
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

约瑟夫问题的数学方法

    博客分类:
  • Math
阅读更多

无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达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]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

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

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

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

#include <stdio.h>
int 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 %d\n", s+1);
}

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

分享到:
评论

相关推荐

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

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

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

    通过这个故事,我们不仅了解了约瑟夫问题的基本概念,还学会了如何运用因式分解的方法来解决问题。这对于培养孩子们的逻辑思维能力和解决问题的能力非常有帮助。同时,通过这样的故事形式,也能让孩子们更加喜欢数学...

    约瑟夫问题代码,约瑟夫问题代码

    动态规划方法常用于解决约瑟夫问题的变种,例如当淘汰规则不是固定数值而是变化的。这种方法通常使用一个数组或矩阵来存储已计算出的结果,避免重复计算。 4. **递归实现**: 对于较小的问题规模,可以使用递归...

    约瑟夫问题的由来和简介

    在数学和算法的世界中,约瑟夫问题是一个经典案例,它的故事和问题结构都蕴含了丰富的数学思想和策略。约瑟夫问题最初来源于17世纪法国数学家约瑟夫·加斯帕的故事,该问题不仅是算法设计的基石,同样也在博弈论中...

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

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

    matlab解决约瑟夫问题

    约瑟夫问题源自一个经典的数学问题,该问题描述了这样的场景:N个人围成一个圈,并按照某种规则依次淘汰,直到只剩下一个人为止。具体规则是:从某人开始报数,数到指定数字(M)的人将被淘汰出局,然后从下一个人...

    Josephus 约瑟夫问题(POJ)

    约瑟夫问题,源自古罗马历史的一个有趣的故事,是由数学家约瑟夫·弗拉基米尔提出的。问题的基本设定是:一群人站成一个圆圈,从某人开始按顺时针方向计数,每数到特定数值的人将被排除,然后从下一个人继续计数,...

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

    约瑟夫问题,又称“约瑟夫环”或“猴子选大王”,是一个著名的理论问题,源自古希腊的数学家约瑟夫·弗拉基米尔。这个问题的基本设定是:有一群人围成一个圈,从某个人开始按顺时针方向编号,然后从第一个人开始报数...

    约瑟夫环约瑟夫环约瑟夫环约瑟夫环约瑟夫环

    理解并掌握解决约瑟夫环问题的方法,对于提升编程思维和算法能力具有重要的实践价值。 总的来说,约瑟夫环问题是一个经典的理论与实践相结合的算法题目,它涉及到链表操作、动态规划、矩阵运算等多方面的知识,对...

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

    总结来说,约瑟夫环问题主要涉及到循环链表的操作、数据结构的应用以及规律的发现和利用,是计算机科学和数学中的一种有趣且具有挑战性的问题。通过这个问题,我们可以学习到如何设计算法来解决复杂问题,并理解数据...

    001.约瑟夫问题_约瑟夫问题_

    约瑟夫问题的解法不仅限于基础的编程技巧,还可以运用到图论、组合数学甚至线性代数等领域。例如,用矩阵快速幂来解决跳跃式约瑟夫问题,可以极大地提高计算效率。 此外,约瑟夫问题在实际应用中也有其价值。例如,...

    约瑟夫问题面向对象解法报告书(C++版)

    在本报告书中,约瑟夫问题及其扩展的求解采用了面向对象的编程方法,特别是使用C++语言。面向对象编程(OOP)是一种编程范式,它使用“对象”的概念来封装数据和代码,以增强代码的重用性和可维护性。在约瑟夫问题中...

    三种结构求解约瑟夫问题1

    以上三种结构都可以有效地解决约瑟夫问题,选择哪种方法取决于具体的应用场景和性能需求。在实际编程实现中,还需要考虑优化算法效率,例如使用递归或循环,以及如何有效地处理边界条件和初始状态。同时,对于大规模...

    用单链表解决约瑟夫问题 C语言实现

    这个问题可以通过数学方法求解,但更常见的是利用数据结构和算法来模拟这一过程。 #### 数据结构选择 本例中选择了单链表作为数据结构的基础,特别是循环单链表,因为它能够很好地模拟圆形排列的特点。每个节点...

    约瑟夫问题

    约瑟夫问题,又称为约瑟夫环问题,是一个源自古希腊的数学趣题,它在计算机科学领域中被广泛用作算法设计的实例。这个问题的基本情景是:有一群人围成一个圈,从某个人开始按顺时针方向依次报数,每次报到特定数字的...

    约瑟夫问题程序设计书

    《约瑟夫问题》是计算机科学领域中一个经典的问题,源于古罗马的传说,由Josephus Flavius提出。在程序设计中,约瑟夫问题通常被用来展示递归、循环和链表等数据结构的应用。这个问题描述如下:n个人围成一圈,从第...

    数据结构 约瑟夫 程序编程问题

    约瑟夫问题源于一个数学谜题,它描述的是:有 n 个人围成一圈,按顺序报数,每次报到 m 的人出圈,直到最后剩下一个人。问题在于找出最后剩下的那个人是第几个。 #### 三、数据结构基础:链表 在解决约瑟夫问题时...

    约瑟夫问题设计书(c++)

    约瑟夫问题源自古罗马著名史学家Josephus提出的数学难题,通常被称为Josephus问题。该问题的基本场景是编号为1至n的n个人按顺时针方向围坐成一圈,每个人都持有特定的密码Ki(整数),根据一定的规则依次出圈,最终...

Global site tag (gtag.js) - Google Analytics