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)
┋
这时候，我们需要分类讨论了:
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
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 × 2n - 1 - 2
#include#include int main(void) { int n; while (scanf("%d", &n) != EOF) printf("%.0f\n", 3 * pow(2, n - 1) - 2); return 0; }