本文共 2093 字，大约阅读时间需要 6 分钟。

[程序代码]

#include
   
    /* 函数原型 */unsigned long f(unsigned int n);/* */int main(){    int n;    printf("Input days n:");    scanf("%d", &n);    if(n >= 1)    {        printf("x=%d\n", f(n));    }    else    {        /* 数据非法 */        printf("data error!\n");    }    /* */    return 0;}/* 猴子吃桃 */unsigned long f(unsigned int n){    if(n == 1)    {        /* 递归终止条件 */        return 1;    }    else    {        /* 递归一般条件 */        return 2 * f(n - 1) + 2;    }}/* 分析 *//* 猴子在第n天吃桃时, 吃掉了当前的一半桃子, 还没吃够, 便又吃了一个桃子,方才罢休 *//* 由此关系可得第n天和第n-1天桃子数量的递推公式 *//* P(n-1)=P(n)-1/2*P(n)-1, p(n)为第n天的桃子数量, P(n-1)为第n-1天桃子的数量, 数量观测时间选在每天猴子即将吃桃子前 *//* P(n)=2*P(n-1)+2 */
   

[运行结果]

       另外也可以用非递归的方式解决该问题.

[程序代码(迭代)] 

#include
   
    /* 函数原型 */unsigned long f(unsigned int n);/* */int main(){    int n;    printf("Input days n:");    scanf("%d", &n);    if(n >= 1)    {        printf("x=%d\n", f(n));    }    else    {        /* 数据非法 */        printf("data error!\n");    }    /* */    return 0;}/* 猴子吃桃 */unsigned long f(unsigned int n){    unsigned long p = 1;    /* 第一次迭代计算后的桃子数量对应第2天的桃子数量 */    unsigned int i = 2;    while(i <= n)    {        /* p = 第i天吃桃子前的桃子数量 */        p = 2 * p + 2;        i ++;    }    return p;}/* 分析 *//* 猴子在第n天吃桃时, 吃掉了当前的一半桃子, 还没吃够, 便又吃了一个桃子,方才罢休 *//* 由此关系可得第n天和第n-1天桃子数量的递推公式 *//* P(n-1)=P(n)-1/2*P(n)-1, p(n)为第n天的桃子数量, P(n-1)为第n-1天桃子的数量, 数量观测时间选在每天猴子即将吃桃子前 */
   

[运行结果]

       最后我们再以尾递归思想实现该问题的求解.

[程序代码(尾递归)] 

#include
   
    /* 函数原型 */unsigned long f(unsigned int n, unsigned long p);/* */int main(){    int n;    printf("Input days n:");    scanf("%d", &n);    if(n >= 1)    {        printf("x=%d\n", f(n, 1));    }    else    {        /* 数据非法 */        printf("data error!\n");    }    /* */    return 0;}/* 猴子吃桃 */unsigned long f(unsigned int n, unsigned long p){    if(n == 1)    {        /* 递归的终止条件 */        return p;    }    else    {        /* 递归的一般条件 */        p = 2 * p + 2;        return f(n - 1, p);    }}/* 分析 *//* 猴子在第n天吃桃时, 吃掉了当前的一半桃子, 还没吃够, 便又吃了一个桃子,方才罢休 *//* 由此关系可得第n天和第n-1天桃子数量的递推公式 *//* P(n-1)=P(n)-1/2*P(n)-1, p(n)为第n天的桃子数量, P(n-1)为第n-1天桃子的数量, 数量观测时间选在每天猴子即将吃桃子前 */
   

[运行结果]