题目

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

数学思路及数学解法

本题的关键就是如何理解“到第10天早上想再吃时”，这里的第10天早上想再吃时剩下的是第9天吃剩下的，然后根据题目要求，设第$n-1$天没吃之前还剩下$H(n-1)$个桃子，则第$n-1$天猴子吃了 H ( n − 1 ) 2 + 1 \frac{H\left ( n-1 \right ) }{2} + 1 2H(n−1)​+1个桃子，则第$n-1$天猴子吃过后剩下的桃子个数为
H ( n − 1 ) − [ H ( n − 1 ) 2 + 1 ] = H ( n − 1 ) 2 − 1 H(n-1)-\left [ \frac{H\left ( n-1 \right ) }{2} + 1 \right ]=\frac{H\left ( n-1 \right ) }{2} – 1 H(n−1)−[2H(n−1)​+1]=2H(n−1)​−1
第$n-1$天吃了桃子后剩下的桃子个数即为第$n$天没吃之前还剩下桃子的个数，所以有如下递推关系 H ( n ) = H ( n − 1 ) 2 − 1 H(n)=\frac{H\left ( n-1 \right ) }{2} – 1 H(n)=2H(n−1)​−1
（这里的$H(n)$指的是第n天吃过后剩下的桃子个数，也就是说，若求第一天摘了多少，相当于求$H(0)$，第0天实际上是不存在，但是根据这个数列的定义可以发现，第1天摘了多少桃子相当于第0天吃过后还剩多少桃子）
但是这个题目没有以直接的方式给这个递推方程（差分方程）的初值条件，只给了第10天早上想吃之前还剩1个桃子（第9天吃过后剩下了1个桃子）这个条件，我们只能从第10天反向遍历到第1天，将递推方程恒等变形得：
$H(n-1)=2\left[H(n)+1\right]$
由于第10天早上想吃之前还剩1个桃子（第9天吃过后剩下了1个桃子）
所以$H(9)=1$，则$H(8)=2\left[H(9)+1\right]=2(1+1)=4$
这样我们就拿到了初值条件和差分方程
由于 H ( n ) = H ( n − 1 ) 2 − 1 H(n)=\frac{H\left ( n-1 \right ) }{2} – 1 H(n)=2H(n−1)​−1
则 H ( n ) − H ( n − 1 ) 2 = − 1 H(n)-\frac{H\left ( n-1 \right ) }{2} =- 1 H(n)−2H(n−1)​=−1，这是一个一阶线性非齐次差分方程，它的特征方程为 λ − 1 2 = 0 \lambda -\frac{1}{2} =0 λ−21​=0即 λ = 1 2 \lambda =\frac{1}{2} λ=21​
则设改方程对应的齐次方程的通解为 H C ( n ) = C ⋅ ( 1 2 ) n H_{C} (n)=C\cdot \left ( \frac{1}{2} \right ) ^{n} HC​(n)=C⋅(21​)n
则非齐次方程的特解为 H ∗ ( n ) = A H_{*}(n)=A H∗​(n)=A
则 H ( n ) = C ⋅ ( 1 2 ) n + A H(n)=C\cdot \left ( \frac{1}{2} \right ) ^{n}+A H(n)=C⋅(21​)n+A
由于$H(9)=1$，$H(8)=4$则有
H ( 8 ) = C ⋅ ( 1 2 ) 8 + A = 4 H(8)=C\cdot \left ( \frac{1}{2} \right )^{8}+A=4 H(8)=C⋅(21​)8+A=4
H ( 9 ) = C ⋅ ( 1 2 ) 9 + A = 1 H(9)=C\cdot \left ( \frac{1}{2} \right )^{9}+A=1 H(9)=C⋅(21​)9+A=1
联立上述两个方程解得 C = 3 ⋅ 2 9 C=3\cdot 2^{9} C=3⋅29,$A=-2$
故差分方程的通解为 H ( n ) = 3 ⋅ 2 9 ⋅ ( 1 2 ) n − 2 H(n)=3\cdot 2^{9}\cdot \left ( \frac{1}{2} \right ) ^{n}-2 H(n)=3⋅29⋅(21​)n−2
故第一天摘了$H(0)=1534$个桃子
这是利用差分方程理论的数学解法，计算机可以利用递推关系进行循环得到结果，循环结束的条件是天数小于0,（也就是说我们要求到第0天即$H(0)$），P.S循环的时间复杂度不如直接将数列通项公式直接带入好，但是在这里为了体现编程的思想我还是给出循环的C语言代码实现，但是通项公式法需要编程人员掌握大学微积分（高等数学）。

代码（循环法）

#include //到第m天吃过后还剩下n个桃子void func(int m,int n){    int temp = m;//用于记录天数m的变量，在下文中会将其作为循环的迭代器    int x1 = 0;//记录H(n-1)    int x2 = n;//记录H(n)    if (m == 0 || n == 0)    {        printf("天数和桃子数不符合规定！\n");    }    //循环，一直到天数小于等于0时退出    while (temp > 0)    {        //求出当前天的前一天还剩多少桃子即H(n-1)        x1 = 2 * (x2 + 1);        //让x2变成x1，即天数向前串一位；        x2 = x1;        //循环一次，相当于从后往前循环一天，所以要减少一天        temp--;    }    printf("第1天一共吃了%d个桃子\n", x2);}int main(){    //题干要求是第10天早上想吃的时候只剩1个，说明第10天还没吃，剩下的一个是第9天吃剩下的，所以m=9    func(9, 1);}

循环法的时间复杂度为$O(n)$

代码（通项公式法）

#include #include//通项公式法long double H(int n){    return 3.0 * pow(2, 9) * pow(0.5, (long double)n) - 2.0;}int main(){    printf("第1天一共吃了%1.0f个桃子\n", H(0));}

通项公式法的时间复杂度为$O(1)$，而循环法的时间复杂度为$O(n)$，高下立判了家人们，论学好数学的重要性，学好数学能减少多少算法运行的时间啊！