数据结构课程设计-猴子吃桃问题(DOC)

《数据结构课程设计-猴子吃桃问题(DOC)》由会员分享，可在线阅读，更多相关《数据结构课程设计-猴子吃桃问题(DOC)（16页珍藏版）》请在毕设资料网上搜索。

1、 0 数学与计算机学院 课程设计说明书 课 程 名 称: 课 程 代 码: 题 目: 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2014 2014 年 5 5 月 14 14 日 完 成 时 间: 2014 2014 年 5 5 月 28 28 日 1 目 录 1 需求分析3 2 概要设计3 3 详细设计4 4 调试分析11 5 用户使用说明12 6 测试结果12 7 结论14 致谢15 参考文献15 2 摘摘 要要 本课程设计主要解决猴子吃桃子的问题。一群猴子摘了一堆桃子，他 们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一 个桃子。用多种方法实现求出原

2、来这群猴子共摘了多少个桃子。在课 程设计中，系统开发平台为 Windows 2000，程序设计设计语言采用 Visual C+，数据库采用 MS SQL 2000，程序运行平台为 Windows 98/2000/XP。在整个程序中分别采用数组数据结构、链数据结构、递 归等结构形式实现此问题的求解。程序通过调试运行，初步实现了设 计目标。 关键词：关键词：程序设计；C+；数组；链；递归；猴子吃桃 引 言 在日常生活中经常遇到一些与数据计算有关的问题， 许多与猴子吃桃 问题类似的问题要求用计算机程序语言来解决，用这个程序算法可以解决 一些类似问题，以便利于生活实际。 3 1 需求分析 1.1 任务

3、与分析 任务功能：有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多 吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共 摘了多少个桃子 要求： 采用数组数据结构实现上述求解 采用链数据结构实现上述求解 采用递归实现上述求解 如果采用 4 种方法者,适当加分 分析： 这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃 子问题。每个部分都有不同的算法思想。 用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的 项来实现。 用链结构实现的算法，则是建立链表，将每天的桃子数目存入链表， 然后输出第一天的桃子数。 用递归结构实现的算法，是通过函数本身的特

4、点，反复调用自身，最 后找到递归的出口，求得算法的解。 1.2 测试数据 输入任意一篇文章，按要求输入功能序号与字符串。 测试是否能按要求输出正确结果。 2 概要设计 C 是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程 4 序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序 层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的， 这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而 使程序完全结构化。 如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以 天数作为数组的下标 i， 剩下桃子的个数 ai的递推公式为 ai=(ai-1+

5、1)*2。 ai实际代表了倒数第 i 天剩下的桃子数。所以可以求得此数组的通项公式 为 ai=3*2e(i-1)-2 (i=2)。 如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一 天桃子数的关系 n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一 天的桃子数。 如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一 半且再多吃一个这一特点，设计一个递归算法。 3 详细设计 3.1 数组结构 把猴子吃桃的天数倒过来看的话，以天数作为数组的下标 i，剩下桃子 的个数 ai的递推公式为 ai=(ai-1+1)*2。ai实际代表了倒数第 i 天剩下 的桃子数。所以可以求得此数组的通项公式为 ai=3*pow（2，(i-1)）-2 (i=2)。数组结构算法的流程图如图 3-1： 建立一个以天数为下标以 剩下桃子数为元素的数组 规定此数组的通向公式 开 始 5 图图 3-1 int day,tao11; /定义数组和下标 tao0=0; /tao0