前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >追踪状态——消息解码问题的思路剖析

追踪状态——消息解码问题的思路剖析

作者头像
Zoctopus
发布2018-06-04 11:57:25
7540
发布2018-06-04 11:57:25
举报
文章被收录于专栏:章鱼的慢慢技术路

一、题目描述 

一条消息被编码为一个文本流,被逐字符地读取。这个流包含了一系列由逗号分隔的整数,每个整数都可以用C的int类型表示。但是,一个特定整数所表示的字符取决于当前的解码模式。共有3种这样的模式:大写字母、小写字母和标点符号。

在大写字母模式下,每个整数表示一个大写字母:这个整数除以27的余数表示字母表中的具体字母(其中1=A,接下来以此类推)。因此,大写字母模式中的143这个值表示字母H,因为143除以27的余数为8,而H正是字母表中的第8个字母。

小写字母模式的机制类似,只不过表示的是小写字母。整数除以27的余数表示小写字母(1=a,接下来以此类推)。因此,在小写字母模式下,56这个值表示字母b,因为56除以27的余数是2,而b正是字母表中的第2个字母。

在标点符号模式下,是把整数除以9求余,下表给出了不同余数的解释。19表示感叹号,因为19除以9的余数是1。

编号

符号

1

2

3

4

.

5

(空格)

6

7

"

8

\'

下面我们通过一张图来理解下消息解码问题的处理(B-大写模式;X-小写模式;D-标点符号模式):

a列显示了输入中的当前数字;b列是当前的模式;c列显示了当前模式的除数;d列是a列的当前输入除以c列的除数所得到的余数;e列显示了结果。

二、问题分块解析

我们需要读取一个字符串,直到读取到行末符。这些字符表示一系列的整数,因此需要读取这些数字字符并把它们转换为整数以便进行处理。有了这些整数之后,需要把他们转换为单个字符进行输出。最后我们需要一些方法处理解码模式,以便知道当前的整数应该被解码为小写字母、大写字母还是标点符号。我们首先把这些需要完成的任务进行分解:

  • 逐个读取字符,直到读取了行末符。
  • 把表示一个数的一系列字符转换为一个整数。
  • 把一个1~26之间的整数转换为一个大写字母。
  • 把一个1~26之间的整数转换为一个小写字母。
  • 把一个1~8之间的整数转换为一个标点符号。
  • 追踪一种解码模式。
让我们从整数到字符的转换开始

从Luhn公式程序中,我们知道需要读取一个0~9范围内的字符数字,并把它转换为0~9范围的整数。我们怎么才能扩展这种方法,使之能够处理多位数呢?让我们考虑最简单的可能性:两位数。这看上去非常简单。在两位数中,第一个数字是十位数,因此我们应该把这个数字乘以10,然后与第二个数字所表示的值相加。例如:输入一个数为35,我们用程序以字符的形式分别读取了3和5之后,把它们分别转换为整数3和5,然后通过表达式3*10+5得到总的整数。我们可以用代码来验证一下:

代码语言:javascript
复制
1     char digitChart1,digitChart2;
2     printf("Enter a two-digit number:");
3     scanf("%c",&digitChart1);
4     scanf("%c",&digitChart2);
5     int digit1 = digitChart1 - '0';
6     int digit2 = digitChart2 - '0';
7     int overallNumber = digit1 * 10 + digit2;
8     printf("That number as an integer:%d",overallNumber);

这段代码达到了输出了我们输入的相同的两位数。但是,这个程序使用两个不同的变量保存两个字符输入,虽然它在当前不会有什么问题,但显然不适合作为一种通用的解决方案。如果采用这样的做法,我们所需要的变量数量就和输入的数字一样多。这很容易造成混乱,并且如果输入流发生了变化就很难修改输入数据的字数范围。对于把字符变换为整数的这个子任务,我们需要一种更通用的解决方案。寻找这种通用的解决方案的第一个步骤是对前面的代码进行限制,使它只能使用2个变量,1个char变量和1个int变量:

