文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 约瑟夫问题详解(C C++)
侵权投诉

约瑟夫问题详解(C C++)

假设n个竞赛者排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。

Josephus 约瑟夫 问题

假设n个竞赛者排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。

无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较麻烦,而且时间复杂度高达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

变换后就完完全全成为了(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>

main()

{

第1页

你可能喜欢

  • 约瑟夫环实验报告
  • 数据结构课程设计约瑟夫环
  • 登录模块设计
  • 面试的问题
  • 问题解决
  • 加减乘除运算
  • Java笔记
  • C语言冒泡排序

热门文档

相关文档

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题...利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:有 n 个人(n>=1)围坐在...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题...约瑟夫问题的描述是: 个人按顺时针方向围坐一圈, 约瑟夫问题的描述是:编号为 1...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题...实验一 线性表实现方法实验名称: 实验一——线性表(约瑟夫问题) 学生姓名: 曾...

  • 约瑟夫问题

    约瑟夫奈 17页 免费 约瑟夫 2页 2财富值 新版约瑟夫问题 2页 1财富值 约瑟夫问题详解(C C++) 8页 1财富值 约瑟夫问题的研究 3页 10财富值 约瑟夫环 3页 ...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题...1.循环单链表求解约瑟夫问题。 #include<stdio.h> #include<stdlib.h> ...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题...以下是约瑟夫问题 C++语言描述的源代码: #include<iostream> using namespace std...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题的研究 3页 4下载券 约瑟夫环 3页 免费 约瑟夫斯问题 11页 3下载券喜欢此文档...

  • 约瑟夫问题

    约瑟夫 2页 2财富值 新版约瑟夫问题 2页 1财富值 约瑟夫问题详解(C C++) 8页 1财富值 约瑟夫问题的研究 3页 10财富值 约瑟夫环 3页 免费 约瑟夫斯问题 11...

  • 于亭亭约瑟夫问题

    约瑟夫问题的研究 3页 4下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫环...(约瑟夫中为3)y存活人数(约瑟夫中为2) unsigned char i,j,w=0;//中间变量...

  • 约瑟夫问题

    新版约瑟夫问题 2页 1下载券 约瑟夫问题详解(C C++) 8页 1下载券 约瑟夫问题的研究 3页 4下载券 约瑟夫环 3页 免费 约瑟夫斯问题 11页 3下载券喜欢此文档...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email