1、 一、一、设计题目设计题目 猴子吃桃子问题猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一 个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共 摘了多少个桃子。 二、运行环境（软、硬件环境）二、运行环境（软、硬件环境） VC+6.0 PCVC+6.0 PC 电脑一台电脑一台 三、三、算法的需求分析算法的需求分析 1) 采用数组数据结构实现上述求解 2) 采用链数据结构实现上述求解 3) 采用递归实现上述求解 4) 如果采用 4 种方法者,适当加分 /用户界面 int Desk(int n) printf(“*n“); printf(“| 欢迎进入
2、猴子吃桃子系统 |n“); printf(“| 1-数组法 2-链表法 3-递归法 4-二叉树法 5-退出 |n“); printf(“*n“); printf(“请输入要选择的方法: “); scanf(“%d“, getchar(); system(“cls“); /刷新屏幕 while(n5) printf(“*输入错误 ! 请重新输入*n“); scanf(“%d“, return n; 四、算法概要设计四、算法概要设计 /采用链数据结构 (栈) 实现上述求解 typedef struct int *top; int *base; stack; /初始化一个栈 stack Init(s
3、tack *s) s-base=(int *)malloc(STACK_SIZE*sizeof(int); if(s-base = NULL) printf(“Init failed !n“); exit(-1); s-top = s-base; return *s; /二叉树 创建一个大小为 DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右 节点存放数字 1，即为多吃的一个桃子。 typedef struct TNode int data; struct TNode *lchild; struct TNode *rchild; tree; /创建一个二叉树 tree Cr
4、eatTree(tree *T) /T 为指针类型 int n=0,i=0; tree *p,*pr,*T1; T=(tree *)malloc(sizeof(TNode); T1=T; T-data=1; /根节点内的数据为第 DAYS 天的桃子数 for(i=1; ilchild=NULL; pr-rchild=NULL; p-data=0; pr-data=1; T1-lchild=p; T1-rchild=pr; T1=p; T1-lchild=NULL; T1-rchild=NULL; return *T; /返回 T 的地址 /算法框架图算法框架图 N Y N Y 打印共摘的桃子数
5、 量 判断是否执行 完毕 进入猴子吃桃子系统界面 开始 选择要使用的方法 进入该函数 判断是否执行 完毕 继续执行 五、五、算法详细设计算法详细设计 #include #include #include “peach.h“ /函数声明 int Desk(int n); void peach_1(void); stack Init(stack *s); void Push(stack *s,int num); void Pop(stack *s,int void peach_2(stack *s); void peach_3(int n,int i); tree CreatTree(tree *T); void calculate(tree *T); void peach_4(tree *T); int main() int data=0; int n=1,i=1; stack s; tree T; s=Init( T=CreatTree( while(1) switch(Desk(n) case 1: peach_1(); break; case 2: peach_2( break; case 3: peach_3(n,i); break; case 4: peach_4( break; case 5: exit(0); break; return 0; /头文件