代码语言:javascript
复制
1     char digitChart;
2     printf("Enter a two-digit number:");
3     scanf("%c",&digitChart);  //读取第一个字符数字 
4     int overallNumber = (digitChart - '0') * 10;  //把它转换为整数并乘以10,然后存储结果 
5     scanf("%c",&digitChart);  //读取第二个数字 
6     overallNumber += (digitChart - '0');
7     printf("That number as an integer:%d",overallNumber);

它的功能与前面的代码相同,区别在于只使用了两个变量:一个表示最近所读取的字符,一个表示整数的总值。

下一个步骤是考虑这样对这个方法进行扩展,使之适用于三位数。一旦完成了这个任务之后,我们很可能会发现一种模式,可以为任意位数的整数创建一个通用的解决方案。

但是我们不知道要处理的数有多少个数字,所以我们可以试着:编写一个程序,逐字符读取一个数,并把它转换为整数,只能使用1个char变量和1个int变量,这个数可能由3个或4个数字组成。

由于我们只能使用1个数值变量,如果没有思路,可以先放宽这个限制,以便取得一些进展,所以简化后的问题为:编写一个程序,逐字符读取一个数,并把它转换为整数,只能使用1个char变量和2个int变量,这个数可能由3个或4个数字组成。

现在我们可以把“双管齐下”的计算方法付诸实施。我们将用两种不同的方式处理前3位数字,然后看看是否存在第4位数字:

代码语言:javascript
复制
 1     char digitChar;
 2     printf("Enter a three-digit number:");
 3     scanf("%c",&digitChar);
 4     int threeDigitNumber = (digitChar - '0') * 100;  //读取最左边的数字之后,把它的整数值乘以100,并把它存储在表示三位数的变量中 
 5     int fourDigitNumber = (digitChar - '0') * 1000;
 6     scanf("%c",&digitChar);
 7     threeDigitNumber += (digitChar - '0') * 10;
 8     fourDigitNumber += (digitChar - '0') * 100;
 9     scanf("%c",&digitChar);
10     threeDigitNumber += (digitChar - '0');
11     fourDigitNumber += (digitChar - '0') * 10;
12     scanf("%c",&digitChar);
13     if(digitChar == 10)  //在读取了第4个字符之后,我们把它与10这个数进行比较,确定它是否为行末符 
14         printf("Number entered:%d\n",threeDigitNumber);  //如果是,那么所输入的值就是个三位数 
15     else
16         printf("Number entered:%d\n",fourDigitNumber);  //如果不是,我们需要把它作为最后一个数字添加到总和中 

现在,我们需要确定怎样去掉其中一个整型变量。假设我们完全去掉了fourDigitNumber变量,threeDigitNumber仍然是被正确赋值的。但是当我们需要fourDigitNumber时,就没办法再得到它了。使用threeDigitNumber的值,是否还有办法确定fourDigitNumber的值呢?假设原始输入为1234,在读取了前3个数字之后,threeDigitNumber变量的值将是123,此时fourDigitNumber的值应该是1230。一般而言,由于在计算过程中fourDigitNumber的每个乘数都是threeDigitNumber的对应乘数的10倍,因此前者的值总是后者的10倍。所以我们只需要使用1个整型变量,因为在必要的情况下只要乘以10就可以得到另一个变量的值:

代码语言:javascript
复制
 1     char digitChar;
 2     printf("Enter a three-digit number:");
 3     scanf("%c",&digitChar);
 4     int number = (digitChar - '0') * 100;
 5     scanf("%c",&digitChar);
 6     number += (digitChar - '0') * 10;
 7     scanf("%c",&digitChar);
 8     number += digitChar - '0';
 9     scanf("%c",&digitChar);
10     if(digitChar == 10)   
11         printf("Number entered:%d\n",number);  
12     else{
13         number = number * 10 + (digitChar - '0');
14         printf("Number entered:%d\n",number); 
15     }

现在我们已经有了一个可利用的模式。考虑把这段代码扩展到可以处理五位数:

代码语言:javascript
复制
 1     char digitChar;
 2     printf("Enter a number with three,four,five digits:");
 3     scanf("%c",&digitChar);
 4     int number = (digitChar - '0') * 100;
 5     scanf("%c",&digitChar);
 6     number += (digitChar - '0') * 10;
 7     scanf("%c",&digitChar);
 8     number += digitChar - '0';
 9     scanf("%c",&digitChar);
