题目

来源：http://acm.hdu.edu.cn/showproblem.php?pid=2013

第一天悟空吃掉桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。聪明的你，请帮悟空算一下，他第一天开始吃的时候桃子一共有多少个呢？

常规解法

while (scanf("%d", &n) != EOF){
    int r = 1;
    for (int i = 2; i <= n; i++)
        r = (r + 1) * 2;
    printf("%d\n", r);
}

高端写法

while (scanf("%d", &n) != EOF)
    printf("%.0f\n", 3 * pow(2, n - 1) - 2);

从数学的角度思考这个题

本题很容易得到它的递推方程

$ f(1) = 1 $

$ f(n) = [f(n-1) + 1] \times 2 $

于是我们得到 $ f(n) + 2 = 2 \times [f(n-1) + 2] $

由于 $ f(1) + 2 = 3 $，

推导得 $ f(n) + 2 = 3 \times 2^{n-1} $

进一步整理得 $ f(n) = 3 \times 2^{n-1} - 2 $

另一种方法

$f(1) = 1$
$f(n) = 2f(n-1) + 2 = f(n-1) + 2f(n-2) + 4$

$\Rightarrow f(n) + f(n-1) + 4 = 2 \times [f(n-1) + f(n-2) + 4]$

设 $g(n) = f(n) + f(n-1) + 4$

则 $g(n) = 2 \times g(n-1)$
$g(2) = f(2) + f(1) + 4 = 9$

$\therefore g(n) = 9 \times 2^{n-2} \quad (n > 1)$

$\therefore f(n) + f(n-1) = 9 \times 2^{n-2} - 4 \quad ①$
$f(n-1) + f(n-2) = 9 \times 2^{n-3} - 4 \quad ②$
$\vdots$
$f(3) + f(2) = 9 \times 2 - 4$
$f(2) + f(1) = 9 - 4$

把①式减去②式得
$f(n) = 9 \times 2^{n-3} + f(n-2)$
$f(n-2) = 9 \times 2^{n-5} + f(n-4)$
$\vdots$

这时候，我们需要分类讨论了。

当 n 为奇数时

$f(n) = 9 \times 2^{n-3} + f(n-2)$
$f(n-2) = 9 \times 2^{n-5} + f(n-4)$
$\vdots$
$f(5) = 9 \times 2^2 + f(3)$
$f(3) = 9 + f(1)$
$f(1) = 1$

从下往上迭代，得:

$f(n) = 9 \times (2^{n-3} + 2^{n-5} + \ldots + 2^2 + 1) + 1$
$\Rightarrow f(n) = 9 \times \frac{1 - 4^{(n-1)/2}}{1 - 4} + 1$
$\Rightarrow f(n) = 3 \times 2^{n - 1} - 2$

当 n 为偶数

$f(n) = 9 \times 2^{n-3} + f(n-2)$
$f(n-2) = 9 \times 2^{n-5} + f(n-4)$
$\vdots$
$f(4) = 9 \times 2^1 + f(2)$
$f(2) = 4$

从下往上迭代，得:

$f(n) = 9 \times (2^{n-3} + 2^{n-5} + \ldots + 2^1) + 4$
$\Rightarrow f(n) = 9 \times 2 \times \frac{1 - 4^{(n-2)/2}}{1 - 4} + 4$
$\Rightarrow f(n) = 3 \times 2^{n - 1} - 2$

世上的事往往如此，巧合的事情经常发生。不得不感叹大自然的美妙~

现在我们就得到了这道题目的公式了 $f(n) = 3 \times 2^{n - 1} - 2$