问题描述

某天一只猴子摘了一堆桃子，具体多少它没有数。猴子每天吃了其中的一半然后再多吃了一个,第二天则吃剩余的一半然后再多吃一个，……，直到第 10 天，猴子发现只有 1 个桃子了。问这只猴子在第一天摘了多少个桃子？

问题分析

这是一道简单的递归经典问题。

这只猴子共用了 10 天吃桃子，只知道最后一天剩余 1 个桃子，要想求出第1 天剩余的桃子数，就先要求出第 2 天剩余的桃子数，……。假设 $a_n$ 表示第 $n$ 天剩余的桃子数量，n = 1~10 ,则有如下关系：
$ a_1=(a_2+1)*2 $
$ a_2=(a_3+1)*2 $
$ a_3=(a_4+1)*2 $
$ a_4=(a_5+1)*2 $
$ \cdots $
$ a_9=(a_{10}+1)*2 $
$ a_{10}=1 $

从上述的式子可知，只能通过倒推来求得第一天的桃子数，这在程序上需要借助递归算法。为了通用性的方便，可以编写一个算法，来计算猴子吃桃问题。算法的示例代码如下：

int peach(int n)
{
    //猴子吃桃算法
    int pe;
    if(n==l)
    {
        return 1;
    }
    else
    {
        pe=(peach(n-1)+1)*2;
    }
    return pe;
}

代码示例

#include <iostream>
#include <stdio.h>
using namespace std;

int peach(int n)
{
    //猴子吃桃算法
    int pe;
    if(n==1)
    {
        return 1;
    }
    else
    {
        pe=(peach(n-1)+1)*2;
    }
    return pe;
}

int main()
{
    int n;
    int peachnum;
    cout<<"猴子吃桃问题求解！"<<'\n'<<"输入天数：";
    cin>>n;
    peachnum = peach(n);
    cout<<"最初的桃子个数为："<<peachnum<<"个！"<<endl;
    return 0;
}