POJ 1016

http://poj.org/problem?id=1016

一道字符串处理的题目，理解题意后注意细节就好。

题意：每一串数字都可以写成 a1 b1 a2 b2 ....ai bi

其中ai是指bi这个数字，在一串数字中出现过多少次。也就是每一串数字都可以转换成这一种形式

题目就是给你一串数字，让你转换

如果转换后的数字和第一个数字一模一样的话，那么这一种类型被称为 self-inventorying

如果要通过N次转换后，n+1次和n是一模一样的话，那么这一种就被称为is self-inventorying after n steps

如果通过N（N<15）次转换后，在这N次的转换的数串之中，每隔K次就出现同一串数字，那么这种类型被称为 enters an inventory loop of length K

如果15次后，前面三种都没出现的话，那么被称作为can not be classified after 15 iterations

解题思路：

首先每一个数字都要进行统计，那么就需要一个统计次数的一个函数，因为这个需要多次使用。（这里注意次数可能会超过10次）。

其次利用strcmp函数判断两个字符串是否相等，strcmp函数的话，当两个串相等的时候是返回0.

然后就多次反复比较。

我写的还是比较丑。

有很大的优化空间，首先就是那个num可以放到cmp里，这样可以减少很多行的代码。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 char num[85],cmp[20][85],ans;
 5 
 6 int sum(char x[],int len,int m)      这个就是那个统计次数的函数。  
 7 {
 8     int sum=0;
 9     for(int i=0;i<len;i++)
10             if(x[i]=='0'+m) sum++;
11     return sum;
12 }
13 
14 int main()
15 {
16     while(scanf("%s",num),num[0]!='-'){
17         int len=strlen(num);
18 
19         ans=0;
20 
21         for(int i=0,k=0;k<=9;i++,k++){
22 
23             int tmp=sum(num,len,k);
24 
25             if(tmp==0){
26 
27                 i--;
28                 continue;
29 
30             }else{
31             if(tmp>=10){          //用来形成新的数串。
32                 cmp[0][i]=tmp/10+'0';
33                 cmp[0][++i]=tmp%10+'0';
34                 cmp[0][++i]=k+'0';
35             }
36                 else {
37                     cmp[0][i]=tmp+'0';
38                     cmp[0][++i]=k+'0';
39                 }
40             }
41         }
42         int flog=0;
43         if(strcmp(cmp[0],num)==0){
44 
45             printf("%s is self-inventorying
",num);
46             flog=1;
47         }
48         else{
49 
50             for(int i=1;i<=16;i++){
51                     ans++;
52                     int len=strlen(cmp[i-1]);
53                 for(int m=0,k=0;k<=9;m++,k++){
54 
55                     int tmp=sum(cmp[i-1],len,k);
56 
57                     if(tmp==0){
58 
59                         m--;
60                         continue;
61 
62                     }else{
63                         if(tmp>=10){
64                             cmp[i][m]=tmp/10+'0';
65                             cmp[i][++m]=tmp%10+'0';
66                             cmp[i][++m]=k+'0';
67                         }
68                         else {
69 
70                             cmp[i][m]=tmp+'0';
71                             cmp[i][++m]=k+'0';
72                         }
73              }
74                 }
75                 if(strcmp(cmp[i],cmp[i-1])==0){
76                     printf("%s is self-inventorying after %d steps
",num,ans);
77                     flog=1;
78                     break;
79                 }
80             }
81         }
82         if(flog==0){
83             for(int i=0;i<14;i++){
84                 for(int j=i+2;j<15;j++)
85                     if(strcmp(cmp[i],cmp[j])==0) {
86                         printf("%s enters an inventory loop of length %d
",num,j-i);
87                         flog=1;
88                         break;
89                     }
90                 if(flog) break;
91             }
92             if(flog==0) printf("%s can not be classified after 15 iterations
",num);
93         }
94         memset(num,0,sizeof(num));
95         memset(cmp,0,sizeof(cmp));
96     }
97     return 0;
98 }