当前位置: 首页 > article >正文

约瑟夫环问题(队列,链表实现)- c++

1.关于约瑟夫问题

约瑟夫斯领导犹太人反抗罗马帝国的统治,在与罗马军队的激烈战斗中,与士兵们一同被困在一个山洞里。总共有41人,约瑟夫斯希望向罗马军队投降,但他的士兵们却坚决拒绝,宁愿死也不愿被敌人俘虏。面对这种困境,约瑟夫斯需要找到一种既能实现投降目的,又能确保自己安全的解决方案。

于是,他提出了一个方案:让大家围成一个圈,按照顺时针的顺序,每数到第m个人就杀掉,这个过程不断重复,直到最后只剩下一个人。这样,通过数学计算和策略安排,约瑟夫斯能够确保自己不被处决,同时实现投降的目的。士兵们接受了这个方案,并按照约瑟夫斯的要求行动起来。

例如,有7个人围成一圈,按顺序编号,约定数到3的人自杀,那么顺序如下:
在这里插入图片描述
第一次报数: 3号被淘汰。
第二次报数: 6号被淘汰。
第三次报数: 2号被淘汰。
第四次报数: 7号被淘汰。
第五次报数: 5号被淘汰。
第六次报数: 1号被淘汰。
最后存活的十是4号。

2.题目描述

对于给定的n和m,分别表示总人数和要报的数字,求最后剩余的人是几号?

输入:7 3
输出:4

3.算法1 (队列实现)

思考报数过程,其报数规律如下:

 1 2 3 4 5 6 7 (3应该被淘汰,接下来的报数顺序应该是如下)4 5 6 7 1 2    (数到7后继续从1开始,模拟环,此时6应该被淘汰,变成)7 1 2 4 5      (同上,接下来2该被删除,变成)4 5 7 1         (7被删除)1 4 5			(5被删除)1 4              (1被删除)4 //即存活的人

可以发现,数字顺序的变化规律,就是将报到m之前的人(m-1)移到最后面来模拟环,之后再删除要删除的数即可。在数列的前面进行删除操作,在数列后面进行删除操作,故可以采用队列这种数据结构。
实现函数如下:

/* 队列求解 */
int getAnsByQueue(int n,int m){queue<int> q;for(int i
http://www.lryc.cn/news/2419448.html

相关文章:

  • 系统编程之文件IO(四)——初级IO(open、close、write、lseek)
  • JS中clientWidth offsetWidth innerWidth scrollWidth等区分
  • 经纬度有哪些格式
  • WAV文件格式详解
  • Ubuntu (安装问题,包括系统更新和软件安装)
  • 软件工程与计算II-12-详细设计
  • i386和X86各是什么意思 与arm的区别
  • 人脸对齐 matlab,常用几种人脸对齐算法ASM/AAM/CLM/SDM
  • 计算机网络知识之URL、IP、子网掩码、端口号
  • 磁力链接转换为种子文件 magnet to torrent
  • 深入浅出声学系统频率响应
  • Android开发者必须收藏的8个开源库,值得收藏!_android 开源鉴黄
  • 关于System.currentTimeMillis()的理解
  • python的np.meshgrid函数
  • 数字后端概念——shielding
  • 用hist()绘制直方图
  • [转]推荐一款新型 Java 网站内容管理系统,灵活、易用,运行稳定,轻松管理建设网站(附源码)
  • Linux tar命令详解,Linux备份解压文件_linux tar备份文件
  • 新手怎么炒外汇?
  • 【合唱】男女差八度的科学解释
  • handoop job工作运行的机制与原理详解
  • 20款最流行的免费定性数据分析工具
  • 主数据管理和实施
  • Linux 详解:最完整的入门指南_linux菜鸟入门指南
  • 【游戏】如何开发一款游戏:游戏开发流程及所需工具
  • 飞鸡:从小训练飞行的鸡能飞行吗?为什么野鸡能飞吗?是同一品种吗?今天自由思考
  • c++_ifstream,ofstream读写文件
  • 使用rkhunter检测Linux的rootkit
  • jdk源码写过注释后debug提示source code does not match the bytecode
  • nodejs中的__filename和__dirname的使用说明