标签 数据结构 下的文章
 2015-03-31T16:20:49.296004    |      C/C++    |     AilsonJack    |     暂无评论    |     976 views
今天给大家讲讲约瑟夫问题是什么,并且我提供了一种约瑟夫问题的解决办法。对于不知道约瑟夫是谁的人来说,就更不用提什么是约瑟夫问题了。那么问题来了,约瑟夫是谁,约瑟夫问题又是个什么东西。首先来个解释吧,约瑟夫问题,有时也称为约瑟夫置换,是一个出现在计算机科学和数学中的问题。特别是对于学习过数据结构的人来说,在书上看到解决这个问题的题目,可能都不下5遍吧。在计算机编程的算法中,类似的问题又称为约瑟夫环或者丢手绢问题。约瑟夫(Josephus)是谁,约瑟夫是著名的犹太历史学家,那么约瑟夫问题又是个什么东西呢。其实我并不太清楚约瑟夫的什么生平经历,但是关于约瑟夫问题,倒是有一个小故事给大家讲一讲,这个故事就是约瑟夫问题的原型。好了,下面来个大家讲故事了,据说在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。从上面的故事,大家至少可以知道,约瑟夫虽然是个历史学家,但是他的数学学的也不赖嘛。约瑟夫问题并不难,求解的方法也非常的多,我这里提供一个循环链表的解决方法,为什么用循环链表,因为我看那个故事里面的人都是手拉手围成一个圆圈的嘛。  这里是我用CodeBlocks编写的程序,什么是CodeBlocks,以及如何使用,大家可以参考我的博文:CodeBlocks 安装 配置 使用 一条龙 超详细。CodeBlocks其实还是挺好用的。我的源代码下载地址:点此下载  密码:glf4。下面是我写的程序源代码,大家看看,就知道是怎么解决的了:注:可以通过修改main()函数中的Start,Count,length这3个参数来改变游戏的规则,大家可以试试。下面是程序的运行结果:以上就是对约瑟夫问题的解决方法啦,大家有不明白的可以留言哟。
编程语言CC++数据结构算法 阅读全文»
  • 1

  本站信息

目前本站共被浏览 154795 次
目前本站已经运行 3306 天
目前本站共有 165 篇文章
目前本站共有 6 条评论信息
目前本站共有 104 个标签
目前本站共有 0 条留言信息
网站创建时间: 2015年03月01日
最近更新时间: 2023年11月26日
Copyright © 2015~2023  说好一起走   保留所有权利   |  百度统计  蜀ICP备15004292号