hdu

万进制

题目链接

Computer Transformation

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,初始时数组中只有1.所以执行第1次后数组变成01,第2次变成1001,以此类推.问执行到第n步时有几对连续的00存在.

这道题属于大数处理,基本上规律是很容易得到的.做了两道,就贴这一道留个纪念. 这里是每10000进1,即传说中的万进制.计算时要注意余数用后清零.打印时高位补0. f[k] = f[k-1] + 2 * f[k-2] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<string.h>
#define MAX 1001
#define MOD 10000

int a[MAX][500]; //{0,0,1,1,3,5,11,21,43,85,171};

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n, i,j,y;
    memset(a, 0, sizeof(a));
    a[1][0] = 1; //length of a[1]
    a[1][1] = 0;
    a[2][0] = 1;
    a[2][1] = 1;
    for(i = 3; i < MAX; i++){
        memcpy(a[i], a[i-1], 4*(a[i-1][0]+1));//memcpy(dis, src, size of byte)
        y = 0;
        for(j = 1; j <= a[i-2][0]; j++){
            a[i][j] += (a[i-2][j]<<1) + y;
            y = 0;
            if(a[i][j] >= MOD){
                y = a[i][j] / MOD;
                a[i][j] %= MOD;
            }
        }
        if(y){
            a[i][j] += y;
            if(j > a[i][0])a[i][0] = j;
        }
    }
    while(~scanf("%d", &n)){
        printf("%d", a[n][a[n][0]]);
        for(int i = a[n][0]-1; i > 0; i--){
            if(a[n][i] >= 1000){
                printf("%d", a[n][i]);
            }else if(a[n][i] >= 100){
                printf("0%d", a[n][i]);
            }else if(a[n][i]>=10){
                printf("00%d", a[n][i]);
            }else printf("000%d", a[n][i]);
        }
        printf("\n");
    }
   // fclose(stdin);
   // fclose(stdout);
    return 0;
}