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里，这样可以减少很多行的代码。

 #include <stdio.h>

 #include <string.h>

 char num[],cmp[][],ans;

 int sum(char x[],int len,int m)      这个就是那个统计次数的函数。

 {

     int sum=;

     for(int i=;i<len;i++)

             if(x[i]==''+m) sum++;

     return sum;

 }

 int main()

 {

     while(scanf("%s",num),num[]!='-'){

         int len=strlen(num);

         ans=;

         for(int i=,k=;k<=;i++,k++){

             int tmp=sum(num,len,k);

             if(tmp==){

                 i--;

                 continue;

             }else{

             if(tmp>=){          //用来形成新的数串。

                 cmp[][i]=tmp/+'';

                 cmp[][++i]=tmp%+'';

                 cmp[][++i]=k+'';

             }

                 else {

                     cmp[][i]=tmp+'';

                     cmp[][++i]=k+'';

                 }

             }

         }

         int flog=;

         if(strcmp(cmp[],num)==){

             printf("%s is self-inventorying\n",num);

             flog=;

         }

         else{

             for(int i=;i<=;i++){

                     ans++;

                     int len=strlen(cmp[i-]);

                 for(int m=,k=;k<=;m++,k++){

                     int tmp=sum(cmp[i-],len,k);

                     if(tmp==){

                         m--;

                         continue;

                     }else{

                         if(tmp>=){

                             cmp[i][m]=tmp/+'';

                             cmp[i][++m]=tmp%+'';

                             cmp[i][++m]=k+'';

                         }

                         else {

                             cmp[i][m]=tmp+'';

                             cmp[i][++m]=k+'';

                         }

              }

                 }

                 if(strcmp(cmp[i],cmp[i-])==){

                     printf("%s is self-inventorying after %d steps\n",num,ans);

                     flog=;

                     break;

                 }

             }

         }

         if(flog==){

             for(int i=;i<;i++){

                 for(int j=i+;j<;j++)

                     if(strcmp(cmp[i],cmp[j])==) {

                         printf("%s enters an inventory loop of length %d\n",num,j-i);

                         flog=;

                         break;

                     }

                 if(flog) break;

             }

             if(flog==) printf("%s can not be classified after 15 iterations\n",num);

         }

         memset(num,,sizeof(num));

         memset(cmp,,sizeof(cmp));

     }

     return ;

 }

巴特西

POJ 1016

最新文章

热门文章