HDU 1041 Computer Transformation 大数递推
发布时间:2020-12-14 03:30:54 所属栏目:大数据 来源:网络整理
导读:Computer Transformation Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5787????Accepted Submission(s): 2090 Problem Description A sequence consisting of one digit,the number 1 is in
Computer Transformation Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5787????Accepted Submission(s): 2090
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
Sample Output
/* 要学会分析题目啊。。。。。 00的产生必然由n-1组的01产生,即00的个数等于n-1组01的个数。 n-1组01的产生有两个来源。 1).由n-2组的1 2).由n-2组的00变幻1010, 其中一个00只能产生一个01.这个就是要求的n-2连续的个数 可以推出第n组00的个数dp[n]=dp[n-2]+第n-2组1的个数(2^((n-2)-1)); 发现还要用大数 */ #include<iostream> #include<cstring> using namespace std; int dp[1002][500];//因为两个长度 比较麻烦 直接500 不记长度 int p[500]; int main(){ int n,i,j,z,t; memset(p,sizeof(p)); memset(dp,sizeof(dp)); dp[1][1]=0; dp[2][1]=1; dp[3][1]=1; p[1]=1; for(i=4;i<1001;i++) { for(j=1;j<500;j++)//处理2的多次方 p[j]=p[j]*2; z=0; for(j=1;j<500;j++) { t=p[j]+z; z=t/10; p[j]=t%10; } for(j=1;j<500;j++)//处理递推方程 dp[i][j]=dp[i-2][j]+p[j]; z=0; for(j=1;j<500;j++) { t=dp[i][j]+z; z=t/10; dp[i][j]=t%10; } } while(cin>>n) { i=499; while(dp[n][i]==0) i--; for(;i>=1;i--) printf("%d",dp[n][i]); if(n!=1) printf("n"); else printf("0n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |