首页 > 代码库 > UVa 1647 - Computer Transformation

UVa 1647 - Computer Transformation

题目:初始给你一个1,然后每一次1变成01,0变成10求变化n步后,有多少个00。

分析:数学题。我们观察变化。

 

            00 -> 1010 出现 10、01

            01 -> 1001 出现 10、00、01

            10 -> 0110 出现 01、11、10

            11 -> 0101 出现 01、10

            仅仅有01下一步会生成00,可是00、01、10、11都会生成01。每个1都会生成01,而00也能够生成01,

            由此分成两种情况计算;设O(n)是变化n步后1的个数。Z(n)是变化n步后生成的00的个数。有结论:

             Z(n)= Z(n-2)+ O(n-2)。O(n)= 2^(n-1){不管0、1都会生成0与1。所以是位数的一半}

说明:数据较大,用数组模拟大整数运算。

#include <iostream>
#include <cstdlib>    
#include <cstring>
#include <cstdio>      
    
using namespace std;    
  
int O[1010][100];
int Z[1010][100];
  
int main(){
	memset( O, 0, sizeof(O) );
	memset( Z, 0, sizeof(Z) );
	O[0][0] = O[1][0] = 1;
    for ( int i = 2 ; i < 1001 ; ++ i ) 
	for ( int k = 0 ; k < 100  ; ++ k ) {
		O[i][k] += O[i-1][k] + O[i-1][k];
		Z[i][k] += O[i-2][k] + Z[i-2][k];
		O[i][k+1] += O[i][k]/10000; O[i][k] %= 10000;
		Z[i][k+1] += Z[i][k]/10000; Z[i][k] %= 10000;
	}
    
    int n;
    while( ~scanf("%d",&n) ) {
        int end = 99;
		while ( end > 0 && !Z[n][end] ) -- end;
		printf("%d",Z[n][end --]);
		while ( end >= 0 )
			printf("%04d",Z[n][end --]);
		printf("\n");
    }    
    return 0;    
}   

UVa 1647 - Computer Transformation