猴子吃桃子 Microsoft Word 文档

猴子吃桃子 Microsoft Word 文档 院、系 专业 姓名 学号 指导教师 二,一, 年 十二 月 二十九 日 猴子吃桃子 摘要:有一群猴子摘了一堆桃子～他们每天都吃当前桃子的一半且再多吃一个～到了第10天就只余下一个桃子。用多种实现求出原来这群猴子共摘了多少个桃子。 关键字:数组，链数据，递归 一、 实验目 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求: 1)采用数组数据结构实现上述求解 2)采用链数据结构实现上述求解 3)采用递归实现上述求解 二、实验分析 这个课程设计分为三个部分，即分别用三种不同的方法解决猴子吃桃子问题。每个部分都有不同的算法思想。 (1)用数组结构实现的算法，通过构造求桃子数的数组，然后输出要求的项来实现。 (2)用链结构实现的算法，则是建立链，将每天的桃子数目存入链表，然后输出第一天的桃子数。 (3)用递归结构实现的算法，是通过函数本身的特点，反复调用自身，最后找到递归的出口，求得算法的解 三、 实验步骤 1、 采用数组数据结构实现 (1) 流程图 1 开始 建立一个以天数为下标以 剩下桃子数为元素的数组 规定此数组的通 向公式 求第一天的桃 子数 (2) 代码 结束 int A[Day+1];//定义数组 int i; A[Day]=1;//第十天的桃子数 for(i=Day;i>=1;i-- ) A[i-1]=(A[i]+1)*2; /*第一天的桃子数是第2天桃子数加1后的2倍*/ printf("the total of peaches are %d ",A[0]) 2、采用链数据结构实现 用链结构实现这个算法，其核心是利用链表这种存储结构，将每天的桃子数存储在链表中，在链表中 实现数的递推。 首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给L。 然后把每天的桃子数从链表的第一个结点插入链表。 最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e，最后只要输出e即得 到第一天的桃子数 void InitList(LinkList &L)//构造一个空链链表 { L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点 if(!L) exit(OVERFLOW); L->next=NULL; } Status ListInsert(LinkList L,int i,ElemType e)//在第i个位置之前插入元素e 2 { int j=0;//计数器初值为0 LinkList s,p=L;//p指向头结点 while(p&&jnext; } 3、 采用递归算法实现 (1)流程图 开始 定义参数i和 n i》0 调用本身，且--i 输出sum 2)代码: 结束int sum_fan(int n,int i) //子函数sum_fun，参数n和i接受主函数的参数 x和day { if (i>0) { n = sum_fan((n+1)*2,--i); //每一次都用((n+1)*2)的值去调用子函数本身 } return n; //返回结果 ) 3 运行结果 数组运行结果 4 链式运行结果 5 递归运行结果 四、总结结论 6 这次的课程设计的内容是用C语言实现猴子吃桃子问题，这对我来说是个很具有挑战性的任务，虽然只做了一个很简单的学生学籍管理模块，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻理解了C++中类的思想和实现，文件的概念和相关操作，以及有关数据结构的很多知识。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。 五、附录(程序) 数组: #include #define Day 9 void main() { int A[Day+1];//定义数组 int i; A[Day]=1;//第十天的桃子数 for(i=Day;i>=1;i-- ) A[i-1]=(A[i]+1)*2; /*第一天的桃子数是第2天桃子数加1后的2倍*/ printf("the total of peaches are %d ",A[0]); } 链式: #include #include #define NULL 0 typedef struct linknode 7 { int data; struct linknode *next;//链表指针 }node; node *head; //头结点 void creat()//创建链表 { node *p,*s; int peaches=1;//第十天时只剩下一个桃子 int day=10; head=(node*)malloc(sizeof(node)); p=head; while(day>0) { s=(node*)malloc(sizeof(node));//分配存属空间 s->data=peaches;//用来存放结点数据 p->next=s; //把结点插入链表中 p=s; peaches=(peaches+1)*2;//第一天的桃子数是第二天桃子数加后的2倍; day-- ; } p->next=NULL; p=head; head=head->next;//使头指针指向头结点 free(p); //释放指针P } void print()//输出从这十天每天的桃子数 { node *p; p=head; int day=10; while(p&&day>0) { printf("第%d天的桃子数:%d个\n",day,p->data); p=p->next; day-- ; } } 8 void main()//主函数 { creat(); print(); } 递归: #include int sum_fan(int n,int i) { if (i>0) { n = sum_fan((n+1)*2,--i); } return n; } int main() { int n; int s=sum_fan(1,9); printf("%d\n",s); return 0; } 参考文献 [1] 王红梅～胡明～王涛. 数据结构(C++版) . 北京:清华大学出版社～2007 [2] 谭浩强 . C++程序设计. 北京:清华大学出版社, 2004 9