猴子吃桃问题数据结构课程设计

一、设计题目猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。

用多种方法实现求出原来这群猴子共摘了多少个桃子。

二、运行环境（软、硬件环境）VC++6.0 PC电脑一台三、算法的需求分析1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解4)如果采用4种方法者,适当加分//用户界面int Desk(int n){printf("**************************************************\n");printf("| 欢迎进入猴子吃桃子系统|\n");printf("| 1-数组法2-链表法3-递归法4-二叉树法5-退出|\n");printf("***************************************************\n");printf("请输入要选择的方法: ");scanf("%d",&n);getchar();system("cls"); //刷新屏幕while(n<1 || n>5){printf("***输入错误! 请重新输入***\n");scanf("%d",&n);}return n;}四、算法概要设计//采用链数据结构(栈) 实现上述求解typedef struct{int *top;int *base;}stack;//初始化一个栈stack Init(stack *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 CreatTree(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; i<DAYS; i++){p=(tree *)malloc(sizeof(TNode));pr=(tree *)malloc(sizeof(TNode));pr->lchild=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的地址}//算法框架图Y五、算法详细设计#include <stdio.h>#include <stdlib.h>#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 &num);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(&s);T=CreatTree(&T);while(1){switch(Desk(n)){case 1: peach_1();break;case 2: peach_2(&s);break;case 3: peach_3(n,i);break;case 4: peach_4(&T);break;case 5: exit(0);break;}}return 0;}//头文件代码#define DAYS 10 //定义给定的天数#define STACK_SIZE 5 //栈的容量,实际只用了一个#define TRUE 1#define ERROR 0void peach_3(int n,int i);//用户界面int Desk(int n){printf("**************************************************\n");printf("| 欢迎进入猴子吃桃子系统|\n");printf("| 1-数组法2-链表法3-递归法4-二叉树法5-退出|\n");printf("***************************************************\n");printf("请选择要使用的方法: ");scanf("%d",&n);getchar();system("cls"); //刷新屏幕while(n<1 || n>5){printf("***输入错误! 请重新输入***\n");scanf("%d",&n);}return n;}//采用数组数据结构实现上述求解void peach_1(void){int peach[50]={0};int i=0,j=0;peach[DAYS-1]=1; //最后一天的桃子数for(i=DAYS ; i>0; --i , j=i-1){peach[j] = 2*(peach[i] + 1);}printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 数组法* \n");printf("* 这群猴子共摘了%d 个桃子*\n",peach[0]);printf("* * * * * * * * * * * * * * * * * * * * *\n");}//采用链数据结构实现上述求解typedef struct{int *top;int *base;}stack;//初始化一个栈stack Init(stack *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;}//把当天的桃子数进栈void Push(stack *s,int num){*s->top++ = 2*(num + 1);}//把前一天的桃子数出栈void Pop(stack *s,int &num) //&num位地址传递，可以直接对参数进行修改{num = *--s->top;}void peach_2(stack *s){int i=0;int num=0;Push(s,1); //先把最后一天的桃子数进栈i++;while(i < DAYS){Pop(s,num);Push(s,num);i++;}printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 链表法* \n");printf("* 这群猴子共摘了%d 个桃子*\n",num);printf("* * * * * * * * * * * * * * * * * * * * *\n");void peach_3(int n,int i){if(i ==DAYS) //DAYS 为递归终止条件由用户给出{printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 递归法*\n");printf("* 这群猴子共摘了%d 个桃子*\n",n);printf("* * * * * * * * * * * * * * * * * * * * *\n");}else{n = 2*(n + 1);peach_3(n,i+1);}}//二叉树typedef struct TNode{int data;struct TNode *lchild;struct TNode *rchild;}tree;tree CreatTree(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; i<DAYS; i++){p=(tree *)malloc(sizeof(TNode));pr=(tree *)malloc(sizeof(TNode));pr->lchild=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的地址//对二叉树进行赋值计算 void calculate(tree *T) { int i=0; tree *T1,*T2,*T3; //T1,T3分别为T2的左右孩子 T2=T; for(i=0; i<DAYS-1; i++) { T1=T2->lchild; T3=T2->rchild; T1->data=2*(T2->data + T3->data); T2=T1; } }//二叉树遍历最左下角的孩子节点 void peach_4(tree *T) { calculate(T); while(T->lchild != NULL) { T=T->lchild; } printf("* * * * * * * * * * * * * * * * * * * * *\n"); printf("* 二 叉 树 法 *\n"); printf("* 这群猴子共摘了 %d 个桃子 *\n",T->data); printf("* * * * * * * * * * * * * * * * * * * * *\n"); }六、算法的测试//主函数#include <stdio.h> #include <stdlib.h> #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 &num); 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(&s);T=CreatTree(&T);while(1){switch(Desk(n)){case 1:peach_1();break;case 2:peach_2(&s);break;case 3:peach_3(n,i);break;case 4:peach_4(&T);break;case 5:exit(0);break;}}return 0;}//采用数组数据结构实现上述求解void peach_1(void){int peach[50]={0};int i=0,j=0;peach[DAYS-1]=1; //最后一天的桃子数for(i=DAYS ; i>0; --i , j=i-1){peach[j] = 2*(peach[i] + 1);}printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 数组法* \n");printf("* 这群猴子共摘了%d 个桃子*\n",peach[0]);printf("* * * * * * * * * * * * * * * * * * * * *\n");}void peach_2(stack *s){int i=0;int num=0;Push(s,1); //先把最后一天的桃子数进栈i++;while(i < DAYS){Pop(s,num);Push(s,num);i++;}printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 链表法* \n");printf("* 这群猴子共摘了%d 个桃子*\n",num);printf("* * * * * * * * * * * * * * * * * * * * *\n");}void peach_3(int n,int i){if(i ==DAYS) //DAYS 为递归终止条件由用户给出{printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 递归法* \n");printf("* 这群猴子共摘了%d 个桃子*\n",n);printf("* * * * * * * * * * * * * * * * * * * * *\n");}else{n = 2*(n + 1);peach_3(n,i+1); //循环体}}//二叉树遍历最左下角的孩子节点void peach_4(tree *T){calculate(T);while(T->lchild != NULL){T=T->lchild;}printf("* * * * * * * * * * * * * * * * * * * * *\n");printf("* 二叉树法*\n");printf("* 这群猴子共摘了%d 个桃子*\n",T->data);printf("* * * * * * * * * * * * * * * * * * * * *\n");七、运行结果分析1、数组法：创建一个大小为DAYS的一维数组a[DAYS]，a[0],a[1]...a[DAYS-1]分别存放当天的桃子数，其中a[n] = 2*(a[n-1] + 1)。