Question

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

猴子吃桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求：1)采用数组数据结构实现上述求解2)采用链数据结构实现上述求解3)采用递归实现上述求解（有源代码 在VC6.0环境下运行）

Answer 1

//数组解法
#include<stdio.h>
void main()
{
int i,tao[10];
tao[9]=1;//tao[9]代表第10天剩的桃子数
for(i=8;i>=0;i--){
tao[i]=2*(tao[i+1]+1);
}
printf("共摘了%d个桃子！\n",tao[0]);
}
//递归实现
#include<stdio.h>
int tao(int n)
{
if(n==10) return 1;
return 2*(tao(n+1)+1);
}
void main()
{
int sum=0;
sum+=tao(1);
printf("共摘了%d个桃子！\n",sum);
}
至于用数据结构实现，可以采用栈，如下：
#include<stdio.h>
#include<stdlib.h>
//栈的结构定义
typedef struct{
int *base;
int *top;
}Stack;
//初始化栈
void InitStack(Stack &s)
{
s.base=(int *)malloc(sizeof(int));
if(s.base) s.top=s.base;
else{
printf("空间分配错误！\n");
exit(0);
}
}
//入栈
void PushStack(Stack &s,int data)
{
*s.top++=data;
}
//出栈
int PopStack(Stack &s)
{
return *(--s.top);
}
void main()
{
int i=10,data;
Stack s;
InitStack(s);
PushStack(s,1);//先将第10天的桃子数1入栈
while(i-->1){
data=PopStack(s);//出栈一个元素保存在data中
PushStack(s,2*(data+1));//再将2*(data+1)入栈
}
//最后栈中剩余的那个元素就是第1天摘的桃子数
printf("共摘了%d个桃子！\n",PopStack(s));
}