逆序数和约瑟夫
§ 2 全排列及其逆序数
一、全排列
个不同元素排成一列。
可将个不同元素按1~ 进行编号，则个不同元素的全排列可看成这个自然数的全排列。
个不同元素的全排列共有种。
逆序的定义：取一个排列为标准排列，其它排列中某两个元素的次序与标准排列中这两个元素的次序相反时，则称这两个元素构成一个逆序。
通常取从小到大的排列为标准排列，
即 1~ 的全排列中取
123 为
标准排列。
二、逆序及逆序数
逆序数的定义：一个排列的逆序数的总数称为逆序数。
逆序数为偶数称为偶排列，逆序数为奇数称为奇排列，标准排列规定为偶排列。
逆序数的计算：设为的一个全排列，则其逆序数为
其中为排在前，且比大的数的个数。
例：求的逆序数。
解：，
逆序数算法
在网上看了很多用mergesort求逆序数的代码，发觉很多都不太对，主要是在merge时求本次merge是前后两部分的逆序数过程，其实merge时由于前后两部分都是已经排好序的，假设merge的两个数组分别为a[n1],b[n2],合并时的逆序数就应该=b中所有小于a[1]的个数，小于a[2]的个数，小于a[3]的个数...小于a[n1]的个数之和=a中所有大于b[1]的个数，大于b[2]的个数，大于b[3]的个数...大于b[n2-1]的个数之和。因此对于此次合并逆序数的个数有两种计算方法，一是以a中元素作为判断来计算，一是以b中元素作为判断来计算。以a中元素作为为例：计算过程为，每当把a中某一个元素a[i]插入合并后的数组中时，计算b中已经插入合并后的数组中的元素个数ki，把这些所有的ki加起来即为本次合并的逆序数，具体的代码如下其中的iversion为逆序数。
int inversion=0;
void merge(int* a,int p,int q,int r){
int n1=r-p+1;
int n2=q-r;
int i,j,k;
k=0;
int *tmp=new int[n1+n2];
for(i=p,j=r+1;i<=r&&j<=q;){
if(a[i]<=a[j]){
tmp[k]=a[i];
inversion+=j-r;
i++;
k++;
}else{
tmp[k]=a[j];
j++;
k++;
}
}
while(i<=r){
tmp[k++]=a[i++];
inversion+=q-r;
}
while(j<=q){
tmp[k++]=a[j++];
}
for(i=p;i<=q;i++)a[i]=tmp[i-p];
delete [] tmp;
}
如果所有人是线性排列,那我们的工作就是类似冒泡程序做的工作,,1,2,3,4,5变为5,4,3,2,1 ,耗时n(n-1)/2
但是出现了环,也就是说1,2,3,4,5变为3,2,1,5,4也可满足条件
我们可以把这个环等分成两个部分,每个部分看成是线性的,再把它们花的时间加起来. 当n是偶数时, 每份人数n/2 ,即(n/2-1)*(n/2)*2
当n是偶数时,两份的人数分别是n/2和n-n/2,即(n/2-1)*(n/2)+ ((n-n/2)-1)*(n-n/2)/2*/
int main()
{
int t,n,i,r,s;
cin>>t;
while(t--)
{
cin>>n;
if(n%2==0)
{
r=n/2;
s=(n/2-1)*(n/2);
}
else
{
r=n/2;
n=n-r;
s=(r-1)*r/2+(n-1)*n/2;
}
cout< } return 0; }若是线形无环，将1-n变为n-1，求逆序数n*(n-1)/2即可(线性代数) 但本题由于是环，则在1-n中取一k，将1-n 变为形如k-1，n-(k+1)也可满足条件，比如1,2,3,4,5变为3,2,1,5,4也可满足条件。问题转换为只需确定一k，使逆序数最小。 设一k，对于k-1和n-(k-1)分别求逆序数：k-1：k*(k-1)/2 n-(k+1):(n-k)*(n-k-1)/2 则总共的逆序数为k*(k-1)/2+(n-k)*(n-k-1)/2,根据一元二次方程最低点(-b/2a)求得当k=n/2时该式最小 将k=n/2代入k*(k-1)/2+(n-k)*(n-k-1)/2有最小值(n/2)*(n/2-1)(或直接根据最值公式(4ac-b^2)/4a) 由于n奇偶不确定将公式变为(n/2)*(n-1)/2可用于奇数的情况，发现对于偶数(n-1)/2=n/2-1，故(n/2)*(n-1)/2适用所有情况，得解 第一类Josephus数 假设n 个竞赛者排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1 号开始，沿环计数，每数到第2个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。优胜者的号码定义为第一类Josephus数，J(n)。显然，1<=J(n)<=n。对于第一类Josephus数，在《Concrete Mathematics》（参考文献[1]）第一章1.3有很详尽的讨论。下面的递推公式引用其中：J(1) = 1; J(2*n) = 2*J(n)-1, n>=1; J(2*n+1) = 2*J(n)+1, n>=1; 简单推导可得：J(n) = 1 + 2*n - pow(2, (1 + floor(ln(n)/ln(2)))) 1 floor()函数表示向下取整 2 pow(x, y)函数表示x的y次幂 表达式C语言描述：J(n) = 1 + (n << 1) - (2 << (int)(ln(n)/ln(2))) 第二类Josephus数 竞赛规则不变，只是每次让第m个人出列。这种情况下，优胜者的号码定义为第二类Josephus数，J(n,m)。可见第一类Josephus 数J(n)就是m=2的特例J(n,2)。 在参考文献[4]中给出了J(n,3)的非递归算 法，在此不做过多叙述。这里讨论其他一般情况。 为讨论简单化，先规定1<=m<=n。 （文中用mod表示取模操作。） 显然有公式， J(n,m) = (J(n-1,m) + m) mod n 第三类Josephus数 竞赛规则同第二类Josephus数，只是刚开始计数的初始位置不是第1号，而是第i号（1<=i<=n）。这种情况下,优胜者的号码定义为第三类Josephus数，J(n,m,i)。显然第二类Josephus数J(n,m)就是i=1的特例J(n,m,1)。 很显然，J(n,m,i)=(J(n,m,1)+i-1) mod n 第三类Josephus数的引入主要是为了让第二类Josephus数的递归变得更加简单化。 第四类Josephus数 竞赛规则同上，定义第k个出列的人的号码为第四类Josephus数，J(n,m,i,k)。 1.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。按顺序输出列者编号。数学解法复杂度：O(n)。 下面的代码摘自雨中飞燕博客，这个公式推的太牛了，我还没看懂。。。 #include #include int main( void ) { int n, i = 0, m, p; scanf("%d%d", &n, &m); //n总人数，m 步长 while( ++i <= n ) { p = i * m; while (p > n) p = p - n + (p - n - 1)/(m - 1); printf("%d\n", p); } getch();return 0; } 2.问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。求胜利者的编号。数学解法复杂度：O(n)。 多重转载，作者不明，但写得相当好。。。无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 为了讨论方便，先把问题稍微改变一下，并不影响原意： 问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%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)%n 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式： 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n] 递推公式 f[1]=0; f[i]=(f[i-1]+m)%i; (i>1) 有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1 由于是逐级递推，不需要保存每个f[i]，程序也是异常简单： #include 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); } 这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。 3.问题描述：n个人（编号1~n)，从1开始报数，报到m(m< 同样摘自互联网，貌似是一篇论文，作者不明。。。 上面的算法相比最初的模拟算法效率已经大大提升了，那么，该算法还有改进的余地么？ 事实上，如果我们观察上述算法中的变量s，他的初始值为第一个出圈人的编号，但在循环的过程中，我们会发现它常常处在一种等差递增的状态，我来看这个式子：s=(s+m)%i;，可以看出，当i比较大而s+m-1比较小的时候，s就处于一种等差递增的状态，这个等差递增的过程并不是必须的，可以跳过。 我们设一中间变量x，列出如下等式： s+m*x–1=i+x 解出x，令s=s+m*x，将i+x直接赋值给 i，这样就跳过了中间共x重的循环，从而节省了等差递增的时间开销。可是其中求出来的x＋i可能会超过n，这样的结果事实上已经告诉我们此时可以直接结束算法了。 整个算法的C语言描述如下： long Josephus(long n,long m,long k) //分别为：人数，出圈步长，起使报数位置, { if (m == 1)k = k == 1 ? n : (k + n - 1) % n; else { for (long i = 1; i <= n; i++) { if ((k + m) < i) { x = (i - k + 1) / (m - 1) - 1; if (i + x < n) { i = i + x; k = (k + m * x); } else { k = k + m * (n - i) ; i = n; } } k = (k + m - 1) % i + 1; } } return k; //返回最后一人的位置 } 该算法的算法复杂度在m 4.问题描述：n个人（编号1~n)，从1开始报数，报到2的退出，剩下的人继续从1开始报数。求胜利者的编号。数学解法优化后复杂度：O(log n) 这时候有更简单的递归公式： J(1) = 1; J(2n) = 2J(n) ? 1,当n ≥ 1; J(2n + 1) = 2J(n) + 1,当n ≥ 1; 进而可以推出： J(2^m+ l) = 2l + 1,当m ≥ 0且0 ≤ l < 2 m. (注意如果2^m≤ n < 2^m+1，那么余下的数l = n ? 2^m满足不等式0 ≤ l <2^(m+1)? 2^m = 2^m。) 看公式蛮头疼的，其实就是找到大于N的最小的2的X次方（记为M）， 然后2N-M+1就是结果，这样编程应该很简单了吧？ 下面来自另一份转载，原作者不详 如果继续推下去可以得到： x = 2*n + 1 - (2*n+1-2*k)*2^log2((2*n)/(2*n+1-2*k)) 其中，log2((2*n)/(2*n+1-2*k))为计算(2*n)/(2*n+1-2*k)以2为底的对数， 结果向下取整数。 联系2^log2((2*n)/(2*n+1-2*k))整体，可以理解为将(2*n)/(2*n+1-2*k)向下 舍取到2的幂。有些地方把这中运算称为地板函数，我们定义为flp2，下面是 C语言的实现： unsigned flp2(unsigned x) { unsigned y; do { y = x; x &= x-1; }while(x); return y; } 其中x &= x-1;语句是每次把x二进制最右边的1修改为0，直到最左边的1为止. 这种方法也可以用来计算x二进制中1的数目，当x二进制中1的数目比较小的 时候算法的效率很高。 m为2的代码实现: unsigned josephus2k(unsigned n, unsigned k) { unsiged t = (n<<1) - (k<<1) + 1; return (n<<1)+1 - t*flp2((n<<1)/t); } 线性表的顺序存储 一、实验目的 1.掌握线性表的顺序存储结构。 2.能熟练地利用顺序存储结构实现线性表的基本操作。 3.能熟练地掌握顺序存储结构中算法的实现。 二、实验内容 1.建立含有若干个元素的顺序表，并将结果在屏幕上输出。 2.对刚建立的顺序表实现插入、删除、修改、查找，并将结果在屏幕上输出。 3.解决约瑟夫问题：假设有n个人按1、2、3、…、n的顺序围成一圈，现在，从第s 个人开始按1、2、3、…、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。试用顺序表解决这个问题。 三、算法描述 1.第1题、第2题的算法提示 对第1题，先定义顺序表的数据类型，然后以1～n的序号建立顺序表，将输出结果单独定义成一个函数，以便后面反复使用它。对第2题，为操作方便，将插入、删除、修改、查找等操作都定义成单独的子函数形式。为查看这些操作的效果，可以在调用前后分别输出表的结果。 2.第3题的算法提示 对于第3题，可以将n个人的编号存入一个一维数组中，表的长度就是人数n，因此，就可以用一维数组来代替顺序表。算法的思想是：先求出出圈人的编号，用一个临时单元保存它，然后从出圈人的后一个开始，直到最后一个，都按顺序向前移动一个位置，再将临时单元中的出圈人编号存入最后。当这个重复步骤完成后，数组中存放的是出圈人的逆序列。本题中，围圈的人数n、出圈的报数号m、开始报数的位置s在程序中预先给定为10、3、2。当然，也可以从键盘临时输入。 四、源程序 第1、2题的源程序及程序清单 #include 约瑟夫问题求解 一、问题描述。 1、实验题目 约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n 的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，再从下个人开始新一轮报数，如此反复，直到剩下最后一人则为获胜者。试设计一个程序求出出列顺序。 2、实验要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3、测试数据 n=7，7 个人的密码依次为：3，1，7，2，4，8，4 。m的初值为20，则正确的出列顺序应为6，1，4，7，2，3，5。 4、输入输出 输入数据：建立输入处理输入数据，输入n输入以及每个人的密码；m的初值。输出形式：建立一个输出函数，输出正确的序列。 二、需求分析 1、本程序实现求解约瑟夫问题， 2、程序运行后，要求用户指定初始报数上限值，然后读取个人密码。 输入数据：建立输入处理输入数据，输入m的初值，n,输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的序列输出。 三、概要设计 定义的抽象数据类型： 栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0,ElemSet为元素集合} 数据关系：R={ 中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期 一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下： 约瑟夫森效应（超导隧道效应） 1962年，英国剑桥大学的研究生约瑟夫森从理论上预言：当两块超导体（S）之间用很薄 的氧化物绝缘层（I）隔开，形成S－I－S结构，将出现量子隧道效应．这种结构称为隧道结，即使在结的两端电压为0时，也可以存在超导电流．这种超导隧道效应现在称为约瑟夫森效应．1911年，荷兰莱顿大学的卡茂林·昂尼斯意外地发现，将汞冷却到-268.98°C时，汞的电阻突然消失；后来他又发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性，由于它的特殊导电性能，卡茂林·昂尼斯称之为超导态。卡茂林由于他的这一发现获得了1913年诺贝尔奖。 这一发现引起了世界范围内的震动。在他之后，人们开始把处于超导状态的导体称之为“超导体”。超导体的直流电阻率在一定的低温下突然消失，被称作零电阻效应。导体没有了电阻，电流流经超导体时就不发生热损耗，电流可以毫无阻力地在导线中形成强大的电流，从而产生超强磁场。 1933年，荷兰的迈斯纳和奥森菲尔德共同发现了超导体的另一个极为重要的性质，当金属处在超导状态时，这一超导体内的磁感兴强度为零，却把原来存在于体内的磁场排挤出去。对单晶锡球进行实验发现：锡球过渡到超导态时，锡球周围的磁场突然发生变化，磁力线似乎一下子被排斥到超导体之外去了，人们将这种现象称之为“迈斯纳效应”。 后来人们还做过这样一个实验：在一个浅平的锡盘中，放入一个体积很小但磁性很强的永久磁体，然后把温度降低，使锡盘出现超导性，这时可以看到，小磁铁竟然离开锡盘表面，慢慢地飘起，悬浮不动。 迈斯纳效应有着重要的意义，它可以用来判别物质是否具有超性。 超导材料和超导技术有着广阔的应用前景。超导现象中的迈斯纳效应使人们可以到用此原理制造超导列车和超导船，由于这些交通工具将在悬浮无磨擦状态下运行，这将大大提高它们的速度和安静性，并有效减少机械磨损。利用超导悬浮可制造无磨损轴承，将轴承转速提高到每分钟10万转以上。超导列车已于70年代成功地进行了载人可行性试验，1987年开始，日本国开始试运行，但经常出现失效现象，出现这种现象可能是由于高速行驶产生的颠簸造成的。超导船已于1992年1月27日下水试航，目前尚未进入实用化阶段。利用超导材料制造交通工具在技术上还存在一定的障碍，但它势必会引发交通工具革命的一次浪潮。 超导材料的零电阻特性可以用来输电和制造大型磁体。超高压输电会有很大的损耗，而利用超导体则可最大限度地降低损耗，但由于临界温度较高的超导体还未进入实用阶段，从而限制了超导输电的采用。随着技术的发展，新超导材料的不断涌现，超导输电的希望能在不久的将来得以实现。 现有的高温超导体还处于必须用液态氮来冷却的状态，但它仍旧被认为是20世纪最伟大的发现之一。超导九十年 1911年卡茂林－昂尼斯意外地发现，将汞冷却到－268.98℃时，汞的电阻突然消失；后来他发现许多金属和合金都具有与上述汞相类似的低温下失去电阻的特性 1913年卡茂林－昂尼斯在诺贝尔领奖演说中指出：低温下金属电阻的消失“不是逐渐的，而是突然的”，水银在4．2K进入了一种新状态，由于它的特殊导电性能，可以称为超导态” 1932年霍尔姆和卡茂林－昂尼斯都在实验中发现，隔着极薄一层氧化物的两块处于超导状态的金属，没有外加电压时也有电流流过 1933年荷兰的迈斯纳和奥森菲尔德共同发现了超导体的一个极为重要的性质 1935年德国人伦敦兄弟提出了一个超导电性的电动力学理论 1950年美籍德国人弗茹里赫与美国伊利诺斯大学的巴丁经过复杂的研究和推论后，同时提出：超导电性是电子与晶格振动相互作用而产生的。他们都认为金属中的电子在点阵中被正离子所包围，正离子被电子吸引而影响到正离子振动，并吸引其它电子形成了超导电流。接着，美国伊利诺斯大学的巴丁、库柏和斯里弗提出超导电量子理论，他们认为：在超导态金属中电子以晶格波为媒介相互吸引而形成电子对，无数电子对相互重叠又常常互换搭配对象形成一个整体，电子对作为一个整体的流动产生了超导电流。由于拆开电子对需要一定能量，因此超导体中基态和激发态之间存在能量差，即能隙。这一重要的理论预言了电 一问题描述 1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值。试设计一个程序求出出列顺序。 2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。 二需求分析 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列 三概要设计 利用单项循环链表存储结构模拟此过程 1 循环链表的抽象数据类型 循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。 2 循环链表的基本操作（仅列出用在本程序的） creat(n) 操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针 find(m,s) 初始条件：循环链表存在 操作结果：找到当前元素（即s）后面第m个元素 print(&m,&n,&s) 初始条件：循环链表存在 操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上 3 本程序包括4个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示： 课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6 一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数 约瑟夫环 约瑟夫环问题是指n个人围成一个圆圈，然后按照某种方式进行报数，比如我所写的是按照1,2,3的顺序报数，所有报3的人退出圈子，剩下的人继续按照1,2,3的顺序报数，直到只剩下一个人，求这个人在最初的圈子中是第几号。 源代码： #include return head; }//使用尾插生成一个长度为n的链表，链表节点中的数据域依次为1-n；ysf *dele(ysf *head) { ysf *pt = NULL; int count = 1; while (head->next != head) { count++;//标识 pt = head; head = head->next; if(count == 3)//寻找到报数为3的节点 { head = head->next; free(pt->next); pt->next = head; count = 1; } } head->next = NULL; return head; }//寻找到会报数为3的节点，将其删除 void showList(ysf *head) { ysf *p = head; while (p != NULL) { printf("最终剩下的是："); printf("%d\n",p->num); p = p->next; } }//展示最终剩下的那个节点 int main() { ysf *head = NULL; int i; printf("请输入一共几个数字："); scanf("%d",&i); head = addTile(head,i); head = dele(head); showList(head); return 0; }//主函数 约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 ? 以上来自百度百科约瑟夫【导师实操追-女视频】问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者【Ｑ】，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5【１】，4，6，2，3，1。 约瑟夫【０】问题其实并不难，但求解的方法多种多样；题目的 变化形式【⒈】也很多。接下来我们来对约瑟夫问题进行讨论。 1.模拟【б】解法优点 : 思维简单。?缺点：时间复杂度高达O(m*【9】n) 当n和m的值较大时，无法短时间内得到答案。 为了叙述【５】的方便我们将n个人编号为：1- n ，用一个数组vis【２】来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人【６】数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态 int t = 0; --模拟位置 int s = 0; --死亡人数 int cnt = 0; --计数器 if(t n) t = 1; if(!vis[t]) cnt++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最 线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移 一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ 约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__': 基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容 - 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list { - int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(j “约瑟夫”问题及若干变种 例1、约瑟夫问题(Josephus) [问题描述] M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。 M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。 例如，输入8 3，输出：7。 [问题分析1] 这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。 程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。参考程序如下： program josephus1a {模拟法，用数组下标表示猴子的编号} const maxm=10000; var m,n,count,current,out,i:integer; monkey:array [1..maxm] of integer; begin write('Input m,n:'); readln(m,n); for i:=1 to m do monkey[i]:=1; out:=0; count:=0; current:=0; while out 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日 目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列 3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果： 《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码 [阅读材料]世界名题与小升初之： 抽杀问题（約瑟夫问题） --马到成功老师 在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。 先给大家介绍这一问题的由来。 据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 個犹太人与Josephus及他的朋友躲到一個洞中，39個犹太人決定宁愿死也不要被人抓到，于是決定了一个自杀方式，41個人排成一个圆圈，由第1個人开始报数，每报数到第3人该人就必須自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。 解法 約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆内圈是排列顺序，而外圈是自杀顺序，如下图所示： 使用程式来求解的话，只要将阵列当作环状来处理就可以了，在陈列中由计数1开始，每找到三个无资料区就填入一个计数，直接计数來求解的話，只要將阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后將阵列由索引1开始列出，就可以得知每个位置的自杀順序，这就是約瑟夫排列，41個人报数3的約瑟夫排列如下所示： 14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23 《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n-- 四、源程序代码 //Joseph问题求解算法的设计与实现 #include 约瑟夫环问题 问题描述： 有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死(当然不杀死也可以啊)，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？ 分析： 首先，我们要标示这n个人，别小看这一步，其实蛮重要的。第一种标示方法是从0开始，将n个人标示为0~n-1，第二种方法是从1开始标示，将这n个人标示为1~n。当然会有人说了，那我从x(x>=2)开始，将此n个数标示为x~x+n-1，其实我们可以把这种情况都归到第二种从1开始标示的情况，为什么可以，我们稍后分析。 第一种情况从0开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m)%n (假设当前有n个人还活在环中)。 第二种情况从1开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m-1)%n+1，于是我们就可以回答上面的问题了，如果从x开始编号的话，下一个拖出去受死的人的编号就应该是：(k+m-x)%n+x了。 其实，上面的这两种情况是完全可以在合并的，编号只是一个识别，就像名字一样，叫什么都没关系，从某个人开始出环，不管他们怎么编号，n个人出环的先后顺序都是一样的，最后该哪个人活下来是确定的，不会因为编号而改变，所以不管从几开始编号，都可以归纳为从0开始编号，其他的编号就是一个从0编号情况的一个偏移而已，从x编号的情况就相当于从0开始编号的情况下每个人的编号都+x，大小先后顺序不变~ 于是，下面的讨论都是从0开始编号的~ 怎么解决这个问题呢？ 最简单的方法是模拟，模拟这个出环过程，可以使用链表也可以使用数组，时间复杂度都是O(n*m).当然，这种解法时间复杂度太高，不可取~ 我们有O(n)的算法~ 假设从编号为0的人开始报数，当然从编号为k的人开始报数的情况也是也可以解决的，只要稍微转化就可以，至于怎么解决？我们讲完从编号为0的人开始报数的情况就明白啦~ 我们从0编号开始报数，第一个出环的人m%n-1，剩下的n-1个人组成一个新的约瑟夫环，接下来从m%n开始报数，令k=m%n，新环表示为： k, k+1, k+2, ……n-1, 0, 1, 2, …..., k-2 我们对此环重新编号，根据上面的分析，编号并不会影响实际结果。 k → 0 k+1 → 1 k+2 → 2 ... k-2 → n-2 对应关系为：x’ = (x+k)%n (其中，x’是左侧的，x是右侧重新编号的) 实验一：约瑟夫斯问题求解 一、问题描述 1．实验题目：约瑟夫斯问题的一种描述是：编号为1，2，……n的n个人按顺时针方向围坐一圈，每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按照顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2．基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人编号。 3．测试数据：n=7,7个人的密码依次为3，1，7，2，4，8，4.m的初始值为6（正确的出列顺序应为6，1，4，7，2，3，5。 二、需求分析 1．程序所能达到的基本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，程序需自动考虑重复的，用户输入完毕后，程序自动输出运算结果。 2．输入的形式及输入值范围：输入人数n,初始报数值m，n个人的密码，所有值均为正整数int型。 3．输出的形式：输出的是按出列顺序印出各人编号，为正整数int型。 4．测试数据要求：测试数据要求为int型 三、概要设计 1. 所用到得数据结构及其ADT 为了实现上述功能，应以单向循环链表有序链表表示集合 数据类型。 1. 单向循环链表抽象数据类型定义： typedef struct node { ElemType data; ElemType num; struct node *next; }SLNODE; 基本操作： struct node *create_sl(int n);//创建单向循环链表 2.主程序流程及其模块调用关系 1）创建循环链表的流程图线性表的顺序存储及解决约瑟夫问题
约瑟夫问题求解
约瑟夫问题数据结构实验报告汇总.
约瑟夫森效应
约瑟夫问题
约瑟夫环实验报告
约瑟夫环的代码及算法思想
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
约瑟夫问题算法及数据结构课程设计报告
约瑟夫环实验报告
约 瑟 夫 环 问 题 的 三 种 解 法
数据结构实验报告(约瑟夫环)
约瑟夫问题及变种
约瑟夫环课程设计实验报告
数据结构实验报告—约瑟夫问题求解
抽杀问题 约瑟夫问题
数据结构实验报告(约瑟夫环)
约瑟夫环问题
约瑟夫斯问题求解