当前位置:鱼C工作室 >数据结构和算法 > 查看文章

线性表13|约瑟夫问题 – 数据结构和算法18

线性表13:约瑟夫问题

 

让编程改变世界

Change the world by program


 

约瑟夫问题

 

据说著名犹太历史学家 Josephus有过以下的故事:

在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

 

理论付诸实践

 

小甲鱼:理论为什么能够付诸实践?

热心鱼油:你TMD在说啥*&(*%@……!

小甲鱼:我的意思是约瑟夫问题跟我们讲的循环链表有啥关系?

某女鱼油:它们都带套!

小甲鱼:真聪明,亲一个^_^

小甲鱼:对的,约瑟夫问题里边41个人是围成一个圆圈,我们的循环链表也是一个圆圈,所以可以模拟并让计算机运行告诉我们结果!

 

问题:用循环链表模拟约瑟夫问题,把41个人自杀的顺序编号输出。

代码:Josephus.c

 

提高挑战难度:

编号为1~N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数,可以自由输入),开始人选一个正整数作为报数上限值M,从第一个人按顺时针方向自1开始顺序报数,报道M时停止报数。报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止。

 

答案在这里!


为您推荐

报歉!评论已关闭.