10     if(digitChar == 10)    
11         printf("Number entered:%d\n",number);    
12     else{
13         number = number * 10 + (digitChar - '0');
14         scanf("%c",&digitChar);
15         if(digitChar == 10){  //检查它是否表示行末符
16             printf("Number entered:%d\n",number); //如果是,就显示之前计算所得的数
17         }
18         else{
19             number = number * 10 + (digitChar - '0');  //否则就把它乘以10,再加上当前字符所表示的整数数值 
20             printf("Number entered:%d\n",number);
21         }
22     }

我想现在这个模式已经非常清晰了:如果下一个字符非行末符,就可以将当前的数乘以10,然后与当前字符所表示的整数值相加。理解了这一点,我们就可以编写一个循环,处理任意长度的整数了:

代码语言:javascript
复制
 1     char digitChar;
 2     printf("Enter a number with as many digits as you like:");
 3     scanf("%c",&digitChar);  //读取第一个字符 
 4     int number = (digitChar - '0');  //确定它的整数值 
 5     scanf("%c",&digitChar);  //读取第二个字符并进入循环 
 6     while(digitChar != 10){  //检查最近所读取的那个字符是否为行末符 
 7         number = number * 10 + (digitChar - '0');  //如果不是,就把当前为止的和乘以10,并与当前字符的整数值相加 
 8         scanf("%c",&digitChar);  //然后读取下一个字符 
 9     }
10     printf("Numbered entered:%d\n",number);  //一旦读入了行末符,表示当前整数的变量number就包含了可以输出的整数值

这段代码用于处理一系列的字符到对应的整数值的转换。在最终的程序中,我们将读取一系列由逗号分隔的数,而且每个数必须单独读取并处理。

让我们考虑下101,22[EOF](行末符)这个输入,对循环的测试条件进行修改,对行末符或逗号进行检查是很轻松的。接着,我们需要把处理一个数的循环放在一个更大的循环中,后者在所有的数被读取之前将一直持续。因此,内层循环在读取到[EOF]或逗号时将会结束,而外层循环只有在读取到[EOF]时才会结束:

代码语言:javascript
复制
 1     char digitChar;
 2     do{
 3         scanf("%c",&digitChar);
 4         int number = (digitChar - '0');  
 5         scanf("%c",&digitChar); 
 6         while((digitChar != 10)&&(digitChar != ',')){  //内循环 
 7             number = number * 10 + (digitChar - '0');
 8             scanf("%c",&digitChar);
 9         }
10         printf("Number entered:%d\n",number);
11     }while(digitChar != 10);  //外循环    
下面我们可以把注意力集中在处理单独的数上了

把一个范围在1~26之间的数转换为一个A~Z范围内的字母,稍微想一下,就可以发现它实际上是把单个数字字符转换为对应整数值的逆操作。如果我们减去0的字符码,能够从0~9范围的字符码转换为0~9范围的整数值,那么应该也能够通过加上一个字符码,从1~26转换为A~Z。我们先试试加上'A'会怎么样:

代码语言:javascript
复制
1     printf("Enter a number 1-26:");
2     int number;
3     scanf("%d",&number);
4     char outputCharacter;
5     outputCharacter = number + 'A';
6     printf("Equivalent symbol:%c\n",outputCharacter); 

结果显然不正确!字母表中的第五个字母是E而不是F。出现问题的原因是我们从1开始的范围加上一个数的,当我们从另一个方向进行转换,把一个字符数字转换为对应的整数值时,我们所处理的范围应该是从0开始的。所以我们可以把第5行的代码改成number + 'A' - 1来修正这个问题。

因为表中的标点符号在ASCII或其他任何字码符系统中都不是按照这个顺序出现的,因此我们必须用穷举法处理这个标点符号表转换的问题:

代码语言:javascript
复制
 1     printf("Enter a number 1-8:");
 2     int number;
 3     scanf("%d",&number);
 4     char outputCharacter;
 5     switch(number){
 6         case 1:outputCharacter = '!';break;
 7         case 2:outputCharacter = '?';break;
 8         case 3:outputCharacter = ',';break;
 9         case 4:outputCharacter = '.';break;
10         case 5:outputCharacter = ' ';break;
11         case 6:outputCharacter = ';';break;
12         case 7:outputCharacter = '"';break;
13         case 8:outputCharacter = '\'';break; //使用反斜杠作为转义符,以显示单引号 
14     }
15     printf("Equivalent symbol:%c\n",outputCharacter); 
还有一个子问题:当最近读取值的解码结果为0时,就进行模式的转换。

