首页 > 技术文章 > 对Alexia(minmin)网友代码的评论及对“求比指定数大且最小的‘不重复数’问题”代码的改进

pmer 2013-10-10 01:09 原文

  应Alexia(minmin)网友之邀,到她的博客上看了一下她的关于“求比指定数大且最小的‘不重复数’问题”的代码(百度2014研发类校园招聘笔试题解答),并在评论中粗略地发表了点意见。

  由于感觉有些看法在评论中无法详细表达,也由于为了更详细地说明一下我的 算法:求比指定数大且最小的“不重复数”问题的高效实现 博文中没有说清楚的一些想法,并给出这个问题更加完美的代码,故制此文。欢迎Alexia(minmin)网友和其他网友指正。

  Alexia(minmin)网友在其博文中对其算法思想描述得很清楚:

1. 给定N是一个正整数,求比N大的最小“不重复数”,这里的不重复是指没有两个相等的相邻位,如1102中的11是相等的两个相邻位故不是不重复数,而12301是不重复数。

算法思想:当然最直接的方法是采用暴力法,从N+1开始逐步加1判断是否是不重复数,是就退出循环输出,这种方法一般是不可取的,例如N=11000000,你要一个个的加1要加到12010101,一共循环百万次,每次都要重复判断是否是不重复数,效率极其低下,因此是不可取的。这里我采用的方法是:从N+1的最高位往右开始判断与其次高位是否相等,如果发现相等的(即为重复数)则将次高位加1,注意这里可能进位,如8921—>9021,后面的直接置为010101...形式,如1121—>1201,此时便完成“不重复数”的初步构造,但此时的“不重复数”不一定是真正的不重复的数,因为可能进位后的次高位变为0或进位后变成00,如9921—>10001,此时需要再次循环判断重新构造直至满足条件即可,这种方法循环的次数比较少,可以接受。

  下面是Alexia(minmin)网友的代码:

// 求比指定数大且最小的“不重复数”

#include <stdio.h>

void minNotRep(int n)
{
    // 需要多次判断
    while(1)
    {
        int a[20], len = 0, i, b = 0;
        // flag为true表示是“重复数”,为false表示表示是“不重复数”
        bool flag = false;

        // 将n的各位上数字存到数组a中
        while(n)
        {
            a[len++] = n % 10;
            n = n / 10;
        }

        // 从高位开始遍历是否有重复位
        for(i = len - 1; i > 0; i--)
        {
            // 有重复位则次高位加1(最高位有可能进位但这里不需要额外处理)
            if(a[i] == a[i - 1] && !flag)
            {
                a[i - 1]++;
                flag = true;
            }
            else if(flag)
            {
                // 将重复位后面的位置为0101...形式
                a[i - 1] = b;
                b = (b == 0) ? 1 : 0;
            }
        }

        // 重组各位数字为n,如果是“不重复数”则输出退出否则继续判断
        for(i = len - 1; i >= 0; i--)
        {
            n = n * 10 + a[i];
        }

        if(!flag)
        {
            printf("%d\n", n);
            break;
        }
    }
}

int main()
{
    int N;

    while(scanf("%d", &N))
    {
        minNotRep(N + 1);
    }

    return 0;
}

  我对这段代码的总体看法是,main()写的很好,因为很短,很容易看懂。

  主要缺点是,main写在了源程序的后面,我个人认为这种风格欠佳——头重脚轻(参见《品悟C》p262,“贪小便宜——省略函数类型声明等问题”)。

  理由是,看文章我们总是先看标题,同样的道理读代码也总是先读main()。把main()置于源代码的后部于人于己都不利于阅读。

  这种写法唯一的好处是可以省写函数类型声明。这是初学者非常喜欢占的一个小便宜。但从长远以及稍微大一些规模的代码来看,这个小便宜微不足道得可以忽略不计。(我记得要么是在我以前发的博文中,要么就是在《品悟C》这本书里详细地讲过这件事。)

  这段代码的另一个缺点是,minNotRep()太大。原因主要是minNotRep()这个函数不但完成了求不重复数,还顺便输出了这个不重复数。这很不好,函数的功能应该单一,而且函数应该越小越好。因此,minNotRep()不应该定义为

void minNotRep(int n);

的形式,更好一些的写法应该是返回不重复数

int minNotRep(int n);

或者

void minNotRep(int *n);

直接把原来的数改为不重复数,然后在main()中再考虑输出。

  事情要一件一件地做,指望一个函数完成所有事情,代码显然不够从容,函数也必然臃肿。
  所以,从整体上来说,代码这样安排为好 

/*
诸函数类型声明:
输入N();
求最小不重复数();
输出();
*/

int main()
{
    int N;

    //输入N();
    //求最小不重复数();
    //输出();

    return 0;
}

