下载文档原格式
约瑟夫环的知识点总结约瑟夫环这个问题不仅在古代受到了广泛的关注，而且在现代数学中也有着重要的地位。
它涉及到了排列、递推、循环和递归等多个数学概念，并且有着一些有趣的数学特性。
因此，学习约瑟夫环不仅能够增加我们对于数学问题的理解，而且也可以提高我们的数学思维能力。
接下来，我们将从几个方面对约瑟夫环进行深入的讨论。
1. 约瑟夫环的历史约瑟夫环最早出现在约瑟夫斯的《犹太古记》中，他描述了犹太人在与罗马军队的战斗中围攻马萨达城的情景。
根据《犹太古记》的记载，当罗马军队攻陷了马萨达城后，大约960名男子决定宁死不从。
于是，他们站成一个圈，每隔两个人就有一个杀掉，直到最后只剩下一个人。
而这个幸存者恰恰就是约瑟夫斯本人。
因此，这个问题就得名为约瑟夫环。
除了这个故事之外，约瑟夫环在古代数学文献中也有着多次的提及。
例如，中国古代数学家秦九韶在其著作《数书九章》中也提到了这个问题。
他利用递推的方法解出了约瑟夫环的一般解，并推广到了更一般的情况。
自古代以来，约瑟夫环一直受到数学家们的关注，他们提出了很多不同的方法来解决这个问题。
而到了现代，约瑟夫环在计算机科学和密码学中也有着广泛的应用。
因此，约瑟夫环问题可以说是一个古老而又具有重要意义的数学问题。
2. 约瑟夫环的一般解在数学中，我们可以用递推的方法对约瑟夫环进行求解。
假设有N个人站成一圈，编号从0到N-1，而每隔M个人就有一个人出列。
那么一个简单直接的方法就是用递归来求解。
具体来说，我们可以定义一个递归函数f(n, m)，表示N个人中最后存活下来的那个人的编号。
那么这个函数的递归关系可以如下定义：f(n, m) = (f(n-1, m) + m) % n其中f(1, m) = 0，表示只有一个人时的情况。
通过递归的方法，我们可以得到约瑟夫环的一般解。
而根据这个递归关系，我们还可以得到一些有趣的数学性质。
例如，我们可以求解约瑟夫环在给定N和M的情况下的解，而不需要实际模拟整个过程。
约瑟夫环实验小结：智能1201 陈明201208070103一、问题描述：约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。
改进约瑟夫问题的描述是：编号为1，2，…，n 的n个人按顺时针方向围坐一圈,每人有一个密码Ki（整数），留作其出圈后应报到Ki后出圈。
报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。
求最后剩下的人的编号。
这个就是约瑟夫环问题的实际场景二、问题分析：用数组可以解决问题。
每次数到要出列时，就先出列，然后再从数组中删除相应元素，每次数到数组末尾时就重新回到数组第一个元素，重复此步骤，直至到达最后一个元素。
三、代码1）C++代码：/*约瑟夫环问题描述：设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。
然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。
如此下去，直到圈中所有人出列为止。
求出列编号序列。
*/#include<iostream>using namespace std;int main(){while(true){//多次循环实验cout<<"#########***********************多次实验分隔符********************#########"<<endl;//分隔符int n;//数组的大小int m;//m为数到第几个就出列的数cout<<"请输入要数组的初始大小n值,以及数到第m个就出列的m的值,n、m需为任意正整数:"<<endl;;//m可以大于ncin>>n>>m;cout<<"原始数组："<<endl;int *p=new int[n];for(int i=0;i<n;i++){p[i]=i+1;} //初始化数组元素for(i=0;i<n;i++){cout<<p[i]<<",";}cout<<"\n出队顺序："<<endl;int count_Num=1;//计数变量for(int j=1;j<=n;j++){//n的值随出列的元素的变化而变化//cout<<"count_Num="<<count_Num<<",j="<<j<<",n="<<n<<endl;if(n==1){cout<<p[0];break;}else if(m==count_Num){//如果数到就出列// cout<<"!!!!!!!!!!!!!@@@@"<<endl;count_Num=0;if(j==n){j=1;}//判断数到末尾，恢复到开始cout<<"\n"<<p[j-1]<<"->";//“除去”数到第j个元素p[j-1]，“复制”数组int *q=new int[n-1];for(int t=0;t<j-1;t++){q[t]=p[t];}//跳过数组元素p[j];for(t=j;t<=n-1;t++){q[t-1]=p[t];}//将q的地址赋给p；p=q;cout<<endl;for(int i=0;i<n-1;i++){cout<<p[i]<<",";}// count_Num=1;//count_Num再从1开始计数n=n-1;//由于元素总数减少1，故n要减少1//****************j=j-1;//此句没有写，导致输出一直不是需要的结果，经过查找，加上后，就变好了！//***************}if(j==n){j=0;}//判断数到末尾，恢复到开始count_Num++;//计数变量自加！}//释放内存空间！delete [] p;//delete [] q;cout<<"\n";}system("pause");return 0;}2）Java代码：/****/package 约瑟夫环问题;/*** @author 陈明win7**/public class YSFH {int Ini_length;//java类中有四种数据，此处为default类型int SrcA []=new int[20];//定义数组/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println("约瑟夫环问题：");YSFH ys=new YSFH();ys.Ini_length=20;System.out.print("原始数组：");for(int i=1;i<=ys.SrcA.length;i++){ys.SrcA[i-1]=i;System.out.print(ys.SrcA[i-1]+",");}/*ys.remove(3);ys.remove(5);ys.remove(8);for(int i=0;i<ys.SrcA.length;i++){System.out.print(ys.SrcA[i]+",");}*///约瑟夫问题****************int Count_Num=22;//数到就要删除的号码System.out.println("\n数到22就删除！"+"出场顺序：");int j=1;for(int i=0;i<=ys.SrcA.length;i++,j++){//System.out.println("当前数组长度是："+ys.SrcA.length+",,"+"i值是："+i+"，j值是："+j);if(ys.SrcA.length==1){System.out.println(ys.SrcA[0]);}else{if(j==22){if(i==ys.SrcA.length){i=0;}//System.out.println("将删除："+ys.SrcA[i]+",");System.out.print(ys.SrcA[i]+"-》");//if(i==ys.SrcA.length){i=0;System.out.println("###########");}ys.remove(i+1);//ys.Arrayout();j=1;}//System.out.println("@@@@@@@@"+"当前数组长度是："+ys.SrcA.length+",,"+"i值是："+i+",j值是："+j);if(i==ys.SrcA.length){i=0;}}}System.out.println();}/* //移除元素的方法public void remove(int index) {// TODO Auto-generated method stubif(SrcA.length==0||index<0){System.out.println("错误！队列无元素可以删除！");}else if(SrcA.length==1){SrcA=null;}else if(index<=SrcA.length){int[] dest=new int[SrcA.length-1];//复制元素,注意复制的长度出错的可能性大System.arraycopy(SrcA, 0, dest,0 , index-1);//System.out.println("@@@@@@@"+SrcA.length+"##########"+index);System.arraycopy(SrcA, index, dest,index-1 , SrcA.length-index);SrcA=dest;}}//输出当前数组所以元素public void Arrayout(){System.out.print("当前数组为：");for(int i=0;i<SrcA.length;i++){System.out.print(SrcA[i]+",");}System.out.print("\n");}}四、运行结果截图C++结果截图：当需要输出当前结果时：当不需要输出当前结果时：Java结果截图：五、实验小结1）最容易出现的问题就是数组越界，然后多数情况就是使用输出当前所有数组来调试、解决问题2）两个程序均没有参考其他代码，以前的情况多数就是先看看别人的思路、代码，然后再去自己编写程序，但是这次全部独立完成。
约瑟夫问题的经典三个例子以下是 9 条关于约瑟夫问题的经典例子：例子 1：想想看，一群小朋友围成一圈玩游戏，就像我们小时候那样。
这时候说从某个小朋友开始报数，每隔一个人淘汰，最后剩下的那个就是胜利者。
这不就是约瑟夫问题嘛。
就好像在一个神秘的游戏圈子里，大家都紧张又兴奋地等待着命运的裁决。
例子 2：你能想象军队里士兵们站成一圈，然后用这种方式来决定谁去执行特殊任务吗？哎呀呀，那场面肯定很刺激。
每个士兵心里都七上八下的，不知道自己是不是那个“幸运儿”，这和约瑟夫问题如出一辙。
例子 3：假如在一场盛大的聚会中，大家玩这样的游戏，是不是超级有趣？就像一个魔法圈，把大家的注意力都吸引过来了。
每淘汰一个人，大家就会一阵惊呼，这不正是约瑟夫问题带来的独特体验嘛。
例子 4：你看过那种生存挑战节目吗？选手们围成一圈，然后通过类似约瑟夫问题的规则来淘汰人。
哇塞，那紧张的氛围，可不就是在经历一场残酷的竞争，这就是约瑟夫问题在现实中的精彩呈现呀！例子5：好比一群探险家在荒岛上，为了分配重要资源而采取这种方式。
每个人都祈祷自己不要被先淘汰掉，这种感觉是不是很奇妙？这就是约瑟夫问题带来的不确定性啊。
例子6：想象一下公司团建的时候玩这个，大家既期待又担心。
“哎呀，可别先轮到我呀！”“哇，我居然留下来了。
”这种种反应，不就是约瑟夫问题的魅力所在吗？例子 7：学校运动会上，各班学生围成一圈进行比赛，多刺激呀！有人欢喜有人忧，这不就是约瑟夫问题所引发的情绪波澜吗？例子 8：在一个神秘的魔法学院里，学生们也用这种方式来选拔优秀学员。
每一个人都全神贯注，这和约瑟夫问题一样充满了悬念呢！例子9：如果在一个古老的部落中，用约瑟夫问题来决定首领的继承人，那该是多么惊心动魄的场面啊。
大家的心都提到了嗓子眼，。
约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。
求最后剩下的人的编号。
【说明】1）建议用循环链表存储方式，设计循环链表类和约瑟夫类。
2）问题改进：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。
若每人有一个密码Ki（整数），留作其出圈后的报到Ki后出圈。
密码Ki可用随机数产生。
这样事前无法确定谁是最后一人。
#include<stdio.h>#include<stdlib.h>typedef struct Joseph{int num;int key;struct Joseph *next;} Joseph1;Joseph1 *CreatList(int n){Joseph1 *R,*p,*q;int i,k;R=p=(Joseph1*)malloc(sizeof(Joseph1));p->next=NULL;for(i=0;i<n-1;i++){q=(Joseph1*)malloc(sizeof(Joseph1));p->num=i+1;scanf("%d",&k);if(k<=0){printf("输入信息有误!");exit(0);}p->key=k;p->next=q;p=q;}q->num=n;scanf("%d",&k);if(k<=0){printf("输入信息有误!");exit(0);}q->key=k;q->next=R;R=q;return(R);}void DeleList(int n,Joseph1 *P,int m){Joseph1 *q,*t;q=P;int i,j;for(i=1;i<n;i++){for(j=1;j<m;j++)q=q->next;t=q->next;q->next=t->next;m=t->key;printf("删除的第%d个数是:",i);printf("%d\n",t->num);free(t);}printf("删除的最后一个数是:%d\n",q->num);free(q);}void main(){int m,n;Joseph1 *P;printf("请输入参加的人数: ");scanf("%d",&n);if(n<=0){printf("输入信息有误!");exit(0);}printf("请输入初始密码: ");scanf("%d",&m);if(m<=0){printf("输入信息有误!");exit(0);}printf("请输入每个人的密码: ");P=CreatList(n);DeleList(n,P,m);}。
约瑟夫环问题⼩结⼀问题描述约瑟夫环问题的基本描述如下：已知n个⼈(以编号1，2，3...n分别表⽰)围坐在⼀张圆桌周围。
从编号为1的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，要求找到最后⼀个出列的⼈或者模拟这个过程。
⼆问题解法在解决这个问题之前，⾸先我们对⼈物进⾏虚拟编号，即相当于从0开始把⼈物重新进⾏编号，即⽤0,1,2,3,...n-1来表⽰⼈物的编号，最后返回的编号结果加上1，就是原问题的解(为什么这么做呢，下⽂有解释)。
⽽关于该问题的解通常有两种⽅法：1.利⽤循环链表或者数组来模拟整个过程。
具体来讲，整个过程很明显就可以看成是⼀个循环链表删除节点的问题。
当然，我们也可以⽤数组来代替循环链表来模拟整个计数以及出列的过程。
此处只给出利⽤数组来模拟这个过程的解法，最终结果为最后⼀个出列的⼈的编号：#include<iostream>#include<unordered_map>#include<queue>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<sstream>#include<set>#include<map>using namespace std;int main(){int n,m;cin>>n>>m;vector<int>rs(n);for(int i = 0 ; i < n; i++)rs[i] = i + 1;//对⼈物重新进⾏编号，从0开始int cur_index = 0;//当前圆桌状态下的出列⼈的编号int out_cnt = 0;//⽤以表⽰出列的⼈数int cnt = n;//表⽰当前圆桌的总⼈数while(out_cnt < n - 1)//当out_cnt等于n-1时，循环结束，此时圆桌师⽣最后⼀个⼈，即我们要的结果{if(cur_index + m > cnt){if((cur_index + m) % cnt == 0)//这种情况需要单独考虑，否则cur_index就变成负值了cur_index = cnt - 1;elsecur_index = (cur_index + m) % cnt - 1;}elsecur_index = cur_index + m - 1;cnt--;out_cnt++;cout<<"当前出列的为："<<*(rs.begin() + cur_index)<<endl;rs.erase(rs.begin() + cur_index);//从数组中删去需要出队的⼈员}cout<<"最后⼀个出列的⼈物为："<<rs[0]<<endl;}该⽅法的时间复杂度为O(nm)，空间复杂度为O(n)，整个算法的基本流程还是⽐较清晰的，相当于每次循环更新cur_cnt、cnt和out_cnt这三个变量，当out_cnt == n-1时，此时出队的⼈数⼀共有n-1⼈，圆桌上只剩下⼀个⼈了，停⽌循环。
实验一：约瑟夫问题求解一、问题描述1、实验题目：约瑟夫（Josephus）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。
2、基本要求：试设计一个程序，按出列顺序印出个人编号。
3、测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。
ｍ的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。
二、需求分析１、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。
2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。
3、用户输入完毕后，程序自动输出运算结果。
三、概要设计1、设计思路n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。
游戏规则：①给定一个初始密码②循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。
2、数据结构为了实现上述功能，可以采用链式存储结构。
采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定义函数，分别用于创建链表和约瑟夫出列操作。
①链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE{数据对象：D={ i a |i a ∈SLNODE, i=1,2,3.... }数据关系：R=φ}ADT SLNODE;②自定义函数:void create_SLnode(SLNODE *p,int n)//创建队列{ 创建链表，为N 个人分配密码 }void Josef(SLNODE *p,int n)//进行约瑟夫操作{输入初始密码m;for(){ 将出列的结点删除，并输出出列序号；}}③本程序的保护模块：结构体模块主程序模块自定义函数模块调用关系：3、程序设计主要算法的流程图：create_SLnode( )算法流程图Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针#define SLNODE struct slnodeSLNODE//每个结点的结构体{int num;//num代表序号int code;//code代表密码SLNODE *next;};2、自定义函数：void create_SLnode(SLNODE *p,int n)//创建队列，并将其尾指针指向第一个序号{SLNODE *r,*s;s=p;int i,m;cout<<"请给这"<<n<<"个人分配密码："<<endl;for(i=0;i<n;i++){cout<<"请给第"<<i+1<<"个人输入密码："<<endl;cin>>m;r=(SLNODE *)malloc(sizeof(SLNODE));r->code=m;r->num=i+1;r->next=s->next;s->next=r;s=s->next;}p=p->next;s->next=p;}void Josef(SLNODE *p,int n)//进行约瑟夫操作{p=p->next;int m;int i,j;SLNODE *r;cout<<"请输入初始密码："<<endl;cin>>m;cout<<"依次出列的序号为:"<<endl;for(i=0;i<n-1;i++)p=p->next;for(i=0;i<n-2;i++){for(j=0;j<m-1;j++)p=p->next;cout<<(p->next)->num<<endl;m=(p->next)->code;r=p->next;p->next=r->next;}if(m%2==0)cout<<p->num<<endl<<(p->next)->num<<endl;elsecout<<(p->next)->num<<endl<<p->num<<endl;}3、主函数：int main(){SLNODE *p;int n;cout<<"请输入一圈的人数："<<endl;cin>>n;p=(SLNODE *)malloc(sizeof(SLNODE));p->next=NULL;create_SLnode(p,n);Josef(p,n);return 0;}4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。
Josephus（约瑟夫）问题有n个人围成一个圈，从第1个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到剩下一个人，问此人编号为几？或：有n个人围成一个圈，从第k个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有人出列，由此产生一个出队编号的序列。
1、数组解法#include<iostream>#include<stdlib.h>using namespace std;const int n=11, m=3;int main(){int a[n],p=0;int i,k=0,number=0;for(i=0; i<n; i++) a[i]=i+1;while(number<n-1) //number表示出去的人数{ if(a[p]!=0) //p指向正要报数的人{ k++; //k为1,2,3...报数if(k==m) //报到m时，a[p]出去{ a[p]=0; k=0; number++; }}p=(p+1) % n; //下一个人}for(i=0; i<n; i++)if(a[i]!=0){ cout<<"最后一个获胜者的编号是："<<i+1<<endl; break; }system("pause");}其中while循环也可改为：while(number<n-1) //number表示出去的人数{while(a[p]==0) p=(p+1) % n; //找到下一个报数的人k++; //k为1,2,3...报数if(k==m) //报到m时，a[p]出去{ a[p]=0; k=0; number++; }p=(p+1) % n;}2、链表解法#include<iostream>#include<stdlib.h>using namespace std;const int n=11, m=3;struct node{ int no;node *next;};int main(){int k=0;node *p,*q,*r;p=q=new node; //创建第一个节点p->no=1;for(int i=2; i<=n; i++) //建立链表{ r=new node;r->no=i;q->next=r;q=r;}q->next=p; //构成一个"环"q=p;while(q->next!=q){ k++; //k为1,2,3...报数if(k==m) //报到m时，删除q所指结点{ p->next=q->next;delete q;q=p->next;k=0;}else{ p=q; q=q->next; }}cout<<"最后一个获胜者的编号是："<<q->no<<endl; system("pause");}其中while循环也可改为：while(q->next!=q){ for(int i=1; i<m; i++) //直接找到报m的人{ p=q; q=q->next; }p->next=q->next;delete q;q=p->next;}。
约瑟夫问题一、问题描述和要求1、问题描述约瑟夫问题是这样的：设有n个人围圆桌坐成一圈，现从第s个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此重复下去，直到所有人都出列为止。
2、程序设计要求（1）、通过本学期《数据结构》的学习，综合运用已学过的理论和技能去分析和解决约瑟夫问题，加深对数据结构课程理论的理解和运用、切实加强自己的实践动手能力和创新能力。
（2）、结合C语言程序设计、数据结构中所学的理论知识，小组独立设计方案，培养分析与解决问题的能力。
（3）、学会查阅相关手册和资料，进一步熟悉常用算法的用途和技巧，掌握这些算法的具体含义。
（4）、认真调试程序，学会改正程序中的错误，尝试不同的方法实现同一功能，培养严谨的作风和科学的态度。
二、个人所负责的工作1、算法思路约瑟夫问题的解决可以用线性链表，循环链表，数组等多种方法，我们采用线性链表解决该问题，采用分块的设计思路，利用函数调用解决问题。
本算法采用for循环解决线性链表的建立，用printf函数输出链表，利用for循环找到第s个人开始报数，再利用一个for循环找到第m个人，然后多重if语句讨论不同情况的处理，最后通过函数调用解决约瑟夫问题。
2、我负责的工作在这次程序设计中，我主要负责对整个题目设计思路进行分析和对程序的注释。
我们刚设计出来的程序存在着种种问题，各部分程序都需要进行一定的修改和完善，比如线性链表不能够正常输入，主函数对用户的输入要求的描述太过笼统，输出函数不能调用等等。
我就是不断发现这些问题并完善它们，使程序能够正确的运行。
然后我和其他组员经过商议，对程序的各部分含义进行注释。
在程序演示时我主要负责对整个题目设计思路分析及组员介绍。
以下是我修改过的程序之一:NODE *creatlinklist(int n)/*建立线性链表*/{ int i;NODE *head,*p,*q;/*定义整形实参i，指针head、p、q*/if(n==0)return(NULL);/*如果n=0建立一个空链表*/elsehead=(NODE *)malloc(sizeof *head);/*申请一个结点为表头*/q=head;for (i=1;i<=n;i++)/*将n个结点输入到单链表中*/{p=(NODE *)malloc(sizeof *head);printf("输入数据:");p->info=getche();/*getche功能: 输入后立即从控制台取字符，不以回车为结束*/printf("\n");q->next=p;/*q指向表尾，准备导入下一个结点*/q=p;}p->next=NULL;/*将最后一个结点的链域置为空*/return(head);}三、结论经过这次程序设计任务，我认真的复习了数据结构中学习过的理论知识，尤其是对线性链表这一部分进行了认真的归纳总结，对数据结构的认识更深刻了，对线性链表的建立、插入、删除、查找等操作的运用更加熟练，对for循环、输入输出函数等更加了解，而且我意识到今后我可以利用这些函数解决更多的实际问题。
实验一：约瑟夫斯问题实验报告一、问题描述1）问题描述约瑟夫斯（Josephus)问题的一种描述是：编号为1,2,…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数.报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。
试设计一个程序，按出列顺序印出各人编号。
2）基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号.3）测试数据m的初值为20；n=7,7个人的密码依次为：3,1，7，2，4，8，4。
m初值为6（正确的出列顺序应为6，1，4，7，2,3，5）.二、需求分析1．该程序所能实现的功能：将n个数字按照某一特定序列输出，直至全部输出为止。
2．输入的形式及输入值范围：依次输入人数n、每个人的密码及报数上限m值。
3．输出的形式：按照报数上限m及每个人的密码依次输出每个人的编号。
4．测试数据要求：m的初值为20；n=7，7个人的密码依次为：3,1,7,2,4，8,4。
m初值为6（正确的出列顺序应为6，1，4，7，2,3，5）。
三、概要设计1.主程序流程获取每个人的密码，选定m的初值,调用函数,按照特定要求完成输出操作。
2.核心模块的算法伪码主程序：void main（void)｛int m；people *s；s=GetData（）;cout〈<"请输入m的初值："<〈endl；cin〉〉m；DealData（s,m）；｝预编译代码：#include〈iostream。
h〉四、详细设计1。
实现每个操作的伪码，重点语句加注释(1)建立“人”的结构体struct people｛int data;int num；people *next;};(2）获取每个人的相关数据people ＊GetData（）{i nt n；p eople *p1,＊p2，*head；h ead=NULL;c out<<”请输入人数：”;c in〉〉n;c out〈〈”请依次输入每个人的密码：”<〈endl;f or(int i=0；i<n;i++）｛p1=new （people）;cin〉〉p1—>data；p1—>num=i+1；if(head==NULL)｛head=p2=p1; //建立首结点｝else｛p2-〉next=p1; //中间结点p2=p1；｝｝i f（head！=NULL)p2-〉next=head;r eturn（head)； //循环链表}2。
“约瑟夫”问题及若干变种例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;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。
这已经是优化过的程序，大家可以去看未做任何优化的程序josephus1b.pas，这个程序的时间复杂度为O(M*N*K)，K是一个不确定的系数，对应着程序中的repeat循环花费的时间。
空间复杂度为O（M）。
program josephus1b;{模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=1; current:=1;while out<m-1 dobeginwhile count<n dobeginrepeat{寻找圈上的下一只猴子}current:=current+1;if current=m+1 then current:=1until monkey[current]=1;count:=count+1end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[问题分析2]在组织数据时，也可以考虑只记录仍在圈中的猴子的情况。
用一个线性表按编号由小到大依次记录圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元素减少一个。
程序中用变量rest 表示圈中剩余的猴子数，即线性表中元素的总数。
参考程序如下：program josephus2a; {模拟法，用数组元素的值表示猴子的编号}const maxm=10000;var m,n,current,rest,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=i;rest:=m; current:=1;while rest>1 dobegincurrent:=(current + n - 1) mod rest;if current=0 then current:=rest;for i:=current to rest-1 do monkey[i]:=monkey[i+1];rest:=rest-1end;writeln('The monkey king is no.',monkey[1]);readlnend.[运行结果]下划线表示输入Input m，n:10000 1987The monkey king is no.8544 {时间：0.8秒}[反思] 时间复杂度为O（M*K），但K远远小于N，是for循环花费的时间，速度教快。
空间复杂度仍然为O（M）。
也可以用monkey[j]存放第j个猴子的后继编号。
当第j个出圈时，只要把monkey[j]的值赋给它的前驱，这样就自然跳过了j，以后再也不会访问到它了，但是时间上反而不如前面的方法。
程序如下：program josephus2b; {模拟法，用数组元素的值表示后继猴子的编号}const maxm=10000;var m,n,current,rest,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m-1 do monkey[i]:=i+1;monkey[m]:=1;current:=m;rest:=m;while rest>1 dobeginfor i:=1 to n-1 do current:=monkey[current];monkey[current]:=monkey[monkey[current]];end;writeln('The monkey king is no.',monkey[current]);readlnend.[问题分析3]本题用单向循环链表做，模拟的更形象。
时间复杂度为O（m*n），空间复杂度也是O（m），极限数据比方法2稍慢。
程序如下：program josephus3; {模拟法3，单向循环链表}TYPEpoint=^node;node=recorddata:longint;next:pointend;VAR m,n,s:longint; {s为计数器}p,q,head:point;BEGINreadln(m,n);new(head);q:=head;head^.data:=1;for s:=2 to m dobeginnew(p);p^.data:=s; {建一个结点，并且赋上数据域}q^.next:=p;q:=p; {把p接到q的后面，再把p作为新的q}end;q^.next:=head; {做成循环队列}s:=1;q:=head; {从队头开始报数，计数器也设为1}repeats:=s+1;if s mod n=0 then begin {报到了n}q^.next:=p^.next; {p出圈}dispose(p)endelse q:=p;until q^.next=q;writeln('The monkey king is no.',q^.data);readlnEND.[运行结果]下划线表示输入Input m，n:10000 9873The monkey king is no.8195[问题分析4]能不能不通过模拟而直接求出第k次出圈的猴子的编号呢？这就是递推法的思想。
用递推来求约瑟夫问题的方案，主要是找到m个猴子选大王过程与m-1个猴子选大王过程之间的关系。
假如m=5，n=3，有5个猴子：然后进行第一步选猴子，从第一个数起，3出圈，剩下4只猴子（图2，4被标上红色表示下一次从4数起）：接下来的选择过程与m=4，n=3（即四只猴子选大王，图3，从1数起）的情况非常相似。
图2中的4相当于图3中的1，图2中的5相当于图3中的2……。
以此类推，得到如下对应关系（左边一列是图2中的数字，右边一列是图3中的数字）：4←1 （注意：4-1=3 ,4=(1+3-1)mod 5 +1）5←2 ( 5=(2+3-1)mod 5 +1)1←3 ( 1=(3+3-1)mod 5 +1)2←4 ( 2=(4+3-1)mod 5 +1)仔细研究一下这些对应关系，便不难发现，从1数到4要数2、3、4三个数，从2数到5要数3、4、5三个数，从3数到1要数4、5、1三个数，从4数到2要数5、1、2三个数——都是三个数，而这个―三‖是由第一个对应关系确定的：delta=4-1=3。
现在假设我们知道m’=4，n=3的方案（a[i]）为3、2、4、1，那么按照上面介绍的对应关系, 我们就可以推出m=5，n=3的方案为b[i]=(a[i]+delta-1)mod m +1）,即：得到的新序列为1、5、2、4，再在这个序列前加上第一个出队的n(=3)号猴子，就得到3、1、5、2、4，而这就是m=5,n=3的出圈序列。
