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

2011年    12    月    30    日 目录 摘  要    3 1    课题背景的介绍    3 1.1 课题背景    3 1.2 目的    3 2    需求分析    4 2.1 数据需求分析    4 2.2 功能需求分析    4 3    系统总体    5 3.1 系统模块划分    5 3.2 系统模块结构图    5 4    系统详细设计    6 4.1 系统操作界面    6 4.2 各模块功能实现    6 4.2.1顺序存储    6 4.2.2单循环链表    8 4.2.3 数组    9 4.2.4 循环队列    10 4.2.5 递归    11 4.2.6 主函数    12 5    总结    15 6    参考文献    16 7    附录    16 7.1人员分工    16 7.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 #include #include const int max=100; int array[max],num,Templete;//Templete保存递归算法的返回值 //以下数组操作都是从下标0开始，真正的数据编号是从1开始 #pragma region ["用顺序表实现"] typedef struct CirCleNode { int data[max]; int last;//顺序表的大小 }*CNode; CNode CreateCirCleNode(int n)//往顺序表中读入数据 { CNode cn; cn=new CirCleNode; int i; for(i=0;idata[i]=i+1; } cn->last=n; return cn;    } int PushCirCleNode(CNode cn,int m)//顺序表出队 { int count=0,i=0,num=0,j=0,Temp[max]; while(countlast) { while(numlast) { i=i%cn->last+1;//约瑟夫环的每轮起始位置 if(cn->data[i-1])//非0的时候让计数器自加 { num++; } } count++; Temp[j++]=cn->data[i-1]; cn->data[i-1]=0;//出队的时候置为0 num=0;//计数器清零 } /* for(j=0;jlast;j++) { printf("--%d",Temp[j]); }*/ return Temp[cn->last-1]; } #pragma endregion ["顺序表执行"] 4.2.2单循环链表 (1)算法思想 创建不带头结点的单循环链表，创建完链表之后返回链表的第一个结点指针。从第一个结点开始按照以m为间隔，找到要出队的结点的前驱结点和后继结点，将前驱结点的下一个结点指针指向其后继结点，同时删除该结点，以此循环下去直到该循环链表只剩下最后一个结点为止。 (2)代码实现 #pragma region ["单循环链表实现"] typedef struct node { int 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;inext;