问题描述

Problem Description

喜欢西游记的同学肯定都知道悟空偷吃蟠桃的故事，你们一定都觉得这猴子太闹腾了，其实你们是有所不知：悟空是在研究一个数学问题！

什么问题？他研究的问题是蟠桃一共有多少个！

不过，到最后，他还是没能解决这个难题，呵呵^-^

当时的情况是这样的：

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

Input

输入数据有多组，每组占一行，包含一个正整数n（1<n<30），表示只剩下一个桃子的时候是在第n天发生的。

Output

对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。

Sample Input

2
4

Sample Output

4
22

问题分析

Problem Analyse

本题是为C语言初学者提供的。

Algorithm Analyse

本题可以直接用循环迭代过关。但是，如果你对算法有兴趣，你想知道另一种更神奇的算法吗？^_^

算法实现

迭代的方法很简单，直接按题目意思来就可以了。

for (s = n = 1; n < 30; n++)
s = (s + 1) * 2;

计算机的鼻祖本来就是数学家，自然优化程序的最终方法还是要回归到数学上。本题很容易得到它的递推方程:

f(1) = 1;
f(n) = [f(n-1) + 1] × 2;

于是我们得到:

f(n) + 2 = 2 × [f(n-1) + 2]
f(1) + 2 = 3

=>

f(n) + 2 = 3 × 2n-1

=>

f(n) = 3 × 2n-1 - 2

对于这种推断题还有另外一种递推方法，虽然对于本题来说很麻烦。但有时候它是无可替代的。

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

=>

f(n) + f(n-1) + 4 = 2 × [f(n-1) + f(n+2) + 4];

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

则 g(n) = 2 × g(n-1);
   g(2) = f(2) + f(1) + 4 = 9;

∴ g(n) = 9 × 2n-2  (n > 1)

∴ f(n)   + f(n-1) = 9 × 2n-2 - 4 ①
  f(n-1) + f(n-2) = 9 × 2n-3 - 4 ②
  ┋
  f(3)   + f(2)   = 9 × 2 - 4
  f(2)   + f(1)   = 9 - 4

把①式减去②式得
  f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)

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

1. n为奇数

  f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)
  ┋
  f(5)   = 9 × 22 + f(3)
  f(3)   = 9 + f(1)
  f(1)   = 1

从下往上迭代，得:
  f(n) = 9 × (2n-3 + 2n-5 + ... + 22 + 1) + 1
=>
  f(n) = 9 × (1 - 4(n-1)/2) ÷ (1 - 4) + 1
=>
  f(n) = 3 × 2n - 1 - 2

1. n为偶数

  f(n)   = 9 × 2n-3 + f(n-2)
  f(n-2) = 9 × 2n-5 + f(n-4)
  ┋
  f(4)   = 9 × 21 + f(2)
  f(2)   = 4

从下往上迭代，得:
  f(n) = 9 × (2n-3 + 2n-5 + ... + 21) + 4
=>
  f(n) = 9 × 2 × (1 - 4(n-2)/2) ÷ (1 - 4) + 4
=>
  f(n) = 3 × 2n - 1 - 2

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

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

参考源码