敢死队问题(五种算法实现的约瑟夫环).doc

2011年12月30日 目录摘 要31课题背景的介绍31.1 课题背景31.2 目的32需求分析42.1 数据需求分析42.2 功能需求分析43系统总体设计53.1 系统模块划分53.2 系统模块结构图54系统详细设计64.1 系统操作界面64.2 各模块功能实现64.2.1顺序存储64.2.2单循环链表84.2.3 数组94.2.4 循环队列104.2.5 递归114.2.6 主函数125总结156参考文献167附录167.1人员分工167.2 代码16摘 要敢死队问题是根据著名的“约瑟夫环”演变而来的敢死队问题的处理与计算来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成敢死队问题的全过程，包括五种数据结构算法（顺序表、单循环链表、数组、循环队列、递归）、数据的处理与计算、数据的分析、结果的输出。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。关键词：敢死队问题，C语言，数据结构，顺序存储结构，单链表存储结构，数组，队列，递归1 课题背景的介绍1.1 课题背景有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。1.2 目的本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。经过这一个学期对数据结构的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。通过做这么个课程设计将理论联系实际，使我更好的理解课本上的知识，发现不足之处，然后更好的学习，使我的编程能力有进一步的提高。2 需求分析本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下 需要记数初始位置。2.1 数据需求分析由于约瑟夫环模拟的是人的报数操作，固本系统的主要处理的数据是正整数。正整数信息包括:队伍的人数，报数的数值，报数开始的位置。本程序任务是通过输入任意队伍人数n和报数上限m，输出使排长最后一个执行任务而开始记数的初始位置。首先输入队伍人数n，然后输入报数上限m(m<=n),从1号开始报数，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求(z=n-k+2)。2.2 功能需求分析本系统主要实现对学生成绩信息进行管理，需要实现以下几个方面的管理功能：（1）创建存储结构：创建顺序表，创建单循环链表，创建数组，创建循环队列。（2）数据的输入：把队伍的人数，报数的数值输入。（3）数据的处理；对队伍的人数，报数的数值进行计算。（4）结果的输出：把报数开始的位置输出。3 系统总体设计3.1 系统模块划分本系统主要是对敢死队问题的处理，包括了创建存储结构、数据的输入、数据的处理、结果的输出等功能。整个系统分为以下几个模块。1、操作界面模块 本模块提供操作界面的信息输出模式。2、顺序存储结构模块 本模块用于通过运用顺序结构模块来计算结果。3、单链表存储结构模块 本模块用于通过运用单链表结构模块来计算结果。4、数组模块 本模块用于通过运用数组结构模块来计算结果。5、循环队列模块 本模块用于通过运用循环队列模块来计算结果6、递归实现模块 本模块通过递归思想来实现计算结果3.2 系统模块结构图根据系统功能设计，对应的系统模块结构图如图所示敢死队问题功能模块顺序表存储循环队列递归单循环链表数组实现数据处理数据处理数据处理数据处理数据处理退出4 系统详细设计4.1 系统操作界面由于敢死队问题处理的是数字的调度问题，固不需要一些复杂的功能，因此根据实际需求设计了如下比较简洁的界面供用户使用。该界面简单明了，根据界面上的提示信息，用户能很快的使用该系统。4.2 各模块功能实现4.2.1顺序存储(1)算法思想将有n个人的队列存入顺序表中，然后从顺序表的第一个元素开始按间隔人数m读取数据，当报数报到m的时候出队，同时将该位置上的值置为0，以该位置的下一个(值为非0)位置为起始位置，以此循环报数直到剩下最后一个数为止，假设最后这个数为k。通过数学运算z=n-k+2，得到第一个报数的人的编号。注意：在报数的过程中如果出现位置上的值为0的情况，则跳过该位置，继续往下报数，直到有m个非0的数为止。(2)代码实现#include <stdio.h>#include <math.h>#include <stdlib.h>const int max=100;int arraymax,num,Templete;/Templete保存递归算法的返回值/以下数组操作都是从下标0开始，真正的数据编号是从1开始#pragma region "用顺序表实现"typedef struct CirCleNodeint datamax;int last;/顺序表的大小*CNode;CNode CreateCirCleNode(int n)/往顺序表中读入数据CNode cn;cn=new CirCleNode;int i;for(i=0;i<n;i+)cn->datai=i+1;cn->last=n;return cn;int PushCirCleNode(CNode cn,int m)/顺序表出队int count=0,i=0,num=0,j=0,Tempmax;while(count<cn->last)while(num<m && count<cn->last)i=i%cn->last+1;/约瑟夫环的每轮起始位置if(cn->datai-1)/非0的时候让计数器自加num+;count+;Tempj+=cn->datai-1;cn->datai-1=0;/出队的时候置为0num=0;/计数器清零 /*for(j=0;j<cn->last;j+)printf("-%d",Tempj);*/return Tempcn->last-1;#pragma endregion "顺序表执行"4.2.2单循环链表(1)算法思想创建不带头结点的单循环链表，创建完链表之后返回链表的第一个结点指针。从第一个结点开始按照以m为间隔，找到要出队的结点的前驱结点和后继结点，将前驱结点的下一个结点指针指向其后继结点，同时删除该结点，以此循环下去直到该循环链表只剩下最后一个结点为止。(2)代码实现#pragma region "单循环链表实现"typedef struct nodeint data;struct node *next;*Node;Node CreteNode(int n)/创建不带头结点单链表Node p,q,t;int i;t=p=new node;p->data=1;for(i=2;i<=n;i+)q=new node;/申请新的结点插入链表q->data=i;p->next=q;p=q;/printf("-%d",p->data); p->next=t;return t;int DeleteNode(Node nd,int m)/出队Node t;int i;while(nd->next!=nd)for(i=1;i<m-1;i+)/找到要删除结点的前一个结点nd=nd->next;t=nd->next;/printf("->%d",t->data);nd->next=t->next; delete t;nd=nd->next;/将结点指向被删除结点后一个结点return nd->data;#pragma endregion "单循环链表"4.2.3 数组(1)算法思想用数组实现敢死队问题的关键在于用数组的下标构造一个虚假循环，从第一节点开始，以人数m为间隔，找到要删除结点的下标k，将k以后的所有队员依次往前移动一个位置。以此循环下去直到数组中只剩下一个数为止。(2)代码实现#pragma region "数组实现敢死队问题"int Array(int n,int m)int i,temp,j;int k=0;/假设从第一个开始报数int Jspmax;for(i=0;i<n;i+)Jspi=i+1;for(i=n;i>=1;i-)k=(k+m-1)%i;/用数组的下标构造一个虚假循环 temp=Jspk;/temp保存要出队的值for(j=k;j<i;j+)/将k以后的数组往前移Jspj=Jspj+1;/printf("-%d",temp); return temp;#pragma endregion "数组列实现"4.2.4 循环队列(1)算法思想队列操作的最主要思想是先进先出，并且每次操作都是从队首删除，队尾进队。创建循环队列，从结点的第一个结点开始按照m人数间隔查找到要出队的结点，并且修改头结点的指针使其指向该结点，同时将该结点上的数据值修改为0。依次循环下去查找余下的非零结点，直到剩下一个非零结点为止。注意：1、队列的队首指的是队中第一个元素的前一个结点，因此在查找之前，先将头结点的指针指向第一个结点。2、在报数的过程中如果出现位置上的值为0的情况，则跳过该位置，继续往下报数，直到有m个非0的数为止。(2)代码实现/队列操作是先进先出，且每次删除队首，队尾进#pragma region "循环队列实现"typedef struct Sequeint datamax;int front;int rear; *SequeNode;/置空队void Iniqueue(SequeNode p)p->front=0;p->rear=0;int AddQueue(SequeNode p,int n)/入队if(p->rear+1)%n=p->front)return 0;elsefor(int i=1;i<=n;i+)p->rear=(p->rear+1)%n;p->datap->rear=i;/printf("-%d",p->datap->rear);return 1; int outQueue(SequeNode p,int n,int m)int temp=0,k=0,Tempmax;if(p->rear=(p->front+1)%n)return 0;elsep->front=(p->front+1)%n;for(int i=0;i<n;i+)while(temp<m)/找到被删除结点的后一结点p->front=(p->front+1)%n;if(p->front=0)/当头结点的下标是0时改变其下标p->front=n;if(p->datap->front-1!=0)/非零结点时让temp+temp+;Tempi=p->datap->front-1;p->datap->front-1=0;/把找到的那个结点置零/printf("-%d",Tempi);temp=0;return Tempn-1;#pragma endregion "循环队列"4.2.5 递归(1)算法思想参照数组实现。(2)代码实现#pragma region"递归实现敢死队问题"/Templete保存最后的返回值,results保存下标void CreateArray(int n)int i;for(i=0;i<n;i+)arrayi=i+1;int SearchArray(int n,int m)/思路参照数组int results;if(n>num)return 0;elseif(n=1)results=0;results=(SearchArray(n+1,m)+m-1)%n;Templete=arrayresults;for(int j=results;j<n;j+)arrayj=arrayj+1;return Templete,results;#pragma endregion"递归结束"4.2.6 主函数(1)核心算法运用数学思想求得敢死队的最初报数位置。假设总人数为n，报数间隔为m，最后一个出队人的标号为k，第一个出队人的下标为t，则t=n-k+2。(1)代码实现:int main()int push,flag;/num总人数,以push出队int result=0,temp=0;/result最后出队的人的编号SequeNode SNode=new Seque;printf("*敢死队问题*n");printf("*n");printf("请输入总人数:");scanf("%d",&num);printf("*n");printf("请输入间隔人数:");scanf("%d",&push);if(num<1 | push<1)printf("输入错误请重新输入:n");exit(1);if(num=1)printf("要使排长安全则应该从第%d号开始.n",num);exit(1);printf("*n");printf("根据菜单提示选择相应的算法n");printf("*n");printf("1、顺序表 2、链表 3、数组 4、队列 5、递归 6、退出n");while(scanf("%d",&flag)if(flag=6)break;switch(flag)case 1:CNode cnode;cnode=CreateCirCleNode(num); result=PushCirCleNode(cnode,push);break;case 2:Node LNode; LNode=CreteNode(num); result=DeleteNode(LNode,push);break;case 3:result=Array(num,push);break;case 4: Iniqueue(SNode);AddQueue(SNode,num);result=outQueue(SNode,num,push);break;case 5:CreateArray(num); SearchArray(1,push);result=Templete;break;default :result=0;printf("<<请根据菜单提示操作>>n");break;if(result!=0)temp=(num-result+2)%num;/运用数学思想求出第一个开始位置if(temp=0)printf("要使排长安全则应该从第%d号开始报数.n",num);elseprintf("要使排长安全则应该从第%d号开始报数.n", temp);printf("*n");return 0;(2)函数执行结果测试数据1：测试数据2：5 总结本课程设计敢死队问题处理系统，从开发到实现再到最后的测试结果来看，基本上实现了敢死队的五大算法功能模块：顺序存储、单循环链表、数组、循环队列、递归。并达到操作过程中的直观，方便，使用。系统采用模块化的程序设计，便于系统功能的组合和修改。另外通过本次的课程设计使我对数据结构与算法这门课程有了进一步的认识，通过系统中的发现的问题，再到解决问题这个阶段，让我体会到了编程的乐趣。经过这一个学期对数据结构与算法的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。通过做这么个课程设计将理论联系实际，使我更好的理解课本上的知识，发现不足之处，然后更好的学习，使我的编程能力有进一步的提高。6 参考文献c语言-谭浩强数据结构与算法-宁正元7. 代码#include <stdio.h>#include <math.h>#include <stdlib.h>const int max=100;int arraymax,num,Templete,push;/Templete保存递归算法的返回值/以下数组操作都是从下标0开始，真正的数据编号是从1开始#pragma region "用顺序表实现"typedef struct CirCleNodeint datamax;int last;/顺序表的大小*CNode;CNode CreateCirCleNode(int n)/往顺序表中读入数据CNode cn;cn=new CirCleNode;int i;for(i=0;i<n;i+)cn->datai=i+1;cn->last=n;return cn;int PushCirCleNode(CNode cn,int m)/顺序表出队int count=0,i=0,num=0,j=0,Tempmax;while(count<cn->last)while(num<m && count<cn->last)i=i%cn->last+1;/约瑟夫环的每轮起始位置if(cn->datai-1)/非0的时候让计数器自加num+;count+;Tempj+=cn->datai-1;cn->datai-1=0;/出队的时候置为0num=0;/计数器清零 /*for(j=0;j<cn->last;j+)printf("-%d",Tempj);*/return Tempcn->last-1;#pragma endregion "顺序表执行"#pragma region "单循环链表实现"typedef struct nodeint data;struct node *next;*Node;Node CreteNode(int n)/创建不带头结点单链表Node p,q,t;int i;t=p=new node;p->data=1;for(i=2;i<=n;i+)q=new node;/申请新的结点插入链表q->data=i;p->next=q;p=q;/printf("-%d",p->data); p->next=t;return t;int DeleteNode(Node nd,int m)/出队Node t;int i;while(nd->next!=nd)for(i=1;i<m-1;i+)/找到要删除结点的前一个结点nd=nd->next;t=nd->next;/printf("->%d",t->data);nd->next=t->next; delete t;nd=nd->next;/将结点指向被删除结点后一个结点return nd->data;#pragma endregion "单循环链表"#pragma region "数组实现敢死队问题"int Array(int n,int m)int i,temp,j;int k=0;/假设从第一个开始报数int Jspmax;for(i=0;i<n;i+)Jspi=i+1;for(i=n;i>=1;i-)k=(k+m-1)%i;/用数组的下标构造一个虚假循环 temp=Jspk;/temp保存要出队的值for(j=k;j<i;j+)/将k以后的数组往前移Jspj=Jspj+1;/printf("-%d",temp); return temp;#pragma endregion "数组列实现"/队列操作是先进先出，且每次删除队首，队尾进#pragma region "循环队列实现"typedef struct Sequeint datamax;int front;int rear; *SequeNode;/置空队void Iniqueue(SequeNode p)p->front=0;p->rear=0;int AddQueue(SequeNode p,int n)/入队if(p->rear+1)%n=p->front)return 0;elsefor(int i=1;i<=n;i+)p->rear=(p->rear+1)%n;p->datap->rear=i;/printf("-%d",p->datap->rear);return 1; int outQueue(SequeNode p,int n,int m)int temp=0,k=0,Tempmax;if(p->rear=(p->front+1)%n)return 0;elsep->front=(p->front+1)%n;for(int i=0;i<n;i+)while(temp<m)/找到被删除结点的后一结点p->front=(p->front+1)%n;if(p->front=0)/当头结点的下标是0时改变其下标p->front=n;if(p->datap->front-1!=0)/非零结点时让temp+temp+;Tempi=p->datap->front-1;p->datap->front-1=0;/把找到的那个结点置零/printf("-%d",Tempi);temp=0;return Tempn-1;#pragma endregion "循环队列"#pragma region"递归实现敢死队问题"/Templete保存最后的返回值,results保存下标void CreateArray(int n)int i;for(i=0;i<n;i+)arrayi=i+1;int SearchArray(int n,int m)/思路参照数组int results;if(n>num)return 0;elseif(n=1)results=0;results=(SearchArray(n+1,m)+m-1)%n;Templete=arrayresults;for(int j=results;j<n;j+)arrayj=arrayj+1;return Templete,results;#pragma endregion"递归结束"void function()printf("*n");printf("请输入总人数:");scanf("%d",&num);printf("*n");printf("请输入间隔人数:");scanf("%d",&push);if(num<1 | push<1)printf("输入错误请重新输入:n");exit(1);if(num=1)printf("要使排长安全则应该从第%d号开始.n",num);exit(1);printf("*n");int main()int flag;/num总人数,以push出队int result=0,temp=0;/result最后出队的人的编号SequeNode SNode=new Seque;printf("*敢死队问题*n");function();/*printf("*n");printf("请输入总人数:");scanf("%d",&num);printf("*n");printf("请输入间隔人数:");scanf("%d",&push);if(num<1 | push<1)printf("输入错误请重新输入:n");exit(1);if(num=1)printf("要使排长安全则应该从第%d号开始.n",num);exit(1);printf("*n");*/printf("根据菜单提示选择相应的算法n");printf("*n");printf("1、顺序表 2、链表 3、数组 4、队列 5、递归 6、退出n");while(scanf("%d",&flag)if(flag=6)break;switch(flag)case 1:CNode cnode;cnode=CreateCirCleNode(num); result=PushCirCleNode(cnode,push);break;case 2:Node LNode; LNode=CreteNode(num); result=DeleteNode(LNode,push);break;case 3:result=Array(num,push);break;case 4: Iniqueue(SNode);AddQueue(SNode,num);result=outQueue(SNode,num,push);break;case 5:CreateArray(num); SearchArray(1,push);result=Templete;break;default :result=0;printf("<<请根据菜单提示操作>>n");break;if(result!=0)temp=(num-result+2)%num;/运用数学思想求出第一个开始位置if(temp=0)printf("要使排长安全则应该从第%d号开始报数.n",num);elseprintf("要使排长安全则应该从第%d号开始报数.n", temp);/function();printf("*n");return 0;