2013
12-26

# 蟠桃记

2
4

4
22

<span style="font-size:18px;">for (s = n = 1; n &amp;lt; 30; n++)s = (s + 1) * 2;</span>

<span style="font-size:18px;"><br /></span>

<span style="font-size:18px;"><br /></span>

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(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

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


#include <math.h>
#include <stdio.h>

int main(void)
{
int n;

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

return 0;
}