用递归语句来写猴子吃桃问题

Question

猴子吃桃问题。猴子第1天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了个。第2天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,就只剩一个桃子了。求第1天共摘多少个桃子。

Answer 1

一、分析

第一天是 a1 个桃子，吃一半多一个，那么剩下就是 a2 = a1 - ( a1/2 + 1 )；
第二天是 a2 个桃子，吃一半多一个，那么剩下就是 a3 = a2 - ( a2/2 + 1 )；
...
第十天是 a10 个桃子，即 1 个桃子；

所以，你就会发现 a10 = a9 - (a9/2 + 1) = 1，我们反过来， a9 = 2a10 + 2，同理：
a8 = 2a9 + 2
a7 = 2a8 + 2
...
a1 = 2a2 + 2

二、递归代码如下

#include <stdio.h>

int a(int n) {
    if(n == 10) {
        return 1;
    }
    return 2 * a(n+1) + 2;
}

int main() {
    printf("%d\n", a(1));
    return 0;
} 

三、输出

1534