循环链表解决约瑟夫环问题，有段代码不懂，有大神解释啊
[问题点数：40分]
循环链表解决约瑟夫环问题，有段代码不懂，有大神解释啊
[问题点数：40分]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
相关帖子推荐：
2014年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第四
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。请输入关键词：
约瑟夫问题
　　约瑟夫问题
　　这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
　　*问题分析与算法设计
　　约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
　　题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
　　约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。
　　假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。
　　C++代码示例:
　　#include&iostream&
　　void main()
　　int n,m,a[101],k,i,j, //计数器是从1开始的,所以100个人用101
　　cout&&&请输入参加游戏的玩家人数(不超过100人):&;
　　cin&&n;
　　cout&&&----------------------------------------&&&
　　if(n&100)
　　cout&&&玩家太多,请重新登陆此程序!&&&
　　cout&&&输入游戏中要玩的数字:&;
　　cin&&m;
　　cout&&&----------------------------------------&&&
　　for(i=1;i&=n;i++)
　　a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，
　　for(i=1;i&=n;i++){
　　if(a【i】==1){
　　j=j+a【i】;
　　if(j==m)
　　a【i】=0;
　　if(k==n){
　　num=i;
　　if(i==n)
　　cout&&&最后获胜的玩家是第 &&&num&&& 号玩家!&&&
　　cout&&&----------------------------------------&&&
　　写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法 很巧妙很简单 不过只能推出最后一个出列的人
　　无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
　　为了讨论方便，先把问题稍微改变一下，并不影响原意：
　　问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
　　我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）:
　　k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
　　并且从k开始报0。
　　现在我们把他们的编号做一下转换：
　　k --& 0
　　k+1 --& 1
　　k+2 --& 2
　　k-2 --& n-2
　　k-1 --& n-1
　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n
　　如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
　　令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
　　递推公式
　　f[1]=0;
　　f=(f+m) (i&1)
　　有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
　　由于是逐级递推，不需要保存每个f，程序也是异常简单：
　　#include &stdio.h&
　　int main()
　　int n, m, i, s=0;
　　printf (&N M = &); scanf(&%d%d&, &n, &m);
　　for (i=2; i&=n; i++) s=(s+m)%i;
　　printf (&The winner is %d\n&, s+1);
　　pascal
　　var n,m,i,s:
　　write('N M =');
　　read(n,m);
　　for i:=2 to n do
　　s:=(s+m)
　　writeln('The winner is ',s+1);
　　这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。
　　约瑟夫问题10e100版(from vijios)
　　描述 Description
　　n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。
　　输入格式 Input Format
　　一个正整数n，表示人的个数。输入数据保证数字n不超过100位。
　　输出格式 Output Format
　　一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。
　　样例输入 Sample Input
　　样例输出 Sample Output
　　时间限制 Time Limitation
　　各个测试点1s
　　注释 Hint
　　样例说明
　　当n=9时，退出圈子的人的编号依次为：
　　2 4 6 8 1 5 9 7
　　最后剩下的人编号为3
　　初见这道题，可能会想到模拟。可是数据实在太大啦！！
　　我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...
　　有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...
　　这样就好弄了！！
　　大体思路如下：
　　①read(a)
　　②b:=1,c:=1{b为某一组的元素个数，c为现在所加到的数}
　　③while c&a do (b:=b*2,c:=b+c){超过目标时停止加数}
　　⑥c:=c-b{退到前一组}
　　⑦x:=a-c{算出目标为所在组的第几个元素}
　　⑧ans:=x*2-1{求出该元素}
　　⑨write(ans)
　　有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~
　　var a,b,c:array[1..105]
　　la,lb,lc,i:
　　var i:
　　for i:=1 to 105 do c:=c+b;
　　for i:=1 to 104 do if c&9 then
　　c:=c+c div 10;
　　c:=c mod 10;
　　function cxiaoa:
　　var i:
　　cxiaoa:=
　　for i:=105 downto 1 do
　　if c&a then begin cxiaoa:=end
　　else if c&
　　var i:
　　for i:=1 to 105 do b:=b*2;
　　for i:=1 to 104 do if b&9 then
　　b:=b+b div 10;
　　b:=b mod 10;
　　var i,j:
　　for i:=1 to 104 do
　　if c&=b then c:=c-b else
　　j:=i+1;
　　while c[j]=0 do inc(j);
　　while j&i do
　　c[j]:=c[j]-1;
　　c[j-1]:=c[j-1]+10;
　　dec(j);
　　c:=c-b;
　　var i:
　　for i:=1 to 104 do
　　if a&c then a:=a-c else
　　a:=a-1;
　　a:=a+10;
　　a:=a-c;
　　var i,j:
　　for i:=1 to 105 do a:=a*2;
　　for i:=1 to 104 do if a&9 then
　　a:=a+a div 10;
　　a:=a mod 10;
　　if a[1]&0 then a[1]:=a[1]-1 else
　　while a[j]=0 do inc(j);
　　while j&1 do
　　a[j]:=a[j]-1;
　　a[j-1]:=a[j-1]+10;
　　dec(j);
　　a[1]:=a[1]-1;
　　for i:=105 downto 1 do if a&0 then begin j:=i;
　　for i:=j downto 1 do write(a);
　　readln(s);
　　la:=length(s);
　　for i:=la downto 1 do a:=ord(s[la+1-i])-ord('0');
　　b[1]:=1;
　　c[1]:=1;
　　while cxiaoa do
　　end.　　
决了一个约瑟夫环的问题，但是总觉帮助 这就是约瑟夫环问题的数学解 doing? C/C++ code //約瑟夫問題 #include stdio.h; count++; } printf( \n約琴夫排列： ); for(i = 0...
来自： - 最后更新于：
约瑟夫环的问题】 有17个人（编来处理这个问题并在下面写用数组实现约瑟夫环问题 *由m个人热闹了 这个问题都要面向对...
来自： - 最后更新于：
环链表做的约瑟夫环，可以给你);//建立好一个约瑟夫环 p=L; for(int是中英文的问题...
来自： - 最后更新于：
个程序，关于约瑟夫环的，只给出...
来自： - 最后更新于：
一只吃一只，问最后吃的是（C++）：但总出现问题，望高手指教 *p= new M[size+1]; 问题说具体一点+size-1; } 约瑟夫环。 很像约瑟夫环的问题阿，用链...
来自： - 最后更新于：
问题描述】 编号为程序哪里有问题呢？ 大虾帮帮...
来自： - 最后更新于：
环链表解决约瑟夫问题 要求用Java编如何使用的问题 我也正在写有C语言的约瑟夫环问题，算法思想一样，语言不是问题，很简单 约瑟夫问题可以看分就有说到约瑟夫问题，并有很精妙...
来自： - 最后更新于：
2、约瑟夫生者死者游戏 约瑟夫游戏的个乘客为止。问哪些位置是/starcake/blog/item/ea15176d22ebf5.html 约瑟夫环，网上例子...
来自： - 最后更新于：
约瑟夫环问题：有编号从1看问题出在哪儿啊？ C/C++ code //约瑟夫环问题\n",head->num); system("pause"); } 约瑟夫环，8行够了现的程序有问题啊，所建立 的...
来自： - 最后更新于：
问题描述： 约瑟夫问题的描述是：编的 C/C++ code /* title：约瑟夫问题的循环链表数为n进行约瑟夫实验 }; Node *Node::create地解决这个问题，后来想要自 *head, *p,*s; /* 输入问题条件 */ printf( 猴子...
来自： - 最后更新于：
本词条对我有帮助0
积木知识库中的词条内容仅供参考，如果您需要解决实际问题，建议您咨询相关领域专业人士
如果您认为本词条还需进一步完善，欢迎您也来参与编辑词条&&&&让我们共同来完善IT领域的百科全书
浏览该词条的网友还浏览了
最新收录词条
热门脚本语言：约瑟夫环的C语言数组的实现
本文给出了使用C语言数组解决约瑟夫环的一种方法,并得到了预期的结果.
菏泽学院计算机与信息工程系,山东,菏泽,274015
年，卷(期)
机标分类号
本文读者也读过
互动百科相关词
加载中，请稍候
．客服电话
&&8:00-11:30,13:00-17:00(工作日)【】【】【】【】
········
　　《全国专业技术人员计算机应用能力考试标准教程—word&2003中文字处理》严格根据..
定价：￥39.50
优惠价：￥29.60&&本书适合报考全国专业技术人员计算机应用能力考试“中文windows&xp操作系统”科目的..
定价：￥39.50
优惠价：￥29.60&&
············
············
　 　 　 　 　Copyright ©
() All Rights Reserved关于循环链表解决约瑟夫环的问题
[问题点数：20分，结帖人skeeterking]
关于循环链表解决约瑟夫环的问题
[问题点数：20分，结帖人skeeterking]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
相关帖子推荐：
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。