題目
猴子吃桃問(wèn)題。猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了一個(gè)。第2天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想再吃時(shí)，就只剩下愛(ài)一個(gè)桃子了。求第1天共摘了多少桃子
數(shù)學(xué)思路及數(shù)學(xué)解法
本題的關(guān)鍵就是如何理解“到第10天早上想再吃時(shí)”，這里的第10天早上想再吃時(shí)剩下的是第9天吃剩下的，然后根據(jù)題目要求，設(shè)第
n
?
1
n-1
n?1天沒(méi)吃之前還剩下
H
(
n
?
1
)
H(n-1)
H(n?1)個(gè)桃子，則第
n
?
1
n-1
n?1天猴子吃了
H
(
n
?
1
)
2
+
1
\frac{H\left ( n-1 \right ) }{2} + 1
2H(n?1)?+1個(gè)桃子，則第
n
?
1
n-1
n?1天猴子吃過(guò)后剩下的桃子個(gè)數(shù)為
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天吃了桃子后剩下的桃子個(gè)數(shù)即為第
n
n
n天沒(méi)吃之前還剩下桃子的個(gè)數(shù)，所以有如下遞推關(guā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天吃過(guò)后剩下的桃子個(gè)數(shù)，也就是說(shuō)，若求第一天摘了多少，相當(dāng)于求
H
(
0
)
H(0)
H(0)，第0天實(shí)際上是不存在，但是根據(jù)這個(gè)數(shù)列的定義可以發(fā)現(xiàn)，第1天摘了多少桃子相當(dāng)于第0天吃過(guò)后還剩多少桃子）
但是這個(gè)題目沒(méi)有以直接的方式給這個(gè)遞推方程（差分方程）的初值條件，只給了第10天早上想吃之前還剩1個(gè)桃子（第9天吃過(guò)后剩下了1個(gè)桃子）這個(gè)條件，我們只能從第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個(gè)桃子（第9天吃過(guò)后剩下了1個(gè)桃子）
所以
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，這是一個(gè)一階線性非齊次差分方程，它的特征方程為
λ
?
1
2
=
0
\lambda -\frac{1}{2} =0
λ?21?=0即
λ
=
1
2
\lambda =\frac{1}{2}
λ=21?
則設(shè)改方程對(duì)應(yīng)的齊次方程的通解為
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
聯(lián)立上述兩個(gè)方程解得
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個(gè)桃子
這是利用差分方程理論的數(shù)學(xué)解法，計(jì)算機(jī)可以利用遞推關(guān)系進(jìn)行循環(huán)得到結(jié)果，循環(huán)結(jié)束的條件是天數(shù)小于0,（也就是說(shuō)我們要求到第0天即
H
(
0
)
H(0)
H(0)），P.S循環(huán)的時(shí)間復(fù)雜度不如直接將數(shù)列通項(xiàng)公式直接帶入好，但是在這里為了體現(xiàn)編程的思想我還是給出循環(huán)的C語(yǔ)言代碼實(shí)現(xiàn)，但是通項(xiàng)公式法需要編程人員掌握大學(xué)微積分（高等數(shù)學(xué)）。
代碼（循環(huán)法）
#include <stdio.h>
//到第m天吃過(guò)后還剩下n個(gè)桃子
void func(int m,int n)
{
int temp = m;//用于記錄天數(shù)m的變量，在下文中會(huì)將其作為循環(huán)的迭代器
int x1 = 0;//記錄H(n-1)
int x2 = n;//記錄H(n)
if (m == 0 || n == 0)
{
printf("天數(shù)和桃子數(shù)不符合規(guī)定！\n");
}
//循環(huán)，一直到天數(shù)小于等于0時(shí)退出
while (temp > 0)
{
//求出當(dāng)前天的前一天還剩多少桃子即H(n-1)
x1 = 2 * (x2 + 1);
//讓x2變成x1，即天數(shù)向前串一位；
x2 = x1;
//循環(huán)一次，相當(dāng)于從后往前循環(huán)一天，所以要減少一天
temp--;
}
printf("第1天一共吃了%d個(gè)桃子\n", x2);
}
int main()
{
//題干要求是第10天早上想吃的時(shí)候只剩1個(gè)，說(shuō)明第10天還沒(méi)吃，剩下的一個(gè)是第9天吃剩下的，所以m=9
func(9, 1);
}
循環(huán)法的時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-450128.html
代碼（通項(xiàng)公式法）
#include <stdio.h>
#include<math.h>
//通項(xiàng)公式法
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個(gè)桃子\n", H(0));
}
通項(xiàng)公式法的時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，而循環(huán)法的時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)，高下立判了家人們，論學(xué)好數(shù)學(xué)的重要性，學(xué)好數(shù)學(xué)能減少多少算法運(yùn)行的時(shí)間?。?span toymoban-style="hidden">文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-450128.html
到了這里，關(guān)于【C語(yǔ)言】猴子吃桃問(wèn)題。猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了一個(gè)。第2天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想……的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