根据最开始的问题描述,知道了我们需要的就是一个存储当前模式的变量,并把逻辑放在“读取并处理下一个值”的循环中,在必要的时候切换模式。追踪当前模式的变量可以是个简单的整数,但是使用枚举显然可以使代码更容易理解。一个很好的经验是:如果一个变量只用于追踪一个状态,并且任何特定的值并没有内在的含义,那么使用枚举法就很好了。下面根据这个思路写下代码:

代码语言:javascript
复制
 1     enum modeType{UPPERCASE,LOWERCASE,PUNCTUATION};   //枚举型
 2     int number;
 3     modeType mode = UPPERCASE;
 4     printf("Enter some numbers ending with -1:");
 5     do{
 6         scanf("%d",&number);
 7         printf("Number read:%d",number);
 8         switch(mode){
 9             case UPPERCASE:
10                 number = number%27;
11                 printf(". Modulo 27:%d.",number);
12                 if(number == 0){
13                     printf("Switch to LOWERCASE");
14                     mode = LOWERCASE;
15                 }
16                 break;
17             case LOWERCASE:
18                 number = number%27;
19                 printf(". Modulo 27:%d.",number);
20                 if(number == 0){
21                     printf("Switch to PUNCTUATION");
22                     mode = PUNCTUATION;
23                 }
24                 break;
25             case PUNCTUATION:
26                 number = number%9;
27                 printf(". Modulo 9:%d.",number);
28                 if(number == 0){
29                     printf("Switch to UPPERCASE");
30                     mode = UPPERCASE;
31                 }
32                 break;
33         }
34         printf("\n");
35     }while(number != -1);

此时,我们创建了一系列的建筑块,这是最艰苦的工作,现在的任务是把它们装配在一起。

三、完整代码

代码语言:javascript
复制
 1     char outputCharacter;
 2     enum modeType{UPPERCASE,LOWERCASE,PUNCTUATION};   //枚举型
 3     modeType mode = UPPERCASE;
 4     char digitChar;
 5      do{
 6          scanf("%c",&digitChar);
 7         int number = (digitChar - '0');  
 8         scanf("%c",&digitChar); 
 9         while((digitChar != 10)&&(digitChar != ',')){  //内循环 
10           number = number * 10 + (digitChar - '0');
11           scanf("%c",&digitChar);
12         }
13         switch(mode){
14             case UPPERCASE:
15                 number = number%27;
16                 outputCharacter = number + 'A' -1;
17                 if(number == 0){
18                     mode = LOWERCASE;
19                     continue;
20                 }
21                 break;
22             case LOWERCASE:
23                 number = number%27;
24                 outputCharacter = number + 'a' -1;
25                 if(number == 0){
26                     mode = PUNCTUATION;
27                     continue;
28                 }
29                 break;
30             case PUNCTUATION:
31                 number = number%9;
32                 switch(number){
33                                  case 1:outputCharacter = '!';break;
34                                 case 2:outputCharacter = '?';break;
35                                 case 3:outputCharacter = ',';break;
36                                 case 4:outputCharacter = '.';break;
37                                 case 5:outputCharacter = ' ';break;
38                                 case 6:outputCharacter = ';';break;
39                                 case 7:outputCharacter = '"';break;
40                                 case 8:outputCharacter = '\'';break;  
41                  }
42                 if(number == 0){
43                     mode = UPPERCASE;
44                     continue;
45                 }
46                 break;
47         }
48         printf("%c",outputCharacter);
49    }while(digitChar != 10);  //外循环 
50    printf("\n");  
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-01-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述 
  • 二、问题分块解析
    • 让我们从整数到字符的转换开始
      • 下面我们可以把注意力集中在处理单独的数上了
        • 还有一个子问题:当最近读取值的解码结果为0时,就进行模式的转换。
        • 三、完整代码
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档