题目
猴子吃桃问题。猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，就只剩下爱一个桃子了。求第1天共摘了多少桃子
数学思路及数学解法
本题的关键就是如何理解“到第10天早上想再吃时”，这里的第10天早上想再吃时剩下的是第9天吃剩下的，然后根据题目要求，设第
n
−
1
n-1
n−1天没吃之前还剩下
H
(
n
−
1
)
H(n-1)
H(n−1)个桃子，则第
n
−
1
n-1
n−1天猴子吃了
H
(
n
−
1
)
2
+
1
\frac{H\left ( n-1 \right ) }{2} + 1
2H(n−1)+1个桃子，则第
n
−
1
n-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-1
n−1天吃了桃子后剩下的桃子个数即为第
n
n
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
)
H(n)
H(n)指的是第n天吃过后剩下的桃子个数，也就是说，若求第一天摘了多少，相当于求
H
(
0
)
H(0)
H(0)，第0天实际上是不存在，但是根据这个数列的定义可以发现，第1天摘了多少桃子相当于第0天吃过后还剩多少桃子）
但是这个题目没有以直接的方式给这个递推方程（差分方程）的初值条件，只给了第10天早上想吃之前还剩1个桃子（第9天吃过后剩下了1个桃子）这个条件，我们只能从第10天反向遍历到第1天，将递推方程恒等变形得：
H
(
n
−
1
)
=
2
[
H
(
n
)
+
1
]
H(n-1)=2\left [ H(n)+1 \right ]
H(n−1)=2[H(n)+1]
由于第10天早上想吃之前还剩1个桃子（第9天吃过后剩下了1个桃子）
所以
H
(
9
)
=
1
H(9)=1
H(9)=1，则
H
(
8
)
=
2
[
H
(
9
)
+
1
]
=
2
(
1
+
1
)
=
4
H(8)=2\left [ H(9)+1 \right ] =2(1+1)=4
H(8)=2[H(9)+1]=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(9)=1
H(9)=1，
H
(
8
)
=
4
H(8)=4
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
A=-2
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
H(0)=1534
H(0)=1534个桃子
这是利用差分方程理论的数学解法，计算机可以利用递推关系进行循环得到结果，循环结束的条件是天数小于0,（也就是说我们要求到第0天即
H
(
0
)
H(0)
H(0)），P.S循环的时间复杂度不如直接将数列通项公式直接带入好，但是在这里为了体现编程的思想我还是给出循环的C语言代码实现，但是通项公式法需要编程人员掌握大学微积分（高等数学）。
代码（循环法）
#include <stdio.h>
//到第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 ) O(n) O(n)文章来源：https://www.toymoban.com/news/detail-450128.html
代码（通项公式法）
#include <stdio.h>
#include<math.h>
//通项公式法
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(1) O(1)，而循环法的时间复杂度为 O ( n ) O(n) O(n)，高下立判了家人们，论学好数学的重要性，学好数学能减少多少算法运行的时间啊！文章来源地址https://www.toymoban.com/news/detail-450128.html
到了这里，关于【C语言】猴子吃桃问题。猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想……的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
