猴子吃桃子2.doc

用C语言解决猴子吃桃子问题C语言 C语言=2) 1.2 课程设计目的 在这个程序中我们主要是用 C 语言解决猴子吃桃问题，一群猴子摘了一堆 桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个 桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 生活中或学术上有很多类似的问题，这个问题看似简单，却可能使很多重大 问题的重要组成部分或者是核心。 解决此问题的目的是以便在生活中解决根本性 问题，是生活变得更加便利。 1.3 课程设计内容 这个程序的内容是以 C 语言为程序语言载体分别用数组数据结构、链数据 结构、递归等结构形式实现此问题的求解。 2 需求分析 这个 课程设计 分为三个 部分， 即分别用 三种不同 的方法解 决猴子 吃桃 子问题。每个部分 都有不同的算法思想。 用数 组结构实 现的算法 ，通过 构造求桃 子数的数 组，然后 输出要 求的 项来实现。 用链 结构实现 的算法， 则是建 立链表， 将每天的 桃子数目 存入链 表， 然后输出第一天的 桃子数。 用递 归结构实 现的算法 ，是通 过函数本 身的特点 ，反复调 用自身 ，最 后找到递归的出口 ，求得算法的解。 3 概要设计 2.1 设计思路 C 是结构式语言。结构式语言的显著 特点是代码及数据的分隔化 ，即程 序的 各个部分 除了必要 的信息 交流外彼 此独立。 这种结构 化方式 可使程序 层次清晰，便于使用、维护以及调试。C 语言是以函数形式 提供给用户的， 这些 函数可方 便的调用 ，并具 有多种循 环、条件 语句控制 程序流 向，从而 使程序完全结构化 。 2.2 设计方案 如果 用数组结 构解决这 个问题 ，把猴子 吃桃的天 数倒过来 看的话 ，以 天数作为数组的 下标 i ， 剩下桃子的个数 ai 的递推公式为 ai=(ai- 1+1)*2 。 ai 实际代 表了倒数第 i 天剩下 的桃子数。 所以可以求 得此数组的 通项公式 为 ai=3*2e(i- 1)-2 (i=2)。 如果 用链结构 解决这个 问题， 建立一个 链表，根 据每天桃 子数与 后一 天桃子 数的关系 n=2*n+2, 依次将 每天的桃子 数存进链表 中，最后输 出第一 天的桃子数。 如果 用递归结 构解决这 个问题 ，要求利 用他们每 天都吃当 前桃子 的一 半且再多吃一个这 一特点，设计一个递归算法。 4 详细设计 3.1 数组结构 把猴子吃桃的天数 倒过来看的话，以天数作为数组的 下标 i ，剩下桃子 的个 数 ai 的递 推公式为 ai=(ai- 1+1)*2 。ai 实际 代表了倒 数第 i 天剩 下 的 桃 子 数 。 所 以 可以 求 得 此 数 组 的 通 项 公 式 为 ai=3*pow （2 ， (i- 1) ） -2 (i=2)。数组结构算法的 流程图如图 3-1：开 始 建立一个以天数为下标以 剩下桃子数为元素的数组 规定此数组的通向公式 求第一天的桃子数 结 束 图 3-1 int day,tao11; tao0=0; tao1=1; /定义数组和下标 /tao0赋值为 0 / 倒数第一天的桃子数为 1 for(day=2;daynext=NULL; 这个算法中，我运用了单链表，单链表每个结点由数据和指向后驱结点指针两部 分构成。在插入数据时，将插入的位置的前一项的原有后去指针赋给此结点的后 去指针，然后把插入结点的 data 地址赋给前一结点的后驱指针，插入就完成了。 插入结点的程序代码如下： Status ListInsert(LinkList L,int i,ElemType e)/在第 i 个位置之前插入元素 e int j=0;/计数器初值为 0 LinkList s,p=L;/p 指向头结点 while(p&j0 Y 调用本身，且-i N 输出 sum 开 始 主要程序代码如下： int sum_fan(int n,int i) if (i0) n = sum_fan(n+1)*2,-i); / 子函数 sum_fun ， 参数 n 和 i 接受主函数的参数 x 和 day /每一次都用(n+1)*2)的值去调用子函数本身 5 4.1 运行环境 调试分析 在本课程设计中，系统开发平台为 Windows2000,程序设计语言为 Visual C+6.0，程序的运行环境为 Visual C+ 6.0。Visual C+一般分为三个版本:学习 版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用 这三个版本的任意一种，在本课程设计中，以 Visual C+ 6.0 为编程环境。 Microsoft Visual C+ 6.0 是 Microsoft 公司的 Microsoft Visual Studio 6.0 开发 工具箱中的一个 C+程序开发包。Visual C+包中除包括 C+编译器外，还包括 所有的库、例子和为创建 Windows 应用程序所需要的文档。自 1993 年 Microsof 公司推出 Visual C+1.0 后，随着其新版本的不断问世，Visual C+已成为专业程 序员进行软件开发的首选工具。 Visual C+从最早期的 1.0 版本，发展到最新的 7.0 版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许 多的增强。最新的 7.0 版本在编译器、MFC 类库、编辑器以及联机帮助系统等 方面都比以前的版本做了较大改进。 虽然微软公司推出了 Visual C+.NET(Visual C+7.0)，但它的应用的很大的 局限性，只适用于 Windows 2000,Windows XP 和 Windows NT4.0。所以实际中， 更多的是以 Visual C+6.0 为平台。 Visual C+ 6.0 是 Microsoft 公司推出的目前使用最广泛的基于 Windows 平台 的可视化编程环境。Visual C+ 6.0 是在以往版本不断更新的基础上形成的，由 于其功能强大，灵活性好，完全课扩展以及具有强大的 Internet 支持，因而在各 种 C+语言开发工具中脱颖而出，成为目前最为流行的 C+语言集成开发环境。 Visual C+ 6.0 秉承 Visual C+以前版本的优异特性，为用户提供了一套良 好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、 4.2 运行结果数组结构的运行结 果如图 4-1 图 4-1 数组结构结果 链结构的运行结果 如图 4-2 图 4-2 链结构结果 递归结构的运行结 果如图 4-3 图 4-3 递归结构结果 6 总结 这次的课程设计的内容是用 C 语言实现猴子吃桃子问题，这对我来说是个 很具有挑战性的任务，虽然只做了一个很简单的学生学籍管理模块，但通过两个 星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。 数据结构 是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时， 加 强上机实践。 同时再次深刻理解了 C+中类的思想和实现，文件的概念和相关操 作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加 以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论 与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本 的，良好的程序设计技能。提高综合运用所学知识的能力。 在这次课程设计中曾遇到了不少问题， 就单凭我一个人的能力很难准时有效 的完成这次的课程设计，在此，我忠心感谢我的指导老师湛新霞。湛老师对 工作认真负责，耐心辅导，知识丰富而且相当和蔼。在这次课程设计中给了我很 大的帮助。他严谨的治学精神和深厚的理论水平都使我获益非浅。同时还要感谢 我的同学，他们为我提出了很多有用的建议，帮助我完成了这次的课程设计。 最 后也要感谢我们学校为我们提供良好的编程环境，使我们能够按时完成任务。 参考文献 1 王红梅，胡明，王涛. 数据结构(C+版) . 北京：清华大学出版社，2007 2 王红梅，胡明，王涛. 数据结构(C+版) 学习辅导与实验指导. 北京：清华 大学出版, 2007 3 谭浩强 . C+程序设计. 北京：清华大学出版社, 2004 . 4 郑阿奇，丁有和. Visual C+教程.北京：机械工业出版社，2006 . 5 李文军，李师贤， 周晓聪. C+作为计算机专业程序设计入门语言的实践与探 . 讨. 计算机科学，1999，26（4） ：8083 附录：源程序代码 数组结构代码 # include # include void main() int day,tao11; /定义数组和下标tao0=0; /tao0 赋值为 0tao1=1; /倒数第一天的桃子数为 1 for(day=2;daynext=NULL; tatus GetElem(LinkList L,int i,ElemType &e)/当第 i 个元素存在的时，将其值赋 给e while(p&jnext; if(!p|ji) return ERROR; e=p-data; return OK; Status ListInsert(LinkList L,int i,ElemType e)/在第 i 个位置之前插入元素 e int j=0;/计数器初值为 0 LinkList s,p=L;/p 指向头结点 while(p&jnext; if(!p|ji-1) return 0; s=(LinkList)malloc(sizeof(LNode);/生成新的结点 s-data=e; s-next=p-next;/新结点指向原第 i 个结点 p-next=s;/原第 i-1 个结点指向新结点 return 1; void main() InitList(L);/初始化链表 for(i=1,n=1;i=10;i+) n=2*n+2;/将每一天的桃子数赋值给 n ListInsert(L,1,n);/将 n 的值输入链表 Status GetElem(L,1,e); printf(%d,e);/输出桃子的数目 递归结构代码 include int sum_fan(int n,int i) / 子函数 sum_fun ，参数 n 和