猴子吃桃子问题

数据结构课程设计

班级： 姓名： 学号： 日期：

2011—1—3

目 录

1 问题描述 ................................................................................................. 1 2 需求分析 ................................................................................................. 3 3 概要设计 ................................................................................................. 2 3．1函数应用 2

3．2模块划分 错误！未定义书签。

4 详细设计 ................................................................................................. 3 5 测试分析 ............................................................................................... 10 6 课程设计总结 ...................................................................................... 11

1. 问题描述

猴子吃桃子问题

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求：

1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解

2 需求分析

1） 2） 3）

根据问题已知第十天剩余桃子数，求总共桃子数，我们先列出方程可知，有后往前推可知道每天剩余桃子数 ，这样来求解。 栈链比较困难，需要跟递归联系，递归实现在说。

递归实现可以有数组上体现f(n)=2f(n+1)+2,跟数组的道理查不多，而栈链实现也需要这个方程，所以整个程序是相通的。

3概要设计 1）函数应用

除了主函数以外大部分都是算法函数，还有栈的输入与输出函数：

void main() Push(&S,&e) Pop(&S,&e) 2）模块划分

本程序包括四个模块：

( 1 ) 主程序模块 void main() {

初始化； 数组求解； 递归求解； 栈链求解；

}

( 2 ) 栈模块——实现栈的抽象数据类型 ( 3 ) 数组模块——实现数组的运用 ( 4 ) 递归模块——实现递归的运用

4 详细设计

#include\"stdio.h\" #include\"stdlib.h\" #define N 20 typedef struct node { int datax; int datay; struct node *next; }Node;

typedef Node *LinkStack;

LinkStack Push(LinkStack s,int a, int b) { Node *p;

p=(LinkStack)malloc(sizeof(Node)); p->datax=a;p->datay=b; p->next=s; s=p; return s;

}

LinkStack Pop(LinkStack s) {

LinkStack p; if(s==NULL)

{printf(\"栈已空\\n\"); return NULL; } p=s; s=s->next; free(p); return s; }

void Zhanlian(int n) { int f;

LinkStack s=NULL;

for(n=1;n<=10;n++) {

if(n==10) {f=1; while(s) {

f=s->datax*f+s->datay; s=Pop(s); }

printf(\"%d\\n\} else

s=Push(s,2,2); } }

void suzhu()

{

int i,a[N]; a[10]=1;

for(i=9;i>=1;i--) a[i]=2*a[i+1]+2; printf(\"%d\\n\}

int fun(int n) {

if(n==10) return 1; else

return(2*fun(n+1)+2); }

/*主函数*/

void main() { int sum;

printf(\"数组实现:\"); suzhu();

printf(\"栈链实现:\"); Zhanlian(1); printf(\"递归实现:\"); sum=fun(1); printf(\"%d\\n\ }

5 测试分析

测试数据及结果如下图 ：

6 课程设计总结

总的来说这次课程设计还是学到了一些东西，可能还有很多不足的地方，但希望在以后是学习中补足。总结了一下在这次课程设计中学到的东西，一方面除了进一步巩固了平常上课所学到，和以前学到的东西外。另一方面就是自己的不足了，有时一些以前学过的东西自己不会用，用了反而使程序更复杂，所以一开始的程序很复杂，但是在查过资料后改进才有了这个程序，总觉得在思维上与别人有差距，当然也是自己平常用的少，写的少的缘故，所以在以后自己会多多的写程序，并改进程序，使程序简单化。

最后当然也要感谢老师的教导了