Computer Transformation
Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7862 Accepted Submission(s): 2942
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?
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
題解：計算機能把1變成01，0變成10，問第n步后00的個數 step0:1 step1:0 1 step2:10 01 step3:0110 1001 step4:1001 0110 0110 1001 step5:0110 1001 1001 0110 1001 0110 0110 1001 第n步的00由n-1步的01變化而來，第n-1步的01則由n-2步的1變化而來 除此之外，第n-2步的00->1010->01100110也貢獻一個00 所以F（n）=F（n-2）+2^（n-3）（即n-2步里1的個數）
代碼：
#include <iostream>#include <string>#include <cstring>#include <cstdio>#include <cmath>#include <cstdlib>#include <algorithm>#include <queue>#include <map>#define MST(s,q) memset(s,q,sizeof(s))#define INF 0x3f3f3f3f#define MAXN 9999using namespace std;int a[1005][1001];//F(n) = F(n - 2) + 2 ^ (n - 3);void deal(){ MST(a, 0); a[0][1] = 1; a[1][1] = 0, a[2][1] = 1, a[3][1] = 1; for (int i = 4; i <= 1000; i++) { int r = 0; for (int j = 1; j <= 1000; j++) { a[0][j] *= 2; a[0][j] += r; r = 0; if (a[0][j] > 9) { r = 1; a[0][j] -= 10; } } r = 0; for (int j = 1; j <= 1000; j++) { a[i][j] = a[i - 2][j] + a[0][j] + r;; r = 0; if (a[i][j] > 9) { r = 1; a[i][j] -= 10; } } }}int main(){ deal(); int n; while (cin >> n) { if (n == 1) { cout << 0 << endl; continue; } int i = 1000; while (a[n][i] == 0)i--; for (; i >= 1; i--) printf("%d", a[n][i] ); printf("/n"); }}新聞熱點
疑難解答
