猴子吃桃子问题

《猴子吃桃子问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计班级：姓名：学号：日期：2011—1—3目录1问题描述12需求分析13概要设计23．1函数应用23．2模块划分24详细设计35测试分析106课程设计总结111.问题描述猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解2需求分析1）根据问题已知第十天剩余桃子数，求总共桃子数，我们先列出方

2、程可知，有后往前推可知道每天剩余桃子数，这样来求解。2）栈链比较困难，需要跟递归联系，递归实现在说。3）递归实现可以有数组上体现f(n)=2f(n+1)+2,跟数组的道理查不多，而栈链实现也需要这个方程，所以整个程序是相通的。3概要设计1）函数应用除了主函数以外大部分都是算法函数，还有栈的输入与输出函数：voidmain()Push(&S,&e)Pop(&S,&e)2）模块划分本程序包括四个模块：(1)主程序模块voidmain(){初始化；数组求解；递归求解；栈链求解；}(2)栈模块——实现栈的

3、抽象数据类型(3)数组模块——实现数组的运用(4)递归模块——实现递归的运用4详细设计#include"stdio.h"#include"stdlib.h"#defineN20typedefstructnode{intdatax;intdatay;structnode*next;}Node;typedefNode*LinkStack;LinkStackPush(LinkStacks,inta,intb){Node*p;p=(LinkStack)malloc(sizeof(Node));p->dat

4、ax=a;p->datay=b;p->next=s;s=p;returns;}LinkStackPop(LinkStacks){LinkStackp;if(s==NULL){printf("栈已空");returnNULL;}p=s;s=s->next;free(p);returns;}voidZhanlian(intn){intf;LinkStacks=NULL;for(n=1;n<=10;n++){if(n==10){f=1;while(s){f=s->datax*f+s->datay;s

5、=Pop(s);}printf("%d",f);}elses=Push(s,2,2);}}voidsuzhu(){inti,a[N];a[10]=1;for(i=9;i>=1;i--)a[i]=2*a[i+1]+2;printf("%d",a[1]);}intfun(intn){if(n==10)return1;elsereturn(2*fun(n+1)+2);}/*主函数*/voidmain(){intsum;printf("数组实现:");suzhu();printf("栈链实现:")

6、;Zhanlian(1);printf("递归实现:");sum=fun(1);printf("%d",sum);}5测试分析测试数据及结果如下图：6课程设计总结总的来说这次课程设计还是学到了一些东西，可能还有很多不足的地方，但希望在以后是学习中补足。总结了一下在这次课程设计中学到的东西，一方面除了进一步巩固了平常上课所学到，和以前学到的东西外。另一方面就是自己的不足了，有时一些以前学过的东西自己不会用，用了反而使程序更复杂，所以一开始的程序很复杂，但是在查过资料后改进才有了这个程序，总觉得在

7、思维上与别人有差距，当然也是自己平常用的少，写的少的缘故，所以在以后自己会多多的写程序，并改进程序，使程序简单化。最后当然也要感谢老师的教导了