约瑟夫环数据结构顺序表实现(数据结构顺序表代码)

约瑟夫环数据结构顺序表实现

这段代码会有一点绕，请大家耐心的分析读完，毕竟心机吃不了热豆腐。上述代码中”//小孩报数前，先让first和helper移动k-1次“，也就是让第k个小孩从1开始数。

首先我们约定假如有五个人：n=5,k=1//从第k个人开始数1m=2//数两下一个人出列

先让一个辅助指针（变量），指向first节点2.然后通过一个while循环遍历该环形链表，当curBoy（当前的节点）==first（首个节点）就结束了。

先创建第一个节点first指向该节点，并形成环状2.后面当我们创建一个新的节点，就把这个节点加入到已有的环形链表中即可。

数据结构顺序表代码

上端代码中的第一个创建的小孩（节点）是比较特别的，需要构成一个环状，然后后来的小孩（节点）一个个添加，把新的节点加入到原有的环形链表中即可。

仅仅是要求出最后的胜利者的序号,而不是要读者模拟整个过程。因此如果要追求效率,就要打破常规,实施一点数学策略。

题目中30个人围成一圈,因而启发我们用一个循环的链来表示,可以使用结构数组来构成一个循环链。结构中有两个成员,其一为指向下一个人的指针,以构成环形的链;其二为该人是否被扔下海的标记,为1表示还在船上。从第一个人开始对还未扔下海的人进行计数,每数到9时,将结构中的标记改为0,表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

循环链表约瑟夫环

高达O(nm),当n,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间内出结果的。我们注意到

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

约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。

(1)由于对于每个人只有死和活两种状态,因此可以用布尔型数组标记每个人的状态,可用true表示死,false表示活。