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

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

猴子吃桃子问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。二、运行环境（软、硬件环境）VC++6.0PC电脑一台算法的需求分析1)

采用数组数据结构实现上述求解2)

采用链数据结构实现上述求解3)

采用递归实现上述求解4)

如果采用4种方法者,适当加分//用户界面intDesk(intn){ 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); } returnn;}四、算法概要设计//采用链数据结构(栈)实现上述求解typedefstruct{ int*top; int*base;}stack;//初始化一个栈stackInit(stack*s)猴子吃桃问题大数据结构课程设计全文共12页，当前为第1页。猴子吃桃问题大数据结构课程设计全文共12页，当前为第1页。 s->base=(int*)malloc(STACK_SIZE*sizeof(int)); if(s->base==NULL) { printf("Initfailed!\n"); exit(-1); } s->top=s->base; return*s;}//二叉树创建一个大小为DAYS(由用给出)的二叉树,二叉树的左孩子节点存放当天的桃子数，右节点存放数字1，即为多吃的一个桃子。typedefstructTNode{ intdata; structTNode*lchild; structTNode*rchild;}tree;//创建一个二叉树treeCreatTree(tree*T)//T为指针类型{ intn=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的地址}猴子吃桃问题大数据结构课程设计全文共猴子吃桃问题大数据结构课程设计全文共12页，当前为第2页。//算法框架图打印共摘的桃子数量打印共摘的桃子数量判断是否执行完毕进入猴子吃桃子系统界面开始选择要使用的方法进入该函数判断是否执行完毕继续执行N Y NY猴子吃桃问题大数据结构课程设计全文共12页，当前为第3页。猴子吃桃问题大数据结构课程设计全文共12页，当前为第3页。算法详细设计#include<stdio.h>#include<stdlib.h>#include"peach.h"//函数声明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){ intdata=0; intn=1,i=1; stacks; treeT; s=Init(&s); T=CreatTree(&T); while(1) { switch(Desk(n)) { case1: peach_1(); break; case2: peach_2(&s); break; case3: peach_3(n,i); break; case4: peach_4(&T); break; case5: exit(0); break; } } return0;}//头文件代码猴子吃桃问题大数据结构课程设计全文共12页，当前为第4页。#defineDAYS10//定义给定的天数猴子吃桃问题大数据结构课程设计全文共12页，当前为第4页。#defineSTACK_SIZE5//栈的容量,实际只用了一个#defineTRUE1#defineERROR0voidpeach_3(intn,inti);//用户界面intDesk(intn){ 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); } returnn;}//采用数组数据结构实现上述求解voidpeach_1(void){ intpeach[50]={0}; inti=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");}//采用链数据结构实现上述求解typedefstruct{ int*top; int*base;}stack;//初始化一个栈stackInit(stack*s)猴子吃桃问题大数据结构课程设计全文共12页，当前为第5页。{猴子吃桃问题大数据结构课程设计全文共12页，当前为第5页。 s->base=(int*)malloc(STACK_SIZE*sizeof(int)); if(s->base==NULL) { printf("Initfailed!\n"); exit(-1); } s->top=s->base; return*s;}//把当天的桃子数进栈voidPush(stack*s,intnum){ *s->top++=2*(num+1);}//把前一天的桃子数出栈voidPop(stack*s,int&num)//&num位地址传递，可以直接对参数进行修改{ num=*--s->top;}voidpeach_2(stack*s){ inti=0; intnum=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");}voidpeach_3(intn,inti){ if(i==DAYS)//DAYS为递归终止条件由用户给出 { printf("*********************\n"); printf("*递归法*\n"); printf("*这群猴子共摘了%d个桃子*\n",n); printf("*********************\n"); } else {猴子吃桃问题大数据结构课程设计全文共12页，当前为第6页。 n=2*(n+1);猴子吃桃问题大数据结构课程设计全文共12页，当前为第6页。 peach_3(n,i+1); }}//二叉树typedefstructTNode{ intdata; structTNode*lchild; structTNode*rchild;}tree;treeCreatTree(tree*T)//T为指针类型{ intn=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的地址}//对二叉树进行赋值计算voidcalculate(tree*T){ inti=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;猴子吃桃问题大数据结构课程设计全文共12页，当前为第7页。 }猴子吃桃问题大数据结构课程设计全文共12页，当前为第7页。}//二叉树遍历最左下角的孩子节点voidpeach_4(tree*T){ calculate(T); while(T->lchild!=NULL) { T=T->lchild; } printf("*********************\n"); printf("*二叉树法*\n"); printf("*这群猴子共摘了%d个桃子*\n",T->data); printf("*********************\n");}六、算法的测试开始函数功能：开始函数功能：1-数组法2-链表法3-递归法4-二叉树法5-退出选择一个功能执行该功能#include<stdio.h>#include<stdlib.h>#include"peach.h"//函数声明intDesk(intn);voidpeach_1(void);stackInit(stack*s);voidPush(stack*s,intnum);voidPop(stack*s,int&num);voidpeach_2(stack*s);voidpeach_3(intn,inti);treeCreatTree(tree*T);voidcalculate(tree*T);voidpeach_4(tree*T);intmain(){intdata=0;intn=1,i=1;stacks;treeT;s=Init(&s);T=CreatTree(&T);while(1){ switch(Desk(n)){case1: 猴子吃桃问题大数据结构课程设计全文共12页，当前为第8页。peach_1();猴子吃桃问题大数据结构课程设计全文共12页，当前为第8页。break;case2: peach_2(&s);break;case3:peach_3(n,i);break;case4:peach_4(&T);break;case5: exit(0);break;}}return0;}//采用数组数据结构实现上述求解voidpeach_1(void){intpeach[50]={0};inti=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");}猴子吃桃问题大数据结构课程设计全文共12页，当前为第9页。猴子吃桃问题大数据结构课程设计全文共12页，当前为第9页。voidpeach_2(stack*s){inti=0;intnum=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");}voidpeach_3(intn,inti){if(i==DAYS)//DAYS为递归终止条件由用户给出{printf("*********************\n");printf("*递归法*\n");猴子吃桃问题大数据结构课程设计全文共12页，当前为第10页。printf("*这群猴子共摘了%d个桃子*\n",n);猴子吃桃问题大数据结构课程设计全文共12页，当前为第10页。printf("*********************\n");}else{n=2*(n+1);peach_3(n,i+1);//循环体 }}//二叉树遍历最左下角的孩子节点voidpeach_4(tree*T){calculate(T);while(T->lchild!=NULL){T=T->lchild;}printf("*********************\n");printf("*二叉树法*\n");printf("*这群猴子共摘了%d个桃子*\n",T->data);printf("******************