/*
诸函数定义:
输入N()
{
}
求最小不重复数();
{
}
输出();
{
}
*/

   再来看minNotRep()函数。

  在这个函数中,首先把n离散,然后将离散后的数字用一数组(int a[20])和数字的位数len表示。这个结构没有问题,很适合从高位到低位找重复数字要求(但是如果是我,则一定会把这两者构造成一个统一的数据结构。为什么?不解释。因为这是常识,)。问题在于这两个变量被放在了while(1)循环的内部,由于它们是局部auto变量,因而意味着每次循环都要重新建立这个数组和len变量。这显然是不妥的。这两个变量应该放在while(1)循环的外部,这样每次循环就不必重新建立这两个变量了。

  与此类似,n的分解离散及合成写在了while(1)循环之内,这就意味着每次循环都必须重新分解再重新合成,这是无意义的多余动作。经与作者沟通交流发现,作者是因为没有很好地处理进位问题才不得不这样处理的。以19901212为例

  首先,分解为 1、9、9、0、1、2、1、2存入数组,

        while(n)
        {
            a[len++] = n % 10;
            n = n / 10;
        }
View Code

   在数组中的顺序是:2 1 2 1 0 9 9 1
  然后从高位到低位找重复数字
  找到之后如果flag为false则加1

        // 从高位开始遍历是否有重复位
        for(i = len - 1; i > 0; i--)
        {
            // 有重复位则次高位加1(最高位有可能进位但这里不需要额外处理)
            if(a[i] == a[i - 1] && !flag)
            {
                a[i - 1]++;
                flag = true;
            }
            else if(flag)
            {
                // 将重复位后面的位置为0101...形式
                a[i - 1] = b;
                b = (b == 0) ? 1 : 0;
            }
        }

   我不得不说,我很不喜欢这个flag,因为除了表现出一种别扭的思维,这里它没有别的用处。(参见flag标志什么?哦,它标志代码馊了 )这段代码完全可以这样写:

        for(i = len - 1; i > 0; i--)
        {
            if(a[i] == a[i - 1] )
            {
                a[i - 1]++;
                break ;
            }
        }
        for ( 从 i-20 )
        {
            // 将重复位后面的位置为0101...形式
         }

无论从逻辑上还是形式上都更为简洁。

  关于这个flag要说的另一件事情是,它是bool类型。这种类型C语言中是没有的(C99中有_Bool类型),作者恐怕是把C语言和C++混为一谈了。国内很多大学生都犯这个毛病,甚至专业程序员中也有很多人C和C++不分。这个错误很广泛,无疑首先是教材或书籍的责任。(参见《品悟C》p4,“C啊,多少C++假汝之名而行——C和C++不分”)

  当然支持C99的编译器可以这样用,但前提是必须

#include <stdbool.h>

才行。可是在代码中我没有发现这条预处理命令。因此bool是误用无疑。

  回到被打断的话题,加1之后,数组中变成了

2 1 2 1 0 10 9 1

  由于作者没有及时处理这个10,所以才不得不在循环体内不断地分解与合成。其实这时只要对数组稍微处理一下,模拟一下进位,将数组改为

2 1 2 1 0 0 0 2

  就用不着反复地分解、合成了。

  紧接着,代码将0 0左侧的数组元素改写成了“0101...形式”:

0 1 0 1 0 0 0 2

  这里的代码有两个问题。的问题是

  第一,

a[i - 1] = b;

  这句我认为是一个BUG。因为前面说的是a[i]与a[i-1]重复(并且有a[i - 1]++;),所以“// 将重复位后面的位置为0101...形式”应该是从a[i-2]而不是a[i - 1]开始改。但  a[i-2]也不对,因为所在循环for(i = len - 1; i > 0; i--)中的 i 最小可以为1,所以a[i-2]存在数组越界的问题。

  第二问题是,由于加1之后重复位前面可能又出现了新的重复位,所以这里的“将重复位后面的位置为0101...形式”几乎是一个无意义的操作。这个动作仅仅是在最后一次才有意义,这就是我不肯接受这种写法的原因。写代码其实和下围棋一样,任何一个高手下围棋绝对不肯走一步显而易见没有用处的“废棋”。反对直接填写“0101...”的另一个原因是,这是人“算”的,不是程序“算”的。程序员的任务是用程序发出命令让计算机去做,而不是越俎代庖地替代程序和计算机。

  我在这里的写法是将重复位后面各个位置上的数字改为0。而且为了不至于反复地进行无意义地重复写0,使用了一点小技巧。这个小技巧,就评论情况来看,目前还没有人看懂。

  好,评论就到这里。下面讲一下我在这里的处理。依然是以以19901212为例,在数组中的顺序是:2 1 2 1 0 9 9 1。

  我首先用 end = 0 这个变量规定了重复位后面改为0的最后一位。

  用b_point = search ( &map )确定最前面的重复位,在这个例子里应该是5 (199) 。然后将199加1,并在数组中模拟了进位(  add_1( &map , b_point ) ; ) ,

   for ( i = from ; i < p_m->top ; i ++ )        //进位处理  
   { 
      p_m->t[i + 1] += p_m->t[i] / 10u ; 
      p_m->t[i] %= 10u ; 
   } 
     
   if ( p_m->t[p_m->top] > 9u )                  //最高位有进位  
   { 
      p_m->t[p_m->top + 1] = p_m->t[p_m->top] / 10u ; 
      p_m->t[p_m->top ++ ] %= 10u ; 
   } 

