有趣的约瑟夫问题及解决办法
 2015.03.31    |      C/C++    |     AilsonJack    |     暂无评论    |     955 views
广告位C招租:1
By: Ailson Jack
Date: 2014-05-24
个人博客: http://www.only2fire.com/
<p style="text-indent: 2em;">今天给大家讲讲约瑟夫问题是什么,并且我提供了一种约瑟夫问题的解决办法。对于不知道约瑟夫是谁的人来说,就更不用提什么是约瑟夫问题了。那么问题来了,约瑟夫是谁,约瑟夫问题又是个什么东西。</p><p style="text-indent: 2em;">首先来个解释吧,约瑟夫问题,有时也称为约瑟夫置换,是一个出现在计算机科学和数学中的问题。特别是对于学习过数据结构的人来说,在书上看到解决这个问题的题目,可能都不下5遍吧。在计算机编程的算法中,类似的问题又称为<span style="color: rgb(255, 0, 0);">约瑟夫环</span>或者<span style="color: rgb(255, 0, 0);">丢手绢问题</span>。</p><p style="text-indent: 2em;">约瑟夫(Josephus)是谁,约瑟夫是著名的犹太历史学家,那么约瑟夫问题又是个什么东西呢。其实我并不太清楚约瑟夫的什么生平经历,但是关于约瑟夫问题,倒是有一个小故事给大家讲一讲,这个故事就是约瑟夫问题的原型。好了,下面来个大家讲故事了<img src="/UEditor/dialogs/emotion/images/face/i_f29.gif"/>,据说在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。</p><p style="text-indent: 2em;">从上面的故事,大家至少可以知道,约瑟夫虽然是个历史学家,但是他的数学学的也不赖嘛<img src="/UEditor/dialogs/emotion/images/face/i_f07.gif"/>。</p><p style="text-indent: 2em;">约瑟夫问题并不难,求解的方法也非常的多,我这里提供一个循环链表的解决方法,为什么用循环链表,因为我看那个故事里面的人都是手拉手围成一个圆圈的嘛<img src="/UEditor/dialogs/emotion/images/face/i_f03.gif"/>。</p><p style="text-indent: 0em;">&nbsp;&nbsp;这里是我用CodeBlocks编写的程序,什么是CodeBlocks,以及如何使用,大家可以参考我的博文:<a href="http://www.only2fire.com/archives/12.html" target="_blank"><span style="color: rgb(255, 0, 0);">CodeBlocks 安装 配置 使用 一条龙 超详细</span></a>。CodeBlocks其实还是挺好用的。我的源代码下载地址:<a class="btn btn-success" href="https://pan.baidu.com/s/1jGj8YDg" target="_blank">点此下载</a>&nbsp; 密码:<span style="color: rgb(255, 0, 0);">glf4</span>。</p><p style="text-indent: 2em;">下面是我写的程序源代码,大家看看,就知道是怎么解决的了:</p><p style="text-indent: 2em;"><span style="color: rgb(255, 0, 0);">注:</span>可以通过修改<span style="color: rgb(255, 0, 0);">main()</span>函数中的<span style="color: rgb(255, 0, 0);">Start</span>,<span style="color: rgb(255, 0, 0);">Count</span>,<span style="color: rgb(255, 0, 0);">length</span>这3个参数来改变游戏的规则,大家可以试试。</p><pre class="brush:cpp;toolbar:false PrismJs">#include&nbsp;&lt;stdio.h&gt; #include&nbsp;&lt;stdlib.h&gt; /* *功能:约瑟夫问题解决办法(循环链表解决) *By:Ailson&nbsp;Jack *Date:2014.05.24 */ #define&nbsp;error&nbsp;&nbsp;&nbsp;&nbsp;0 #define&nbsp;ok&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1 typedef&nbsp;int&nbsp;ElementType; typedef&nbsp;struct&nbsp;CycleListNode&nbsp;Node; typedef&nbsp;struct&nbsp;CycleListNode&nbsp;*ptrNode; struct&nbsp;CycleListNode//循环链表结点 { &nbsp;&nbsp;&nbsp;&nbsp;ElementType&nbsp;data;//数据区 &nbsp;&nbsp;&nbsp;&nbsp;ptrNode&nbsp;next;//指向下一个结点 }; //函数声明 //约瑟夫问题解决办法(循环链表解决) void&nbsp;Josephus(ptrNode&nbsp;list,int&nbsp;start,int&nbsp;count,int&nbsp;length); //创建循环链表头结点 int&nbsp;CycleList_CreateNode(ptrNode&nbsp;*list); //初始化循环链表,并且最后丢掉链表头结点,链表的数据为1&nbsp;-&gt;&nbsp;length void&nbsp;CycleList_Init(ptrNode&nbsp;*list,int&nbsp;length); //删掉循环链表中从表头数的第position个位置的数据 //最终将头结点变为删除前那个结点的下一个结点 void&nbsp;CycleList_Delete(ptrNode&nbsp;*list,int&nbsp;position); //查找循环链表中数据元素是Start的结点的位置,并且将该节点设为新的起始结点s void&nbsp;CycleList_Find(ptrNode&nbsp;*list,ElementType&nbsp;Start); //打印循环链表中的数据 void&nbsp;Prin_CycleList(ptrNode&nbsp;list,int&nbsp;length); int&nbsp;main(void) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Start=1;//起始计数位置 &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Count=3;//第Count个位置的结点出局 &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;length=41;//循环链表的长度 &nbsp;&nbsp;&nbsp;&nbsp;ptrNode&nbsp;list; &nbsp;&nbsp;&nbsp;&nbsp;CycleList_CreateNode(&amp;list); &nbsp;&nbsp;&nbsp;&nbsp;CycleList_Init(&amp;list,length); &nbsp;&nbsp;&nbsp;&nbsp;Prin_CycleList(list,length); &nbsp;&nbsp;&nbsp;&nbsp;Josephus(list,Start,Count,length); &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(1) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; } //约瑟夫问题解决办法(循环链表解决) void&nbsp;Josephus(ptrNode&nbsp;list,int&nbsp;start,int&nbsp;count,int&nbsp;length) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i=1; &nbsp;&nbsp;&nbsp;&nbsp;CycleList_Find(&amp;list,start); &nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;\r\n约瑟夫问题解决开始....\r\n&quot;); &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&lt;=length) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CycleList_Delete(&amp;list,count); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;\r\n约瑟夫问题解决结束\r\n&quot;); } //创建循环链表头结点 int&nbsp;CycleList_CreateNode(ptrNode&nbsp;*list) { &nbsp;&nbsp;&nbsp;&nbsp;*list=(ptrNode)malloc(sizeof(struct&nbsp;CycleListNode)); &nbsp;&nbsp;&nbsp;&nbsp;if(*list==NULL) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;Out&nbsp;of&nbsp;Space...\r\n&quot;); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;error; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;(*list)-&gt;next=NULL; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;ok; } //初始化循环链表,并且最后丢掉链表头结点,链表的数据为1&nbsp;-&gt;&nbsp;length void&nbsp;CycleList_Init(ptrNode&nbsp;*list,int&nbsp;length) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i=1; &nbsp;&nbsp;&nbsp;&nbsp;ptrNode&nbsp;newNode; &nbsp;&nbsp;&nbsp;&nbsp;ptrNode&nbsp;FirstNode; &nbsp;&nbsp;&nbsp;&nbsp;FirstNode=*list; &nbsp;&nbsp;&nbsp;&nbsp;while(i&lt;=length)//i从1到&nbsp;length &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newNode=(ptrNode)malloc(sizeof(struct&nbsp;CycleListNode)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newNode-&gt;data=i; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*list)-&gt;next=newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*list)=newNode; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;(*list)-&gt;next=FirstNode-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;*list=FirstNode-&gt;next; } //删掉循环链表中从表头数的第position个位置的数据 //最终将头结点变为删除前那个结点的下一个结点 void&nbsp;CycleList_Delete(ptrNode&nbsp;*list,int&nbsp;position) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i=1; &nbsp;&nbsp;&nbsp;&nbsp;ptrNode&nbsp;tmp; &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(position==1) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp=*list; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(tmp-&gt;data!=(*list)-&gt;next-&gt;data) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*list=(*list)-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;%d&nbsp;&quot;,(*list)-&gt;next-&gt;data); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*list)-&gt;next=tmp-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*list=tmp-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;free(tmp); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp=NULL; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&lt;position-1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*list)=(*list)-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp=(*list)-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;%d&nbsp;&quot;,tmp-&gt;data); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*list)-&gt;next=(*list)-&gt;next-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;free(tmp); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp=NULL; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*list=(*list)-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;} } //查找循环链表中数据元素是Start的结点的位置,并且将该节点设为新的起始结点 void&nbsp;CycleList_Find(ptrNode&nbsp;*list,ElementType&nbsp;Start) { &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;((*list)-&gt;data!=Start) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*list=(*list)-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;} } //打印循环链表中的数据 void&nbsp;Prin_CycleList(ptrNode&nbsp;list,int&nbsp;length) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i=1; &nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;打印循环链表...\r\n&quot;); &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&lt;=length) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;%d&nbsp;&quot;,list-&gt;data); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list=list-&gt;next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;\r\n结束打印\r\n&quot;); }</pre><p style="text-indent: 2em;">下面是程序的运行结果:</p><p style="text-align:center"><img src="/uploads/AilsonJack/2018.08.17/1534498116478304.png" onclick="preview_image(&#39;/uploads/AilsonJack/2018.08.17/1534498116478304.png&#39;)"/></p><p style="text-indent: 2em;">以上就是对约瑟夫问题的解决方法啦,大家有不明白的可以留言哟。<br/></p>
欢迎关注博主的公众号呀,精彩内容随时掌握:
热情邀请仔细浏览下博客中的广告,万一有对自己有用或感兴趣的呢。◕ᴗ◕。。
如果这篇文章对你有帮助,记得点赞和关注博主就行了^_^,当然了能够赞赏博主,那就非常感谢啦!
注: 转载请注明出处,谢谢!^_^
广告位C招租:2
广告位C招租:3
转载请注明来源: 本文链接:  By: AilsonJack
有趣的约瑟夫问题及解决办法  |  说好一起走
广告位D招租:1
广告位D招租:2
暂无评论,要不要来个沙发
发表评论

 
广告位E招租
Copyright © 2015~2021  说好一起走   保留所有权利   |  百度统计  蜀ICP备15004292号