作业帮猴子选大王课程设计
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/14 09:38:59 字数作文
篇一：猴子选大王 课程设计报告
目录
一、需求分析 ................................................................................................................................... 1
1、问题描述： ......................................................................................................................... 1
2、基本要求： ......................................................................................................................... 1
3、需求分析： ......................................................................................................................... 1
二、概要设计 ................................................................................................................................... 2
三、详细设计 ................................................................................................................................... 3
1、循环队列 ............................................................................................................................. 3
2、循环链表 ............................................................................................................................. 4
3、伪代码 ................................................................................................................................. 5
4、具体函数分析及变量分析 ................................................................................................. 6
四、调试分析和测试结果 ............................................................................................................... 6
五、总结........................................................................................................................................... 9
六、参考文献 ................................................................................................................................. 10
七、附录......................................................................................................................................... 11
一、需求分析
1、问题描述：
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
2、基本要求：
输入数据：输入m,n。 m,n 为整数，n 输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的 猴子是几号 ，建立一个函数来实现此功能。 3、需求分析： ① 输入数据m,n ② 计算出最终猴子大王的序号。 ③ 模拟出整个过程。 ④ 找到合适的数据结构处理这个问题。 ⑤ 找到正确的方法解决这个问题。 二、概要设计 对题意进行分析后，可以画出整个过程的流程图。 具体流程图: 这个问题属于约瑟夫环问题，我们对这个题目进行具体分析： 假如现在m=5,n=2,即有5只猴子，按照循环数2的方法，我们演变这个过程： 第一次：1 2 3 4 5 × 2号出局 第二次：1 2 3 4 5 × × 4号出局 第三次：1 2 3 4 5 × × × 1号出局 第四次：1 2 3 4 5 × × × × 5号出局 最后得到猴子大王的序号是3号。 那么一般化，对于m猴子，n只猴子我们该怎么做？ 三、详细设计 1、循环队列 队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 仔细分析整个过程，我发现这个过程和学过的循环队列特别像，在学习循环队列的时候，如果采取数组来存储队列，那么在front端弹出元素就执行front=（front+1)%MAX，在rear端进入队列的时候就执行rear=（rear+1)%MAX，以实现绕圈的操作。 回顾一下循环队列的具体的入队算法： 1、tail=tail+1； 2、若tail=n+1，则tail=1； 3、若head=tail尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理； 4、否则，Q(tail)=X，结束（X为新入出元素）。 队列空的条件：front==rear 队列满的条件： （rear+1）% =MAXSIZE==front 那么在这个问题中能不能学习这个技巧？仔细想想，我认为答案是可以的。 在问题中还牵涉到一个淘汰的过程，对于这个问题，我们该怎么处理？其实这个问题比较好处理，如果我们采取的是链表那么直接删除掉就可以了，如果是数组，我们只要把删除的做个标记，下次碰到已经删除的直接跳过这个元素就可以了。 2、循环链表 在这个问题上也可以用链表。 链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据和一或两个用来指向明上一个/或下一个节点的位置的地址。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表有很多种不同的类型：单向链表，双向链表以及循环链表。 显然这个问题可以用循环链表处理。 循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。 篇二：猴子选大王 课程设计文档 XXXX大学计算机系 课程设计说明书 课程名称课程代码题 目年级/专业/班学生姓名学 号 指导老师开题时间完成时间数据结构 猴子选大王 2009 年 月 日 : : : : : : : : : 目 录 摘 要 .................................................................................................................. 3 一、引 言(小三号、黑体、加粗) ..................................................................... 4 二、设计目的与任务 ........................................................................................... 4 1、课程设计的目的 ....................................................................................... 4 2、课程设计的任务 ....................................................................................... 5 三、设计方案与实施(小三号、黑体、加粗) ................................................... 5 1、总体设计 ................................................................................................... 5 2、详细设计 ................................................................................................... 6 3、程序清单 ................................................................................................... 8 4、程序调试与体会 .....................................................................................10 5、运行结果（截图） ................................................................................. 11 四、结 论 ..........................................................................................................12 五、致 谢 ..........................................................................................................12 六、参考文献......................................................................................................13 1、设计的目的与要求： .............................................................................14 2、设计进度及完成情况 .............................................................................14 摘 要 线性链表是一种重要而且使用广泛的数据结构，用链表所表示数据元素之间的逻辑关系是由节点中的指针指示的，而循环链表的特点是表种最后一个节点的指针指向头结点，整个链表形成一个环，用循环链表作为本课题的数据存储结构，充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，大大降低空间复杂度就简单的实现了要求，动态地模拟出了猴子选大王问题中猴子循环报数的情况。 关键词：数据结构 线性链表 存储结构 空间复杂度（3~5个） Abstract Linear list is an important and extensive use of the data structure,List said that the data used by the logic of relations between the elements by the node in the direction of the pointer,The circulation list of the characteristics of the species list is the last node of the indicators point to the first node, the entire list to form a ring,With the cycle of the list as the subject of data storage structures, taking into account the full cycle through the list of the characteristics of only two out of circulation list, out into operation, greatly reduce the complexity of space on the realization of a simple request,To simulate the dynamics of the monkey king election issue in a number of monkeys circulation Situation Key words: Data Structure, Linear List, Storage structure, Space complexity 《数据结构》课程设计 --猴子选大王问题设计 一、引 言 数据结构是一门专业技术基础课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。 循环链表是一种重要的链式结构，其特殊性在于需附设两个指针分别指示表头元素及表尾元素的位置且表头和表尾相邻接，臆造的环状空间巧妙的解决了需循环依次删除元素的约瑟夫问题。 本设计采用目前最通用的程序设计语言之一——C语言作为数据结构和算法的描述语言，循环链表作为数据存储结构。 充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，就简单的实现了要求，动态的模拟出了猴子选大王问题中猴子循环报数的情况。该程序通俗易懂且实用性强，其他类似的算法均可借鉴和参考使用。并且该程序清单详细具体、全面、具有很强的可读性。 二、设计目的与任务 1、课程设计的目的 1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本 方法和技能； 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算 2) 法设计、编写程序，求解出指定的问题； 3) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生 的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风； 4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 2、课程设计的任务 问题描述：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个） 按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 课题要求：输入数据m,n 其中m,n 为整数，n输出形式为提示按照m个 猴子，数n 个数的方法，输出为大王的猴子是几号 三、设计方案与实施 1、总体设计 //写总体的设计思想 采用两个循环队列反复出队列与入队列来进行“舞伴配对”。程序中主要用到以 下抽象数据类型： 1) 设定链表抽象数据类型的定义 ADT struct {对象数据＝（整数） 操作对象:struct monkey *create() 建立链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 篇三：猴子选大王数据结构课程设计报告(内附详细注释) 1.需求分析 问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m 问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m 第一步 建立数组，填入猴子编号及猴子出局时报的数 第二步 从第一个猴子报数 第三步 数到m让指针指向元素变为0 第四步 继续报数，重复第三步 2.概要设计（流程图） 3.详细设计 #include #include void FindKing_pointer(int,int,int*);//移动指针法找大王 void Initialize(int,int*);//初始化数组 整形和指针型 int main() { int m,n,*ptr; printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); while(n { printf("输入数据有误，请重新输入!\n"); printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); } ptr=(int *)calloc(n,sizeof(int)); Initialize(n,ptr); FindKing_pointer(m,n,ptr); free(ptr); return 0; } /* 在数组中依次填入1,2,3,4,… */ void Initialize(int n,int *ptr) { int i; for(i=0;i ptr[i]=i+1; } /* 循环一次指针向后移一位,所指元素不为0时计数器加1. 移动指针,当计数器数到m时将指针所指元素设为0. */ void FindKing_pointer(int m,int n,int *ptr) { int i,count,*ptr2; count=n-1; //count=0时终止循环 就是只剩一个猴子时 ptr2=ptr; // 移动ptr2进行查找 开始时ptr为多少 //calloc()为指针类型的元素分配内存时，元素被初始化为空指针 for(i=0;count!=0;ptr2++) { if(ptr2==ptr+n) ptr2=ptr; /*指针所指元素不为0时计数器加1.*/ if(*ptr2!=0) i++; /*计数器数到m时将指针所指元素设为0*/ if(i==m) { *ptr2=i=0; count--; //用于终止循环 } } /*最后不为0的元素的值即为大王的编号*/ for(ptr2=ptr;;ptr2++) { if(*ptr2!=0) { printf("第%d个猴子是大王\n",*ptr2); break; } } } /*思想是猴子围坐一圈，有N个猴子，开始数数，数到第M个猴子，该猴子就出列， 然后再从该猴子的下一个猴子开始数到第M个猴子，直到只剩下一个猴子时。该猴子就是 所要选得大王 */ 4.结果分析 5.设计总结 在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。 篇四：猴子选大王数据结构课程设计 11信计2012-2013（一） 数 据 结 构 课 程 设 计 设计题目 猴子选大王 设计时间 学生姓名 学生学号 所在班级 11精算 指导教师 徐州工程学院数学与物理科学学院 一、需求分析 问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m 问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m 第一步 建立数组，填入猴子编号及猴子出局时报的数 第二步 从第一个猴子报数 第三步 数到m让指针指向元素变为0 第四步 继续报数，重复第三步 二、概要设计 程序流程图 三、详细设计 #include #include void FindKing_pointer(int,int,int*);//移动指针法找大王 void Initialize(int,int*);//初始化数组 整形和指针型 int main() { int m,n,*ptr; printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); { printf("输入数据有误，请重新输入!\n"); printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m); } ptr=(int *)calloc(n,sizeof(int)); Initialize(n,ptr); FindKing_pointer(m,n,ptr); free(ptr); return 0; } /* 在数组中依次填入1,2,3,4,… */ void Initialize(int n,int *ptr) { int i; for(i=0;i 循环一次指针向后移一位,所指元素不为0时计数器加1. 移动指针,当计数器数到m时将指针所指元素设为0. */ void FindKing_pointer(int m,int n,int *ptr) { int i,count,*ptr2; count=n-1; //count=0时终止循环 就是只剩一个猴子时 ptr2=ptr; // 移动ptr2进行查找 开始时ptr为多少 //calloc()为指针类型的元素分配内存时，元素被初始化为空指针 for(i=0;count!=0;ptr2++) { if(ptr2==ptr+n) ptr2=ptr; /*指针所指元素不为0时计数器加1.*/ if(*ptr2!=0) i++; /*计数器数到m时将指针所指元素设为0*/ if(i==m) { count--; //用于终止循环 } } /*最后不为0的元素的值即为大王的编号*/ for(ptr2=ptr;;ptr2++) { if(*ptr2!=0) { printf("第%d个猴子是大王\n",*ptr2); break; } } } /*思想是猴子围坐一圈，有N个猴子，开始数数，数到第M个猴子，该猴子就出列， 然后再从该猴子的下一个猴子开始数到第M个猴子，直到只剩下一个猴子时。该猴子就是 所要选得大王 */ 四、调试分析 1）输入猴子数与出局时报的数 9 5 第6个猴子是大王 2）输入猴子数与出局时报的数 5 3 第5个猴子是大王 3) 输入猴子数与出局时报的数 6 8 输入数据有误，请重新输入! 输入猴子数与出局时报的数 7 7 第2个猴子是大王 4）输入猴子数与出局时报的数 145 145 第94个猴子是大王 5）输入猴子数与出局时报的数 5 1 第6个猴子是大王 篇五：猴子选大王——课程设计 邮电与信息工程学院 课程设计说明书 课题名称： 猴子选大王 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师： 课题工作时间： 2010-6-22 至 2010-6-25 1 2 3 4 目 录 摘 要 …………………………………………………….……………......….……,…………… 6 Abstract ………………………………………………….……………...…....…,……………... 7 第一章 课题背景…………………………………….…….……………….…………,………..8 1.1课程设计的目的…………………..……………...…………………………...……….……..8 1.2 课程设计的要求………..…………………………..….……….………......……,………… 8 1.3 课程设计的实验环境………..…………………………………..………...……,……….… 8 第二章 课程设计详细内容 …………..……………………………..………………,,.……….. 9 2.1 问题描述…..……………………………………………………….……..………,,..…….…9 2.2 程序代码精解…………………..……..………………....…………….…………,,..…….…9 2.3 程序结果运行……………………..……..………………....……..……………,……….…13 总 结 …….……………………………………………………..………………,……….…..… 15 致 谢 …….……………………………………………………..………………..,…………..…16 参考文献 …….………………..………………………………..…………..……,….……….…17 附录 主要程序代码 ………...………………………………..………….……,……..…….…18 5