首页 > 代码库 > H - Computer Transformation(简单数学题+大数)
H - Computer Transformation(简单数学题+大数)
H - Computer Transformation
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
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?
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
23Sample Output
1
1
//这题意思是
1 01 0
2 1001 1
3 01101001 1
1->01 0->10
就这么一直变下去,问 n 步之后，有多少个相邻的 0
我是先输出模拟了大概 8 项找出了规律，然后。。。wa
因为数据太大，long long 也存不下
然后用字符串，当做大数处理，就可以了，注意一些细节问题，代码里有
1 /* 2 //EEE 3 #include <stdio.h> 4 #include <string.h> 5 6 char ch[10][1200]; 7 8 int main() 9 { 10 strcpy(ch[0],"01"); 11 12 for (int i=1;i<10;i++) 13 { 14 int k=0; 15 int len=strlen(ch[i-1]); 16 for (int j=0;j<len;j++) 17 { 18 if (ch[i-1][j]==‘0‘) 19 { 20 ch[i][k++]=‘1‘; 21 ch[i][k++]=‘0‘; 22 } 23 else 24 { 25 ch[i][k++]=‘0‘; 26 ch[i][k++]=‘1‘; 27 } 28 } 29 ch[i][k]=‘\0‘; 30 } 31 for (int i=0;i<10;i++) 32 { 33 34 int sum=0; 35 int len =strlen(ch[i]); 36 for (int j=0;j<len-1;j++) 37 { 38 if (ch[i][j]==‘0‘&&ch[i][j+1]==‘0‘) 39 sum++; 40 } 41 //printf("%s\n",ch[i]); 42 printf("%d\n",sum); 43 } 44 return 0; 45 } 46 */ 47 48 #include <stdio.h> 49 #include <string.h> 50 #include <math.h> 51 #include <algorithm> 52 using namespace std; 53 54 char num[1005][500]; 55 char str[500]; 56 57 char *add(char s[]) 58 { 59 memset(str,0,sizeof(str)); 60 61 int i; 62 int len=strlen(s); 63 for (i=0;i<len;i++) 64 s[i]-=‘0‘; 65 reverse(s,s+len); 66 67 for (i=0;i<len;i++) 68 { 69 str[i]+=s[i]*2; 70 if (i==0) str[i]++; 71 72 if (str[i]>=10) 73 { 74 str[i]-=10; 75 str[i+1]++; 76 } 77 78 } 79 while (str[i]!=0) i++; 80 str[i]=‘\0‘; 81 for (int j=0;j<i;j++) str[j]+=‘0‘; 82 for (int j=0;j<len;j++) s[j]+=‘0‘; 83 reverse(str,str+i); 84 reverse(s,s+len); 85 return str; 86 } 87 88 char *de(char s[]) 89 { 90 memset(str,0,sizeof(str)); 91 92 int i; 93 int len=strlen(s); 94 for (i=0;i<len;i++) 95 s[i]-=‘0‘; 96 reverse(s,s+len); 97 98 int k=0,flag=0; 99 for (i=0;i<len;i++)100 {101 str[i]+=s[i]*2;102 if (str[i]>=10)103 {104 str[i]-=10;105 str[i+1]++;106 }107 108 if (flag==0&&str[i]==0)//减1，看这个数最后有几个 0109 {110 k++;111 }112 if (str[i]!=0) flag=1;113 114 }115 while (str[i]!=0) i++;116 str[i]=‘\0‘;117 118 str[k]--;119 while (k--) str[k]=9;//减 1120 121 for (int j=0;j<i;j++) str[j]+=‘0‘;122 for (int j=0;j<len;j++) s[j]+=‘0‘;123 reverse(str,str+i);124 reverse(s,s+len);125 return str;126 }127 128 129 int main()130 {131 int n;132 int i;133 int xx=0;134 135 strcpy(num[1],"0");136 137 for (i=2;i<=1000;i++)138 {139 if (i%2==0)140 {141 add(num[i-1]);142 strcpy(num[i],str);143 }144 145 else146 {147 de(num[i-1]);148 strcpy(num[i],str);149 }150 }151 while (scanf("%d",&n)!=EOF)152 {153 printf("%s\n",num[n]);154 }155 return 0;156 }
H - Computer Transformation(简单数学题+大数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。