猴子吃桃问题—数据结构课程设计.doc-资料库

a2450299730-5726761-4744302543415067361.doc.pdf-第1页.png

第1页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第2页.png

第2页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第3页.png

第3页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第4页.png

第4页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第5页.png

第5页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第6页.png

第6页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第7页.png

第7页 / 共11页

a2450299730-5726761-4744302543415067361.doc.pdf-第8页.png

第8页 / 共11页

长春大学课程设计纸目录一、设计目的 ........................................................... 2 二、设计内容 ........................................................... 2 三、程序流程 ........................................................... 2 四、设计步骤 ........................................................... 4 五、设计总结 ........................................................... 8 六、程序清单 ........................................................... 9 七、参考文献 .......................................................... 11 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 共 11 页第 1 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学 1 设计目的课程设计纸 1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2 设计内容 2.1.问题描述有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 2.2.基本要求 1) 采用顺序表实现上述求解； 2) 采用链表实现上述求解； 3) 采用递归实现上述求解； 4) 使用其他方法实现上述求解； 3 程序流程 3.1 顺序表（数组） 1) 创建数组函数，大小为 10 2) 用 for 循环循环数组，利用核心算法（详见设计步骤）循环计算 3) 输出结果 3.2 链表 1) 主要方法：用动态链表存储方式实现求解函数 2) 定义节点的结构体，并且创建链表函数 3) 开辟动态链表存储空间 4) 利用 for 循环并结合核心算法求出结果（注意：始终使得第一个指针指向最后一个新开节点，而第二个指针指向第一个指针）。 5) 得到结果并输出共 11 页第 2 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学 3.3 递归课程设计纸 1) 创建递归算法的函数，这个函数有两个参数，其中封装了核心算法 2) 创建第二隔递归算法的函数，在这个函数当中循环调用第一个封装了核心算法的函数 3) 得到结果并输出 3.4 其他方法（while 循环）直接在主函数中利用核心算法和 while 循环，计算得到结果数组流程图开始执行 int a [ 10 ] 令 i=1, n=1 执行 a[i-1] = (n+1) * 2 执行 i++ i 是否小于 10 N 输出桃子总数退出或其他操作 Y 共 11 页第 3 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学递归算法流程图课程设计纸开始调用递归算法 recursive_2（） i 是否大于 0？ Y 返回结果桃子总数 n N 退出或其他操作其他算法流程图开始令 i = 1 令 sum + = ( i + 1 ) * 2 令 i 自增（ ++i ） i 是否小于 10 Y N 输出结果桃子总数 n 退出或其他操作共 11 页第 4 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学 4 设计步骤 4.1 问题分析课程设计纸猴子在第十天的时候发现只剩下一个桃，那么由“一天吃一半多一个”的规则可知，在第九天的时候还有（1+1）*2=4 个桃，同理可得第八天还有（4+1）*2=10 个桃，第七天还有（10+1）*2=22 个桃……，所以我们可以用如下这段代码求解此问题： for(int i=1;i<10;i++) sum+=(i+1)*2; 此算法便是解决这个问题的核心算法。 4.2 分别用顺序表、链表、递归实现问题分析中的核心代码 1) 顺序表首先可以确定的是我们用数组来实现顺序表的算法。创建一个大小为 10 的数组，用来代表第几天还有几个桃，并且声明一个变量 n,同样的,代表第几天还有几个桃。将核心公式带入到里面，我们遍可以得到(n+1)*2, 并将 n 的值赋给 a[i-1]。用 for 循环循环 10 次，a[0]就是我们想要的结果。 2) 链表首先我们先创建链表所要用到的节点的结构体，这个机构体包括一个 int 类型的数据部分，和一个指针域。在 link（）函数中开辟动态链表存储空间。利用核心算法，在 for 循环中将每天得到的值赋给链表中的相应的节点，当然，赋值的过程由链表的指针域控制。特别应该注意的是，始终使得 p1 指针指向最后一个新开节点，而 p2 指向 p1。 3) 递归创建一个 recursive_2 函数，实际上，它是封装了核心算法的函数。这个函数有两个整型参数，n 和 i。n 用来控制每天所剩的桃的数量，i 用来控制天数。这个函数重复的调用自己，因为每次调用自己是，i 和 n 都在以核心算法所运算的规则（（n+1）*2）递增，所以每次调用自己得到的结果便是我们想要的结果。 4) 其他算法这个部分其实可以有很多种算法，但是核心算法依然不变（（n+1）*2），唯一可以变的地方是用不同的语法来实现循环，可选的有 for，while， do while，if 等。共 11 页第 5 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学 4.3 调试 1) 进入程序，并选择算法课程设计纸 2) 进入数组计算（顺序表）共 11 页第 6 页

长春大学 3) 进入链表计算课程设计纸 4) 进入递归计算 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 共 11 页第 7 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长春大学 5) 进入其他计算课程设计纸 5 设计总结这是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，李老师就为我们阐述了它的重要性。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。VC++6 里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。共 11 页第 8 页

资料库

猴子吃桃问题—数据结构课程设计.doc

相关推荐

开发技术

热门标签

最新资料