约瑟夫环--上篇

December 21 , 2015

@(算法)[数据结构, 基本算法, 排序问题]

概述

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

问题来历

       据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏

       17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15 个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。

算法原理

  • 一群人围在一起坐成 环状(如:N)
  • 从某个编号开始报数(如:K)
  • 数到某个数(如:M)的时候,此人出列,下一个人重新报数
  • 一直循环,直到所有人出列 ,约瑟夫环结束

算法实践

       马上就要到圣诞节了,群里面举行了互相交换小礼物的活动,那么现在需要对参加的人员进行送礼物收礼物的随机人员分配。这里想用约瑟夫环的算法问题进行一个分组。

例如:

       现在有6个人,分别为因为字母ABCDEF。然后指定第K个人开始从1开始数,数到M的时候那个人出列。        按照约瑟夫环的算法来计算,假设K=1,M=5,那么结果就是:EDFBCA假设我是D,那么我就要收到E送给我的礼物,然后我要把准备好的礼物送给F,即形成了一个新的环链。

请实现如下问题:

  • 根据最后的报名人数进行约瑟夫环的计算,上面的K,M需进行随机数生成(都要在1-N的范围内,N为总人数)。
  • 列出收礼物的人和需要送给的人
  • 程序长期运行,每隔半个小时重新进行计算,运行时间为2015-12-22 12:00:00 至 2015-12-22 23:59:59
  • 将每次运算的程序结果和日志输出。
  • 语言不限,格式不限,要求人类能看懂,最好是web版本。

游客评论区

#1 站长 2015-12-21 15:50:35 / 回复

稍后会放出答案。


发表评论

(请不要填写空的评论)
提交评论 使用QQ登录