约瑟夫环实验报告

约瑟夫环实验 篇一:数据结构实验报告一-约瑟夫环问 实验1约瑟夫环问题 1( 需求分析 (1) 输入的形式和输入值的范围: 每一次输入的值为两个正整数，中间用逗号隔开。 若分别设为n,m，则输入格式为:“n,m”。 不对非法输入做处理，即假设输入都是合法的。 (2) 输出的形式: 输出格式1:在字符界面上输出这n个数的输出序列 输出格式2:将这n个数的输出序列写入到文件中 (3) 程序所能达到的功能: 对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。 (4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。 正确: 1 输入:10,3 输出:3 6 9 2 7 1 8 5 10 4 输入:41,3 输出:3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31 错误: 输入:10 3 输出:6 8 7 1 3 4 2 9 5 10 2( 概要设计 (1)抽象数据类型的定义: 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表ADT定义如下: ADT list 数据对象:整形 数据关系:线性关系，即<ai,ai+1>(0?a,n)。 基本操作: bool remove(int elem)//移除一个元素，被移除的元素赋给elem //如果操作成功，返回true,否则返回false bool isEmpty()//判断数组的元素是否清空，空返回true,否则返回false bool setPos(int place)//设置当前元素的位置，设置成功返 2 回true,否则返回false int getLength()//获取数组的实际长度 (2)算法的基本思想: 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。 核心算法主要分为两步: 1、确定需要删除的位置，2、设置并删除该位置。 已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正(即模拟环状计数)。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 (3)主程序的流程: 程序由三个模块组成: (1)输入模块:无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。 (2)处理模块:将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该 3 位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。 (3)输出模块:分别在DOS下和文件中，按移除元素的顺序依次显示其位置。 (4)各程序模块之间的层次(调用)关系: 主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序。 3( 详细设计 (1) 实现概要设计中定义的所有数据类型(物理数据结构): 1、用整形存储用户输入的整数。 2、用顺序表实现线性表: class AList { private: int *listArray;//指向数组的指针 int realSize;//数组中含有元素的实际长度 int fence;//指向当前元素下标 public: AList(int s)//构造函数，初始化数组 4 { listArray=new int[s]; for(int i=0;i<s;i++) listArray[i]=i+1;//数组值等于数组下标+1 realSize=s; fence=0;//指向首元素 } bool remove(int elem)//移除一个元素 { if(isEmpty())return false;//如果数组为空返回false elem = listArray[fence]; for(int i=fence;i<realSize-1;i++)//从当前位置开始循环向前赋值 { listArray[i]=listArray[i+1]; } realSize--; return true; } bool isEmpty()//判断数组的元素是否清空 { if(realSize==0)return true; 5 else return false; } bool setPos(int place)//设置当前元素的位置 { if(place>=0place<=realSize) { fence=place; return true; } return false; } int getLength()//获取数组长度 { return realSize; } }; (2) 算法的具体步骤: 在主函数中调用上述模块的方法: ofstream fout;//文件流 fout.open("C:\\Josephus.txt");//设置文件路径 int n,m,elem,point=0; scanf("%d,%d",n,m);//获得用户输入 6 AList alist(n);//创建顺序表对象 while(!alist.isEmpty())//如果顺序表不为空，继续删除 { m=m%alist.getLength();//调整计数的长度 if(m==0)m=alist.getLength(); if(point+m-1<alist.getLength()){point=point+m-1;} // 设置偏移位置 else{point=point+m-alist.getLength()-1;} alist.setPos(point);//设置当前需要删除的位置 alist.remove(elem);//删除元素 cout<<elem<<";//DOS输出 fout<<elem<<";//文件输出 } (3) 算法的时空分析和改进设想: 1、初始化部分为循环赋值，时间复杂度为Θ(n)。 2、处理部分，我为了提高效率没有采用循环寻找的方法，直接利用关系通过当前位置获得下一位置，因此对于长度为n的约瑟夫环，只做了n次定位，每次定位的复杂度为Θ(1)，所以时间复杂度为Θ(n)。 但是用顺序表实现时，每次其移除的方法是时间复杂度为Θ(k)的(k与实际长度有关)， (1?n)n所以处理部分总的结果是()的，化简后时间复杂度 7 仍然为Θ(n2)。 2 综上，该算法的时间代价为Θ(n2)。 (PS:如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是Θ(n*m)，然后再用顺序表的移除方法，总的复杂度应该是Θ(m*n2)的。) 事实上要用线性表来完成这道题，其复杂度最好也是Θ(n2)的，毕竟对于n个数据，每个都要进行时间复杂度为Θ(n)的删除工作。欲到达Θ(n)的效率除非不用线性表来实现。 (4) 画出函数的调用关系图: 主程序 (5) 输入和输出的格式: 输入:10,3 输出:3 6 9 2 7 1 8 5 10 4 (文本中的输出):3 6 9 2 7 1 8 5 10 4 4、测试结果 篇二:约瑟夫环C++代码及实验报告 实验一约瑟夫环问题实验报告 通信二班 雷鹤20100820207 20100820208 李春阳 李孟琪 20100820209 一、问题描述 8 设编号为1-n的n(n>0)个人按顺时针方向围成一圈(首先第1个人从1开始顺时针报数(报m的人(m 为正整数)(令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。 二、需求分析 1、需要基于线性表的基本操作来实现约瑟夫问题 2、需要利用数组来实现线性表 3、测试用例 输入:10，3 输出:3 6 9 2 7 1 8 5 10 4 三、概要设计 抽象数据类型 为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。 算法的基本思想 利用数组来代表一个环，然后模拟报号出圈的过程，直到所有人都出圈。 程序的流程 程序由三个模块组成: (1) 输入模块:完成两个正整数的输入，存入变量n和m中。 (2) 计算模块:计算这n个数的输出序列 (3) 输出模块:屏幕上显示这n个数的输出序列。 9 四、详细设计 程序代码: #include <iostream> using namespace std; main() { int n,m,k,j; //n为总人数，m为出列编号 cin>>n>>m; int *listArray=new int[n]; //将n个人放在大小为n的数组中 int *outArray=new int[n]; //用以存放依此出列的人的编号 for(int i=0;i<n;i++) listArray[i]=i+1; //对n个人进行编号 for(i=1,j=k=0;k<n;j=++j%n) //i为报数编号，初始值为1，循环访问数组元素，即数组元素循环报数 { if(listArray[j]!=0) { if(i==m) //报数编号和出列编号相同时 { outArray[k]=listArray[j];//将该元素放置到出列数组里，并输出 cout<<outArray[k]<<"; 10 k++; listArray[j]=0; //将出列元素置0 i=1; //下一个元素从1开始重新报数 } else i++; //报数编号与出列编号不同时，继续报数 } } cout<<'\n'; return 0; } 物理数据类型 队列元素及出列序列都以整型数组方式存储 算法的具体步骤 (1) 将队列里的元素编号 (2) 循环访问数组元素 (3) 第一个元素从1开始报数，报数编号与出列编号相 同时出列，并 将该元素置为0 (4) 下一个元素重新从1开始报数，依次循环 输入和输出的格式 输入格式:n，m 11 输出格式1:在字符界面上输出这n个数的输出序列 输出格式2:将这n个数的输出序列写入到文件中 五、测试结果 其他程序代码 程序1 #include<stdio.h> #include <stdlib.h> typedef int type; //结点数据域类型为整型 typedef struct LNode //结点类型定义 { struct LNode *next;//结点的指针域 type a; //结点的数据域 }link; void initLink(link* l) { l=(link*)malloc(sizeof(link));//在内存的动态存储区申请链表长度的连续空间 //初始化链表 l->next=l; } void insert(link* l) //在其后插入新成员 { 12 link* p; p=(link*)malloc(sizeof(link)); p->next=l->next; l->next=p; } void destory(link* l) //删除其后面的元素 { link* t; t=l->next; l->next=l->next->next; free(t); } int main() { int m,n; char p; while(scanf("%d%c%d",n,p,m)!=EOF) { link* head; link* temp; initLink(head); temp=head; 13 for(int i=0 ; i<n ; i++) { insert(temp); temp->next->a=i+1; //创建链表 temp=temp->next; } temp->next=NULL; temp=head; while(head->next!=NULL) { for(int i=1;i<m;i++)//模拟约瑟夫过程 { { if(temp->next==NULL) temp=head; } temp=temp->next; } if(temp->next==NULL) { printf("%d ",head->next->a); destory(head); } 14 else { printf("%d ",temp->next->a); destory(temp); } } printf("\n"); } } 程序2 #include<iostream> using namespace std; void main() { int n,m,a[100001],k,i,j; cin>>n; if(n>100000) 篇三:实验报告1约瑟夫环 《数据结构》实验报告 班级: 学号:姓名:日期: 08-10-20 题目:约瑟夫环 15 一、 上机实验的问题和要求: 问题描述: 编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列～要求得到依次出列的那些人的编号序列～ 基本要求: 用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果～ 二、程序设计的基本思想，原理和算法描述: (包括程序的模块结构，数据结构，输入/输出设计，符号名说明等) 基本思想: 利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。 程序的模块结构: 定义了相关的结构体之后，主要有以下几大模块: 1. 建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n); 2. 寻找、输出、删除H单循环链表的第m个结点locfor(H,m); 16 3. 最后通过main函数体处理参数的输入与显示，并调用以上两函数，最终解决问题。 主要数据结构: 单链的循环链表，即线性表的链式存储结构。 算法的伪码描述: 结构体定义如下: typedef struct Lnode /*定义单链表*/ { int number; /*编号*/ int cipher; /*密码*/ struct Lnode *next;/*指针*/ }Lnode,*CLinklist; /*重定向命名*/ CLinklist H; /*,为全局单链表*/ 算法的实现详见源程序。 输入/输出设计 本程序并未采用任何二进制文件出入的方式，这点说明将在最后提到。至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。 三、源程序及注释: (说明函数功能、入口及出口参数,其他) #include <stdio.h> /* 头文件*/ #include <stdlib.h> 17 #include <alloc.h> typedef struct Lnode /*定义单链表*/ { int number; /*编号*/ int cipher; /*密码*/ struct Lnode *next;/*指针*/ }Lnode,*CLinklist; /*重定向命名*/ CLinklist H; /*,为全局单链表*/ struct Lnode *crt_CLinkList(CLinklist H,int m) /*创建一个不带头结点的单向循环链表*/ { /*其中，,为全局单链表，m为链表结点总数*/ int i; /*循环记数用*/ struct Lnode *ptr1; /*用于索引*/ if((ptr1=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) /*一旦动态内存分配失败，报错退出～*/ { perror("malloc"); return ptr1; } H=ptr1; /*形成单个结点的单循环链表*/ ptr1->next=H; for(i=1;i<m;i++) /*形成m个结点的不带头结点的单循 18 环链表*/ { if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) { perror("malloc"); ptr1->next=H; return H; } ptr1=ptr1->next; /*其中,指头，ptr指尾*/ ptr1->next=H; } return H; /*返回成功新建的单链表,*/ } void locfor(CLinklist H,int m) /*寻找输出删除链表,中的第m个结点*/ {/*H为全局链表，m为要查找删除的结点位置*/ int i; /*循环计数*/ struct Lnode *ptr; for(i=1;i<=5;i++) /*考虑图形界面的美观问题*/ printf("number\tcipher\t"); i=1; /*初始化*/ while(H->next!=H) /*只剩单个结点时停止循环，进行 19 最后输出～*/ { if(m==1)/*考虑进行自身删除的情况，即m=1*/ { for(ptr=H->next;ptr->next!=H;ptr=ptr-> next);/*正因为是自身删除才要费大劲寻找其父结点*/ printf("%-6d\t",H->number); /*找到后，先输出*/ printf("%-6d\t",H->cipher); m=H->cipher; /*确定下一次寻找的m值*/ ptr->next=H->next; *删除结点，即自身结点*/ ptr=ptr->next; free(H); /*因为对于链表中的结点，每个之前都分配了内存，所以free是必要的*/ H=ptr; /*不同于以下普通结点的删除，自身删除还要还原H*/ i=1; /*i重置，以方便下一次的循环操作*/ } else if(i==m-1)/*因为从自身开始即为1号，因为m-1,而不是m*/{ ptr=H->next; /*结点的删除操作同于上面的情况!*/ printf("%-6d\t",ptr->number); printf("%-6d\t",ptr->cipher); m=ptr->cipher; 20 H->next=ptr->next; H=H->next; free(ptr); i=1; } else { H=H->next;/*若未找到，则继续遍历～*/ i++; } } printf("%-6d\t",H->number);/*对于单个结点的单循环链表，进行最终的输出操作～*/ printf("%-6d",H->cipher); free(H); /*完成所有任务并释放所有内存占用～*/ } void main()/*主函数接口*/ { /*调用所有函数，进行实验模拟，并得出实验结果～*/ int i,j,n=30,m,k; struct Lnode *ptr; randomize(); /*因为下面调用了random函数，故此处的初始化很有必要～*/ printf("Now the experiment will 21 begin.You have two choices!\n"); /*数据输入可以电脑随机，也可以自行输入*/ printf("If you want to enter the datas all by yourself,please enter 1.\n");/*自行输入(方便程序 问题)*/ printf("If you want to get the datas by the computer,please enter 0.\n"); /*电脑随机产生数据*/ printf("Now your choice:");/*用户选择*/ scanf("%d",j); while(j!=0j!=1)/*考虑程序的完善性，对于误输入的提示并 报警～*/ { printf("\nYou enter is unillage!Please try again!\n"); printf("Now your choice:"); /*重新输入*/ scanf("%d",j); } H=crt_CLinkList(H,n); /*初始化链表*/ if(j==0) /*电脑随机充入数据*/ for(i=1;i<=30;i++) { H->number=i; H->cipher=rand(); /*随机函数*/ H=H->next; 22 } else /*此时选择实验者输入数据～*/ { for(i=1;i<=30;i++) { H->number=i; printf("Now number %d,please enter the cipher:",i); scanf("%d",k); H->cipher=k; H=H->next; } } m=rand(); /*默认情况下，m随机产生*/ printf("Do you want to enter the number m?Enter 1 to set or others cancel!\n"); /*当然，如果想自已输，可以进行覆盖*/ scanf("%d",k); if(k==1) /*自行输入m值*/ { printf("Please enter the number m:"); scanf("%d",m); 23 } system("cls"); /*考虑屏幕大小，进行分屏显 示*/ printf("All followed are your datas!\n"); /* 界面友善*/ for(i=1;i<=5;i++) printf("number\tcipher\t"); for(i=0;i<30;i++) /*显示所有处理前数据*/ { printf("%-6d\t",H->number); printf("%-6d\t",H->cipher); H=H->next; } printf("And the number m is :%d\n",m); printf("\nAfter the program,the result is:\n"); locfor(H,m);/*对所有数据进行实验处理，直至所有结点处 理完～*/ getchar(); printf("\nPress any key return!"); /*TC环境 下，方便查看结果～*/ getchar(); } 四、用户使用说明与测试运行结果: 24 1 (运行程序后，首先弹出界面，截图如右: 理性化的选择:如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试～如果打0，那么所有的数据均由电脑产生～那如果打其他的呢, 考虑到误输入，加了一个循环，以提高程序的健壮性～ 2(首先自行输入数据进行测试。 输完后的对话框: 25