问题描述

某天一只猴子摘了一堆桃子,具体多少它没有数。猴子每天吃了其中的一半然后再多吃了一个,第二天则吃剩余的一半然后再多吃一个,……,直到第 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;
}
最后修改:2021 年 03 月 31 日
赠人玫瑰,手有余香。您的赞赏是对我最大的支持!