Problem Description
A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step,
the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.
How many pairs of consequitive zeroes will appear in the sequence after n steps?
the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.
How many pairs of consequitive zeroes will appear in the sequence after n steps?
Input
Every input line contains one natural number n (0 < n ≤1000).
Output
For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.
Sample Input
2
3
Sample Output
1
1
找规律的问题，分开0和1的衍生问题就好理解了。
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std; const short MAX_N = 1001;
vector<short> tbl0[MAX_N], tbl1[MAX_N];//inverse saved numbers void addLargeNum(vector<short> &rs, vector<short> &a, vector<short> &b)
{
int n = (int)a.size(), m = (int)b.size();
rs.clear();
short carry = 0;
for (int i = 0, j = 0; i < n || j < m || carry; i++, j++)
{
short an = i < n ? a[i] : 0;
short bn = j < m ? b[i] : 0;
carry += an + bn;
rs.push_back(carry % 10);
carry /= 10;
}
} void plusOne(vector<short> &a)
{
if (a.empty()) a.push_back(1);
else
{
int i = 0;
while (i < (int)a.size() && 9 == a[i]) a[i++] = 0;
if (i == (int)a.size()) a.push_back(1);
else a[i]++;
}
} void getTbl()
{
tbl0[0].push_back(0); tbl0[1].push_back(0);
tbl1[0].push_back(0); tbl1[1].push_back(0); for (int i = 2; i < MAX_N; i++)
{
addLargeNum(tbl0[i], tbl1[i-1], tbl0[i-1]);
addLargeNum(tbl1[i], tbl0[i-1], tbl1[i-1]);
if (!(i&1)) plusOne(tbl1[i]);
}
} int main()
{
getTbl();
int n;
while (scanf("%d", &n) != EOF)
{
vector<short> &a = tbl1[n];
short m = (short)tbl1[n].size();
for (short i = m-1; i >= 0; i--)
{
printf("%d", a[i]);
}
putchar('\n');
}
return 0;
}