(顺便说一句,这里的p_m->t[p_m->top ++ ] %= 10u ;一句一直是让我感到有些惴惴不安的,生怕“求道于盲”那样精通C语言的网友提出质疑。)
之后数组变为

2 1 2 1 0 0 0 2

然后将数组中从end到b_point-1的元素改为0(一共5个),数组变为

0 0 0 0 0 0 0 2

  最后再将b_point的值赋给end,由于每次循环修改的是从b_point-1到end之间的元素,这样下次就不会再修改数组最左面那5个元素的值了。

我的失误:

  我的失算之处是,最初也被题目中的“给定任意一个正整数”中的“正整数”三个字给迷惑了。直到写完代码我才意识到,这个题目跟正整数几乎没什么关系。把输入视为一个十进制形式正整数的字符序列,不但完全满足原来问题的要求,而且不限于整数类型的范围限制。为此,重新给出可处理最多100位正整数的代码如下:

#include <stdio.h>

#define MAX 100 
typedef  struct
         {
            unsigned char t[ MAX + 1 ] ; 
            int top ;                //记录第一位数的下标 
         } 
         Map ;

void input( Map * );
void reverse( unsigned char [] , int );
void exchange( unsigned char * , unsigned char * );
void squeeze( Map * );
void find( Map * );
int  search( const Map * );
void add_1( Map * , const int );
void clear( Map * , const int , const int );
void out( const Map * );

int main( void )
{
   Map num ;
   
   input( & num );     //输入正整数 
   add_1( & num , 0 ); //加1 
   find ( & num );     //求不重复数 
   out  ( & num );     //输出 
   
   return 0;
}

void squeeze( Map * p_m )
{
   while ( p_m -> t[ p_m -> top ] == 0 ) 
      p_m -> top -- ;   
}

void exchange( unsigned char * p1 , unsigned char * p2 )
{
   unsigned char c = * p1 ;
   * p1 = * p2 ;
   * p2 = c ;
}

void reverse( unsigned char a[] , int n )
{
   int i ;
   
   for ( i = 0 , n -- ; i < n ; i ++ , n -- )
      exchange( a + i , a + n );

}

void input( Map *p_m )
{
   int c ;
   
   p_m -> top = -1 ;
   
   while ( ( c = getchar () ) != '\n' )
   {
      if ( c < '0' || c > '9' || p_m -> top > MAX )
         break ;

      p_m -> top ++ ;
      p_m -> t[ p_m -> top ] = c - '0' ;      
   }
   
   reverse( p_m -> t , p_m -> top + 1 );//颠倒次序 
   
   squeeze( p_m ); //去掉开头的0 
   
}

void clear( Map * p_m , const int from , const int to )
{
   int i ;
   
   for ( i = from - 1 ; i > to - 1; i -- )
      p_m->t[i] = 0u ;
}

void add_1( Map * p_m , const int from )
{
   int i ;
   
   p_m->t[from] ++;                             //最低位加1 
   
   for ( i = from ; i < p_m->top ; i ++ )       //进位处理 
   {
      p_m->t[i + 1] += p_m->t[i] / 10u ;
      p_m->t[i] %= 10u ;
   }
   
   if ( p_m->t[p_m->top] > 9u )                 //最高位有进位 
   {
      p_m->t[p_m->top + 1] = p_m->t[p_m->top] / 10u ;
      p_m->t[p_m->top ++ ] %= 10u ;
   }
}

int  search( const Map * p_m )
{
   int i ;
   
   for ( i = p_m->top ; i > 0  ; i-- )
   {
      if ( p_m->t[i] == p_m->t[i-1] )
         break ;
   }
   
   return i - 1 ; 
}

void find( Map * p_m )
{
   int end = 0 , b_point ;
   
   while ( ( b_point = search ( p_m ) ) > -1 ) //为-1时说明不是不重复数 
   {
      add_1( p_m , b_point );                 //重复数部分加1 
      clear( p_m , b_point , end );           //后面改为0 
      end = b_point ;                         //确定下次循环的处理范围 
   }
}

void out( const Map * p_m )
{
   for (int i = p_m -> top ; i >= 0 ; i -- )
      printf( "%u" , p_m -> t[i] );
      
   putchar('\n');            
}

 

推荐阅读