首页 > 代码库 > 2013级机试D题解析

2013级机试D题解析

写于2014-01-10 。 关键字:字符串比较,结构化编程,单入口/单出口

 http://acm.hnust.edu.cn/JudgeOnline/problem.php?cid=1081&pid=3

问题 D: 大小写不敏感之字符串比较
给定两个字符串,判定其是否相等。字符串相等的意义基于类似于strcmp函数,除了比较时忽略大小写,例如”999abc”和”999ABC”是相等的字符串。

输入

一行输入,包括由空格分开的两个字符串,字符串本身不含空格,字符串长度均不超过100

输出

如果字符串相等,输出一行”EQUAL”,否则输出一行”NOT EQUAL”


样例输入
999abc 999ABC


样例输出
EQUAL

 

本次机试的BDE题是我出的。D题可看成strcmp的加强版。先看一下讲义中strcmp的实现,注意返回0是表示相等

1
2
3
4
5
6
7
8
int myStrcmp(char *s, char *t)
{           
             int i;
             for(i=0;s[i]==t[i];i++)
                   if (s[i]==‘\0‘)
                      return 0;
             return s[i]-t[i];
}

现在的问题是忽略大小写,我们有toupper函数可以用,对于小写字母,toupper函数会将其转换成大写字母并返回,对于非小写字母,toupper函数返回原字符。实现如下:

1
2
3
4
5
6
7
8
int NoCaseStrcmp(char *s, char *t)
{          
             int i;
             for(i=0;toupper(s[i])==toupper(t[i]);i++)
                   if (s[i]==‘\0‘)
                      return 0;
             return s[i]-t[i];
}

剩下的事情就是调用NoCaseStrcmp了,大家自己完成。可以看到,使用现成的库函数能让编码工作变少,代码简洁。

 

上面的处理都是把功能封装在一个函数中,这是我极力向同学们推荐的。下面我们讨论另外一个问题,上面的函数使用了两个return,实际上就有两个出口,从理论上是违反结构化程序设计的。如果我们不把功能封装在函数中,而是直接在main中实现,也往往要使用return同类性质的跳转语句break等,如下的代码,for循环依然有两个出口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void)
{
   int i;
   char s[200], t[200];
   while(scanf("%s%s", s, t) != EOF){
      for(i = 0; toupper(s[i]) == toupper(t[i]); i++)
          if(s[i] == ‘\0‘)
              break;
      if(s[i] == t[i])
         puts("EQUAL");
      else
         puts("NOT EQUAL");
   }
   return 0;
}

 

有没有办法去掉break呢?设置一个flag当然可以,但是多出一个flag感觉总不是那么美妙。下面的技巧是以前某次PK时我突然发现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void)
{
   int i;
   char s[200], t[200];
   while(scanf("%s%s", s, t) != EOF){
      for(i = 0; toupper(s[i]) == toupper(t[i]) && s[i]; i++);
      if(s[i] == t[i])
         puts("EQUAL");
      else
         puts("NOT EQUAL");
   }
   return 0;
}

请体会此处&&的妙味。

 

再回顾求1-100间的所有素数的代码

 

1
2
3
4
5
6
7
int  i,j;
for(i=2;i<101;i++)
{
  for(j=2;j<=i/2;j++)
    if(!(i%j))  break;
  if(j>i/2) printf("%4d",i);
}

这里的break你能去掉吗?

 

总结一下,上面的内容回顾了我们课堂的教学内容,介绍了一个利用&&去掉break的技巧,我无意推广这个技巧,因为去掉break并没有让代码的可读性变得更好。但是了解我曾经的思考过程或许对你有点借鉴意义。

 

小考题:下面的代码是我第一次写的,结果发现了一个bug,你能发现吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void)
{
   int i;
   char s[200], t[200];
   while(scanf("%s%s", s, t) != EOF){
      for(i = 0; toupper(s[i]) == toupper(t[i]) && s[i]; i++);
      if(s[i] == ‘\0‘)
         puts("EQUAL");
      else
         puts("NOT EQUAL");
   }
   return 0;
}

 

 答案

技术分享
如果字符串s为字符串t的前缀,将出现错误的判段。例如s为"ab", t为"abc"。 i=2时s[i]为\0, t[i]为c, for循环结束,但s[i]==\0为真
View Code

 

2013级机试D题解析