怎样调戏程序——《C解毒》试读

    不要疑惑，我说的确实不是如何调试程序，而是怎样调戏程序。调戏程序比调试程序更困难、更重要也更有乐趣。因为，虽然不懂得如何调试程序就意味着无法改正程序中存在的错误，但是，如果不懂得怎样调戏程序，你可能连程序中所存在的错误都无法发现。
    好，废话少说，这就来看题。题目是这样的：

 

题目：找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点。
——谭浩强 ，《C程序设计（第四版）学习辅导》，清华大学出版社，2010年7月，p63

 

    题目看起来没有任何问题，但请不要轻信。就像不要轻易相信小广告一样，一旦轻信你就必然上当，所以轻信是一种很foolish的行为，在程序设计过程中也是如此，因为一旦轻信，就根本不可能调戏程序。
    实际上自然语言往往是模糊的、有歧义的，这种歧义可能导致对程序功能在理解上的分歧，而一旦产生这种分歧，程序写的再怎么正确也必定是错误的。
    在这个题目里，“最大”、“最小”这两个词汇就非常令人起疑。究竟什么叫“在该行上最大”，如果在某行上有这样几个元素：5、2、3、1、5，那么这里的那两个5究竟算不算在该行上最大？或者说这行上究竟有没有最大元素？这样的问题，恐怕3个人中至少会产生4种见解。
    然而弄清楚这两个词的确切含义，关系到是否真正了解了题目的要求。而真正了解题目的要求，在程序设计中的重要性是首当其冲的。连究竟要做什么都不知道你还写神马代码？
    初学者往往意识不到这一点，他们经常轻率地认为他们了解题目的要求是什么，而把重点放在写代码上。但优秀的程序员们恰恰相反，他们往往要在弄清楚究竟要做什么上花费最多的精力。这里就有一个生动的例子(《如何去应付你的上司给你一个变化无常的需求？》
http://www.cnblogs.com/muer/arch ... getrequirement.html)，你可以发现优秀的程序员在弄明白究竟要做什么这件事情上承受着多么巨大的烦恼，绝对不会像初学者们那样“没心没肺”。因为他们清楚地知道：“需求错了是你制造出的最大的BUG”。与正确地理解需求相比，什么设计啊、代码啊神马的都是浮云。
    现在回到题目上。题目中并没有进一步明确“最大”、“最小”这两个词的任何线索，这让人好生烦恼。不过好在后面有题目解答，因此我们可以带着对“最大”、“最小”这两个词的确切含义的疑问继续调戏程序。下面是这道题目的一种解题思路

    一个二维数组最多只有一个鞍点，也可能没有。解题思路是：先找出一行中值最大的元素，然后检查它是否为该列的最小值，如果是，则是鞍点（不需要再找别的鞍点了），输出该鞍点；如果不是，则再找下一行的最大数……如果每一行的最大数都不是鞍点，则此数组无鞍点。
——谭浩强 ，《C程序设计（第四版）学习辅导》，清华大学出版社，2010年7月，p63

    思路点评：
    这个解题思路首先没头没脑且非常武断地来了一句“一个二维数组最多只有一个鞍点”。由于这不属于常识范围之列，又没有给出有力的证明，所以不管你们信不信，反正我是不信。至少在弄清楚“最大”、“最小”这两个词的含义之前不信。
    “先找出一行中值最大的元素，然后检查它是否为该列的最小值”：貌似有理，然而仔细推敲一下不难发现其中的逻辑漏洞。找出最大的元素的前提是存在这样的元素，如果某行中各个元素的值都相等，那么算不算存在最大元素？如果算的话应该找出几个？如果某行中各个元素的值都相等算不算是存在最大元素，如果出现了这种情况程序应该如何处理？这些问题在这个解题思路显然根本就没有考虑。这样的程序不出毛病才怪呢！
    经过了这些思考，现在就可以正式调戏程序了。这个程序的代码如下

#include <stdio.h>
#define N 4
#define M 5
int main()
{
  int i,j,k,a[N][M],max,maxj,flag;
  printf("please input matrix:\n");
  for(i=0;i<N;i++)
    for(j=0;j<M;j++)
      scanf("%d",&a[ i][j]);
  for(i=0;i<N;i++)
    {max=a[ i][0];
     maxj=0;
     for(j=0;j<M;j++)
       if(a[ i][j]>max)
         {max=a[ i][j];
          maxj=j;
         }
     flag=1;
     for(k=0;k<N;k++)
       if(max>a[k][maxj])
          {flag=0;
           continue;}
     if(flag)
      {printf("a[%d][%d]=%d\n",i,maxj,max);
       break;
      }
    }
  if(!flag)
     printf("It is not exist!\n");
  return 0;
}

——谭浩强 ，《C程序设计（第四版）学习辅导》，清华大学出版社，2010年7月，p63~64

    这个程序，当输入
    1 2 3 4 5
    2 4 6 8 10
    3 6 9 12 15
    4 8 12 16 20
    时的输出为：
    a[0][4]=5
    当输入
    1 2 3 4 11
    2 4 6 8 12
    3 6 9 12 15
    4 8 12 16 7
    时的输出为：
    It is not exist!
    表现似乎倒也还算正常(虽然我没看懂“It is not exist!”究竟是哪国英语)。
    然而所谓“调戏”，就是要用各式各样的数据骚扰程序，试验程序都有什么反应。简而言之，就是逗你玩。怀着前面对“最大”“最小”的困惑，很自然会想到用这样的输入数据来调戏一下程序：
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    1 1 1 1 1
    这回程序的输出竟然是
    a[0][0]=1
    这个输出结果究竟应该怎么理解呢?若是说输入的二维数组没有鞍点吧，这个程序硬给整出来一个；若是说这数组有鞍点吧，那么它一共有20个鞍点（注意这和“一个二维数组最多只有一个鞍点”相矛盾），但程序只算出了一个。然而可以确定的是，无论怎样解释这个结果都是错误的。
    看来，程序本无BUG，调戏的次数多了，也就有了BUG。
    稍微地审视一下代码，不难发现这一段代码是错误的

max=a[ i][0];
     maxj=0;
     for(j=0;j<M;j++)
       if(a[ i][j]>max)
         {max=a[ i][j];
          maxj=j;
         }

    这段代码想当然地认为可以求出第i行中的最大值及其位置，但其实却不能。这段代码甚至在还没弄清楚“最大”这个词的确切含义的情况下，就自作多情地假设任何一行都存在着最大值。
    顺便要提到的是下面两段代码，

for(k=0;k<N;k++)
       if(max>a[k][maxj])
          {flag=0;
           continue;}

    和

if(!flag)
     printf("It is not exist!\n");

    这两行代码写得很有喜感，仔细阅读一下就会发现。如果看了第一段没有任何感觉说明你的C语言很菜，看了第二段没有任何感觉则说明你的英语言很菜。
    回过头来看程序错误的产生原因，不难发现，虽然直接原因是代码的产生的，但代码的错误来自错误的解题思路，而错误的解题思路则是由于题目本身不清不楚不明不确或是对题目要求理解得不清不楚不明不确造成的。因此要正确地解决这个问题，首先必须明确问题本身是什么？为此将题目更正为
    题目：找出一个二维数组中的鞍点，即该位置上的元素在该行上最大(即大于该行的其他元素)，在该列上最小(即小于该行的其他元素)，输出鞍点位置及其对应的值。如果鞍点不存在输出“没有鞍点”。
    方法也无非是老老实实地一个元素一个元素地检查。

#include <stdio.h>
#define N 4
#define M 5
#define NO 0
#define YES 1
int main( void )
{
  int a[N][M] , i , j , no_saddle_point = YES ;

  printf("请输入%d*%d的二维数组\n", N , M );
  for( i = 0 ; i < N ; i++ )
    for( j = 0 ; j < M ; j++ )
      scanf( "%d" , &a[i][j] ) ;

  for( i = 0 ; i < N ; i++ )
    for( j = 0 ; j < M ; j++ )
      {
         int m , be_max = YES , be_min = YES ;
         for ( m = 0 ; m < M ; m ++ ) //判断a[i][j]是否在该行中最大
           {
               if ( m == j ) //不和自己比较
                  continue ;
               if ( a[i][m] >= a[i][j] ) //有大于等于该元素的元素
                  {
                     be_max = NO ;
                     break ;
                  }
           }

         if( be_max == NO ) //a[i][j]在该行中不是最大
           continue ;

         for ( m = 0 ; m < N ; m ++ ) //判断a[i][j]是否在该列中最小
           {
               if ( m == i ) //不和自己比较
                  continue ;
               if ( a[m][j] <= a[i][j] ) //有小于等于该元素的元素
                  {
                     be_min = NO ;
                     break ;
                  }
           }
         if( be_min == NO ) //a[i][j]在该列中不是最小
           continue ;

         no_saddle_point = NO ; //鞍点存在
         printf("鞍点在第%d行第%d列,值为%d\n",i,j,a[i][j] );
         //return 0;
      }
  if( no_saddle_point == YES )
     printf("没有鞍点\n");
  return 0;
}

    在明确了最大、最小的含义后，不难分析出二维数组确实只可能有0或1个鞍点。因此前面的代码还有进一步优化的可能：找到鞍点后直接退出。实现这一点也非常容易，只要在输出鞍点之后加上一句return 0;就可以了，此时也没有必要定义no_saddle_point这个变量。这里就不再另写一次代码了。