数据结构-猴子吃桃问题

一、需求分析

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

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

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

3)采用递归实现上述求解；

二、概要设计

1.设计思路

C是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。

2.设计方案

如果用数组结构解决这个问题，把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*2e(i-1)-2 (i>=2)。

如果用链结构解决这个问题，建立一个链表，根据每天桃子数与后一天桃子数的关系n=2*n+2,依次将每天的桃子数存进链表中，最后输出第一天的桃子数。

如果用递归结构解决这个问题，要求利用他们每天都吃当前桃子的一半且再多吃一个这一特点，设计一个递归算法。

三、调用关系与算法流程分析

数组

把猴子吃桃的天数倒过来看的话，以天数作为数组的下标i，剩下桃子的个数a[i]的递推公式为a[i]=(a[i-1]+1)*2。a[i]实际代表了倒数第i天剩下的桃子数。所以可以求得此数组的通项公式为a[i]=3*pow（2，(i-1)）-2 (i>=2)。

关键代码：

nt day,tao[11];  //定义数组和下标
tao[0]=0;         //tao[0]赋值为0
tao[1]=1;         //倒数第一天的桃子数为1
for(day=2;day<=10;day++)
tao[day]=3*pow(2,day-1)-2;  //给数组的赋值
printf("最初的桃子数为%d\n",tao[10]);//输出最初的桃子数

链结构

用链结构实现这个算法，其核心是利用链表这种存储结构，将每天的桃子数存储在链表中，在链表中实现数的递推。首先是建立一个空链表，产生一个头结点，且将头结点的地址赋给L。然后把每天的桃子数从链表的第一个结点插入链表。最后第一天的桃子数被最后一个插入链表，成为链表中第一个值，将其赋给e，最后只要输出e即得到第一天的桃子数。

建立单链表的程序代码如下：

void InitList(LinkList &L)//构造一个空链链表
{ 
L=(LinkList)malloc(sizeof(LNode));//产生头结点,并使L指向此头结点
if(!L) exit(OVERFLOW);
    L->next=NULL;
}

递归

设计递归算法，利用x=2*x+2，定义一个函数sum_fan，然后不断调用自身，求得第一天的桃子数。

四、程序代码（c语言）

# include<stdio.h>
# include<math.h>
void main()
{
int day,tao[11];  
tao[0]=0;         
tao[1]=1;         
for(day=2;day<=10;day++)
tao[day]=3*pow(2,day-1)-2;  
printf("最初的桃子数为%d\n",tao[10]);//输出最初的桃子数
}

#include"iostream"
#include"stdlib.h"
#include"stdio.h"
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW 0
#define OK 1
#define NULL 0
typedef int Status;
typedef int ElemType;
struct LNode
{ 
ElemType data;
LNode *next;
};
typedef LNode *LinkList;
void InitList(LinkList &L)
{ 
L=(LinkList)malloc(sizeof(LNode));
if(!L) exit(OVERFLOW);
    L->next=NULL;
}
Status GetElem(LinkList L,int i,ElemType &e)
{ 
int j=1;
LinkList p=L->next;
while(p&&j<i)
{ 
j++;
p=p->next;
}
if(!p||j>i)
return ERROR;
     e=p->data;
 return OK;
}
Status ListInsert(LinkList L,int i,ElemType e)
{ 
int j=0;
LinkList s,p=L;
while(p&&j<i-1)
{
j++;
        p=p->next;
}
if(!p||j>i-1) return 0;
s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
s->next=p->next;
    p->next=s;
    return 1;
}
void main()
{ 
LinkList L;
int i,e,n;
InitList(L);
for(i=1,n=1;i<=10;i++)
       {
n=2*n+2;
ListInsert(L,1,n);
}
Status GetElem(L,1,e);
printf("%d",e);
}
include<stdio.h>
int sum_fan(int n,int i)    
{
    if (i>0)
    {
        n = sum_fan((n+1)*2,--i);    
    }
return n;               
}
void main()
{
    int sum;
int day = 9;            
    int x = 1;             
sum = sum_fan(x,day);    
    printf("%d",sum);      
}