Problem Description
In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.
Input
Input
consists of several test cases followed by a line containing -1. Each
test case is a line containing an integer 0 ≤ n ≤ 30.
Output
For each test case, output one integer number giving the number of possible tilings.
Sample Input
2
8
12
-1
Sample Output
3
153
2131
当n为奇数时显然没有
a[n] = 4* a[n-2] - a[n - 4]
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 #define N 31 8 long long a[N]; 9 10 void init() 11 { 12 memset(a,0,sizeof(a)); 13 int i; 14 a[0] = 1; 15 a[2] = 3; 16 for(i = 3; i <= N; i++) 17 if(i % 2 == 0) 18 a[i] = 4*a[i-2] - a[i-4]; 19 } 20 21 int main() 22 { 23 init(); 24 int n; 25 while(scanf("%d",&n)) 26 { 27 if(n == -1) 28 break; 29 printf("%lld\n",a[n]); 30 } 31 return 0; 32 }