HUNAN UNIVERSITY课程实习报告题目：约瑟夫问题学生姓名刘海龙学生学号************专业班级软件1 3 0 1 指导老师李晓鸿完成日期 2 0 1 4 年11 月18 日一、需求分析1.输入的形式和输入值的范围本程序中，输入的人数n和报数值m均为整数，n、m均大于0，输入的形式为：n，m （n、m输入时用逗号隔开）2.程序功能提供用户从键盘输入约瑟夫环的关键数据，人数n和报数值m，并显示出列顺序。
3.输出的形式在DOS界面上输出这n个数的输出序列。
4.测试数据①输入（n，m均为正整数，且n>m）10，3输出3 6 9 2 7 1 8 5 10 4②输入（n，m均为正整数，且n<m）4，6输出2 1 4 3③输入（n，m均为正整数，且n=m）7，7输出7 1 3 6 2 4 5④输入 (n,m中有浮点数)8，5.56输出输入有误，请重新输入！⑤输入（n,m中有负数）-3，-8输出输入有误，请重新输入！⑥输入（n,m未按格式输入）aA2，3asf输出输入有误，请重新输入！二、概要设计抽象数据类型n（n为正整数）个人的编号为1~n，1相当于唯一的“第一元素”，n相当于唯一的“最后元素”，除最后元素n外，剩下的n-1个编号均有唯一的后继，除第一元素1外，剩下的n-1个编号均有唯一的前驱，符合线性结构，故应以线性表实现该结构。
ADT alist{数据对象：D={a i| a i∈int，i=1，2，…，n，n≥0}.数据关系：Rl={<a i-1，a i> | a i-1，a i∈D，i=2，…，n}基本操作：InitList（&L，size）//构造一个空线性表L。
Append(&L，e) //新元素e入表Remove(&L，i) //删除表中第i个元素，即将i之后的元素往前移一位。
DesList（&L）//销毁线性表，释放内存空间}无论选择哪种数据结构都应有一个结构初始化操作及相应的结构销毁操作，本程序的结构初始化操作为：InitList（&L，size），结构销毁操作为DesList（&L）。
在将n个人的编号存进线性表时，需要一个添加操作，故设计Append(&L，e)，其用于向线性表表尾添加新元素e。
“出列”相当于删除线性表中某个指定的元素，这就需要一个删除操作，故设计Remove(&L，i)，其根据下标索引需要删除的元素，“删除”即相当于将该元素之后的所有元素向前移动一位。
算法的基本思想n个人的编号为1,2,3,…,n(n>0)，并且这n个人根据编号大小依序排列，即将这n个编号依序存入线性表中，报数值m为正整数。
①．编号为1的人从1开始依序报数，即从线性表的第一个元素起开始访问，并依序逐个访问它的下一个元素。
②．当轮到剩余人群中编号最大的人报数时，剩余人中编号最小的作为他的下一位，继续报数，即当线性表的表尾元素访问完后，将表头元素作为下一个访问对象。
③．数到m时报数停止，并且数到m的人出列，他的下一位从1开始重新报数。
即访问进行到第m次时停止，将第m次访问到的元素从表中删除，并在DOS界面上输出对应的编号，然后从它的下一个元素开始新一轮的访问（每轮m次）。
④．重复步骤2、3，直到出列n个人为止，即当表内元素均被删除为止，此时，整个出列序列已经输出在DOS界面上。
程序的流程程序由三个模块组成：（1）输入模块：完成人数和报数值的输入，存入变量n，m中。
（2）功能模块：设计一个实现约瑟夫问题的函数Joseph(&L,m），模拟循环报数，每出列一个元素，通过输出模块将其显示在屏幕上。
（3）输出模块：屏幕上显示出列的元素。
三、详细设计物理数据类型输入的人数n与报数值m均应为正整数，为了能够存储和处理，变量n，m采用C 语言中的int定义变量。
因为线性表是对n个人的编号1~n进行操作(编号1~n符合线性结构)，过程中无需添加新的元素，即表内元素最多只有n个，为了减小空间上的开销，线性表采用顺序表来实现其物理结构。
线性表的每个元素存储的是n个人的编号1~n中的一个，所以线性表中元素类型定义为整型。
#define DefaultListSize 100 //线性表默认长度为100typedef int Elem;typedef int ElemType;typedef struct List{Elem* listArray; //存储空间基址int length; //当前长度int maxsize; //最大长度}Alist;void InitList(Alist &L, int size=DefaultListSize) //构造一个空线性表L{L.maxsize = size; //若未传参，size取默认值100L.listArray = new Elem[L.maxsize];L.length = 0;}void DesList(Alist &L) //销毁线性表，释放内存空间{delete[] L.listArray;}bool Append(Alist &L, ElemType e) //新元素e入表{若L.length等于L.maxsize，返回false，表满，无法添加L.listArray[L.length] = e;L.length++; //由于有新的元素入表，故表的长度应该加1返回true，表示新元素e入表成功}bool Remove(Alist &L，int i) //删除表中第i个元素，即将i之后的元素往前移一位。
{若L.length等于0，返回false，表空，没有需要删除的元素int j;for(j=i;j<L.length;j++) //从第i+1个元素(下标为i)起，后面的所有元素向前移一位{L.listArray[j - 1] = L.listArray[j];}L.length--; //由于从表中删除了一个元素，故表的长度应该减1返回true，表示删除成功}算法的具体步骤约瑟夫问题的实现(函数joseph(&L,m))算法流程图：删除(基本操作Remove(&L，i))的算法流程图：1.根据n的值新建一个长度为n的线性表，将编号1~n依次存入表中。
2.设变量t=0、i=L.length.3.若i>=1（即线性表中至少还有一个未出列的元素），则t=（t+m-1）%i（即应出列元素的下标）。
4.输出下标为t的元素。
5.将出列元素之后的所有元素往前移一位，实现元素的“删除”；之后，i自减一次（从表中删除了一个元素）。
6.重复步骤3、4、5，直到表中无剩余元素。
算法的时空分析算法的执行，主要是n个编号的出列，以及每次出列一个编号时，将其之后的编号向前移动一位（以达到“删除”目的），每次出列一个编号的时间代价为常量，记为c1，出列之后，将其之后的编号均前移一位的时间代价与n的大小有关，记为c2n，则整个算法执行的时间代价为：（c1+c2n）*n=c1*n+c2n2，即：Θ（n2）。
若采用循环链表实现线性表，则删除的时间代价仅为常数级，相应的算法代价只要Θ（n）。
函数的调用关系图输入和输出的格式输入本程序用于解决约瑟夫环问题。
//提示请输入人数n和报数值m，用逗号隔开，如“10，3”：//提示等待输入输出出列序列为：//提示//输出结果的位置，每个编号之间间隔两个空格长度例如：输入本程序用于解决约瑟夫环问题。
请输入人数n和报数值m，用逗号隔开，如“10，3”：12，6输出出列序列为：6 127 2 108 59 1 11 4 3四、调试分析本题调试的难点主要是对输入合法性的验证。
输入的格式被设计为：“n，m”。
要求先输入一个正整数n，再输入一个逗号，继续输入正整数m，最后按回车结束。
其他形式的输入均不合法。
scanf()函数的格式为：scanf_s("%f,%f", &n, &m)。
scanf()函数按格式正确读入的返回值为2。
初步设计时，根据scanf()函数的返回值，以及成功读入后对n、m的验证（判断n、m是否为负数或浮点数）已能验证需求分析时设计的所有样例。
但是当输入格式为“1，2abc”、“4，21sf”的格式时(即整个输入的前部分是正确格式，如“1，2”、“4，21”)，程序会有根据前部分正确格式计算得到的输出（如输入“1，2abc”时，输出“1”；输入“4，21”时，输出“1 4 2 3”）。
此时的合法性验证中，只要输入时前部分的正确格式被scanf()读取，就会直接无视后半部分不合法的输入，这显然是不合理。
为了避免上述情况，我重新设计了输入合法性验证模块。
通过查阅资料了解到，scanf()成功按格式读入后，输入的回车‘\n’仍余留在输入缓冲区中。
根据这一特点，我首先通过getchar()函数来判断输入缓冲区的余留的第一个字符是否为回车‘\n’，若不是，则证明输入不合法，且该种不合法情况为有多余字符或字符串的输入，这就包括了上述形如“1，2abc”、“4，21sf”的情况，初始值为0的计数变量count在这种情况下加1，在循环的验证中根据count的值来排除这种情况；若是，则通过检验scanf()的返回值和n、m是否为负数或浮点数来验证其合法性。
这样改进后就在原有案例能成功验证的基础上成功规避了上述不合理情况。
之后，又设计了多组测试数据，均能正确验证。
改进前的输入及合法性验证模块：void input(ElemType &n1, ElemType &m1) //输入及合法性检查{float n2, m2;int jud;do{jud = scanf_s("%f,%f", &n2, &m2);if ((jud != 2) || (n2 <= 0) || (m2 <= 0) || (n2 - int(n2)) != 0 || (m2 - int(m2)) != 0){printf("输入有误，请重新输入！\n");while (getchar() != '\n'){}; /*清空输入缓冲，可能有字符串输入，所以用了循环*/}} while ((jud != 2) || (n2 <= 0) || (m2 <= 0) || (n2 - int(n2)) != 0 || (m2 - int(m2)) != 0 );n1 = int(n2);m1 = int(m2);}改进后的输入及合法性验证模块：void input(ElemType &n1, ElemType &m1) //输入及合法性检查{float n2, m2;int jud, count = 0;do{count = 0;jud = scanf_s("%f,%f", &n2, &m2); //按格式成功读入返回2if (getchar() == '\n') //scanf成功读取后仍会余留回车符{if ((jud != 2) || (n2 <= 0) || (m2 <= 0) || (n2 - int(n2)) != 0 || (m2 - int(m2)) != 0){printf("输入有误，请重新输入！\n");continue;}}else{printf("输入有误，请重新输入！\n");count++;while (getchar() != '\n'){}; //清空输入缓冲，可能有字符串输入，所以用了循环}} while ((jud != 2) || (n2 <= 0) || (m2 <= 0) || (n2 - int(n2)) != 0 || (m2 - int(m2)) != 0 || count != 0);n1 = int(n2);m1 = int(m2);}改进前：输入（前部分为正确格式）3，5sd输出2，3，1截图：改进后：输入（前部分为正确格式）3，5sd输出输入有误，请重新输入！截图：五、测试结果①输入（n，m均为正整数，且n>m）10，3输出3 6 9 2 7 1 8 5 10 4测试截图：②输入（n，m均为正整数，且n<m）4，6输出2 1 4 3测试截图：③输入（n，m均为正整数，且n=m）7，7输出7 1 3 6 2 4 5测试截图：④输入 (n,m中有浮点数)8，5.56输出输入有误，请重新输入！测试截图：⑤输入（n,m中有负数）-3，-8输出输入有误，请重新输入！测试截图：⑥输入（n,m未按格式输入）aA2，3asf输出输入有误，请重新输入！测试截图：六、用户使用说明1、本程序的运行环境为Win7 64位操作系统，执行文件为Exp1josephus.exe2、运行程序时提示输入人数和报数值，注意人数和报数值均应为正整数，输入不合法时要求重新输入，在输入时，两者用逗号隔开。