C语言名题精选百则——序曲

 

C语言名题精选百则——序曲

 

尊重他人的劳动，支持原创

从本篇博文开始，D.S.Qiu（以后就这么称呼自己了）将对《C语言名题精选百则》进行整理推出，不光只是书上的名题，还会依据互联网的资源进行不断补充，加强。等全书各个章节都整理完，会做一个总汇。如果你有建议、批评或补充，请你不吝提出（email:[e-mail]，或者直接在本文末评论）。你的支持和鼓励，我将渐行渐远！

终于完成《C语言名题精选百则——序曲》这篇博客了，这系列的每个问题都尽量会有【题目说】【解答】【问题实现】【习题】，如果可以的话，还会有【算法改进】这个分块（如问题1.1最长平台的算法改进，个人觉得还是很不错的），《序曲》主要是介绍了关于有序数组的5个问题（点击查看更多数组和字符串问题），相对简单，但是要是尽善进美还有待不断的挖掘。下一篇是《数字问题》（其实就是数论的一些问题），更多关注：http://dsqiu.iteye.com。

 

问题1.1最长平台（PLATEAU.C )

 

已知一个已经从小到大排序的数组，这个数组中的一个平台（Plateau)就是连续的一串 值相同的元素，并且这一串元素不能再延伸。例如，在1，2，2,3,3,3,4,5,5，6中1,2.2,3.3.3,4,5.5,6 都是平台。试编写一个程序，接收一个数组，把这个数组中最长的平台找出来。在上面的 例子中3.3.3就是该数组中最长的平台。

 

【说明】

这个程序十分简单，但是要编写好却不容易，因此在编写程序时应该考虑下面几点：

(1)使用的变量越少越好。

(2)能否只把数组的元素每一个都只查一次就得到结果？

(3)程序语句也要越少越好。

 

【问题实现】

int longest_plateau(int x[], int n)
{
     int  length = 1;         /* plateau length >= 1.     */
     int  i;

     for (i = 1; i < n; i++)
          if (x[i] == x[i-length])
               length++;
     return length;
}

 

【算法改进】

如果不考虑题目说明中的条件限制，可以对该算法进行改进。

这里先给出参考②的改进方法，改进这个算法主要是能够减少比较，那就只有可能是依据当前的长度leng进行跳跃。

最长平台有一些特点可以利用，从而使得算法的效率更高。 

一个分界点元素指该元素和它的前一个元素不相等。 

1） 从一个分界点开始剩下的元素个数<=length，则可以直接返回。 

2） 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该点（分界点的坐标+length）的元素进行查找。 

   如果点（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的元素可以丢掉，从新的分界点重新开始查找最长平台。 

   如果点（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。 

这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。

参考Eastsun的代码：

int longest_plateau(int x[],int n)
{
           if(n== 0) return 0;
           int length = 0;
           int start = 0;
           while(start + length< n)
          {
               start += length;
               int elem = array[start];
               if(array[start - length] != elem)
               {
                   for(;array[start - 1] == elem;start --);
                   continue;
               }
               for(;start < n && array[start] == elem;length ++,start ++);
           }
           return length;
       }

 

下面给我的改进思路：当我看到“已经排好序”，就想迫不及待用分治思想进行二分查找，当然避免重复比较和尽可能的跳跃（只有牺牲空间），当分治递归长度（end-begin）<length 的时候可以直接跳过（这是一个改进），还有可以减去从中间开始比较的工作，这样理论的时间复杂度的上限就是O(clogn)，其中c是最长平台的长度，实际效率应该是提高不少的（用了一些空间）。实现参考连续子数组最大和的分治策略求解。

【习题】

（1）改写程序，指出最长平台的位置。

（2）在（1）的基础上把所以平台和它的位置都找出来。

（3）如果给定的数组没有排好序，请写一个程序找出最长平台，程序还能够有O(n)的时间复杂度吗，为什么？

针对（3）给出我的想法：没有排好序，其实有点类似求最长重复子串（另一篇博客有讲解），只是这里是最长重叠子串。 

 

问题1.2支配值数目（GT_COUNT.C )

已知f[]与g[]两个整数数组，元素都已经从小到大排列，试编写程序算出f[]中每一个元素比g[]中元素大的个数的总数。换句话说，f[0]比g[]中多少个元素大、f[i]比g[]中 多少个元素大等，这些值的总和就是所要求的答案。

例如，如果f[]中有1，3，5，7,9,而g[]中有2,3，4，7,8,比g[0]大的有f[l]〜f[4],比g[l] 大的有f[2]〜f[4],比g[2]大的有f[2卜f[4],比g[3]大的是f[4],比g[4]大的是f[4]，因此 答案是 4+3+3+1+1=12。

【说明】

与问题1.1 一样，需要特别注意数组f[]与g[]已经排序。如果问题1.1能够做出完美的解答，那么本题也不难，相似的方法就可以得到高效率的程序。

【解答】

这个题目的诀窍在于：当发现f[i]>g[j]时，f[i],f[i+1],...,f[m-1]都会大于g[j]，因为f[]是从小到大排序的（充分利用这个性质），所以当f[i]>g[j]时，比g[j]大的f[]元素有m-i个。

于是程序就从f[0]与g[0]比起，在比较过程中只有两种情况需要处理：

(1) f[i]<=g[j]：既然f[i]小于等于g[j]，可试着用f[i+1]来比较。换言之，f[]的脚码（下标）加上1。

(2) f[i]>g[j]：这是满足要求的部分，所以在f[]中就有m-i个元素比g[j]大；接着比较f[i]与g[j+1]，看看f[i]是否比g[j]的下一个元素大。换句话说，把g[]的脚码加上1。 当玎]或g[]没有元素了，就可以停止工作。如图10-2所示就是比较数组f[1,3,5,7,9]与g[2，3，4，7，8]的情况，中间横线指出进行比较的元素。

 

【问题实现】

int  dominance_count(int f[], int g[], int m, int n)
{
     int  index_f, index_g;
     int  count;

     count = index_f = index_g = 0;
     while (index_f < m && index_g < n)
          if (f[index_f] <= g[index_g])
               index_f++;
          else
               index_g++, count += m - index_f;
     return count;
}

【习题】

（1）请证明这个程序最多只会比较2n次，如果f[]和g[]都有n个元素。

（2）如果f[]和g[]有相同元素这个程序还正确吗？为什么？

（3）修改程序把g[]中小于每一个f[i]的元素都显示出来。

问题1.3等值数目(EQ_COUNT.C )

已知两个整数数组f[]与g[]，它们的元素都己经从小到大排列好，而且两个数组中的 元素都各不相同。例如，f[]中有1,3,4,7,9，而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。

就上例而言，f[l]与g[0]为3是第一组；f[3]与g[2]为7是第二组。

【说明】

建议不要使用下面的方法来编程：

(1)固定f[i]。

(2)对于f[i]而言，检查g[]中是否有与f[i]相同的元素。 ‘

(3)处理下一个f[i],即f[i+1]。

因为f[ ]与g[]都已经从小到大排列好，所以应该活用这一个很强的特性。一个好的程 序员绝对不应用上面的笨拙方法来编写程序，这样会做太多无意义的事。

为什么呢？因为g[]的元素都相异，对于f[i]而言，最多只会找出一个与它相同的元素, 最坏的情况是把g[]全部查完才找出相同元素（如果采用上面的方法)，如果g[]中有n个 元素，需要查n次；但是若f[]中也有n个元素，那么需要把g[]查n遍,一共作n²次比较 才能找出结果。

试着找出一种方法，把ft[]与g[]各查一次就可以得到答案（记住，活用f[]与g[]已经从小到大排列的特性）。

做完这一题后，建议继续做下一题。

【解答】

当比较f[i]与g[j]时，不外乎有下面3种情形之一：

(1) f[i]<g[j],于是f[i]与g[j]就不是相等的一对，如果在fl]中有与g[j]相等的元素， 那么一定在f[i]的后面，亦即是f[i+1]，f[i+2]，…之一，所以下一次应该比较f[i+1]与g[j]。注 意：f[]与g[]都已从小到大排好才有此结论。

(2) f[i]>g[j],同理，下一次应该比较g[j+1]与f[i]。

(3) 这样就找出了相等的一对，下一次应该比较f[i+l]与g[j+l]。注意： 因为f[](或g[]中的元素都相异，才有这样的结论。

程序中coincidence_cmmt()函数接收f[]与g[]两个数组，把相同的元素对应的数目当成 函数值返回来；index_f与index_g就分别是f[]与g[]数组的脚码；count变量是用来计算到目前为止有多少对是相同的。

注意，f[]与g[]中的元素都只查一次，虽然在查的时候可能比较不止一次；但是不论 如何，f[]与g[]中的元素被拿来比较的总次数绝对不超过2n次，为什么？自己想一想。所 以，这是一个效率很高的方法。

【问题实现】

int coincidence_count(int f[], int g[], int m, int n)
{
     int  index_f, index_g;   /* subscripts for f and g   */
     int  count;              /* equal pair counter       */

     count = index_f = index_g = 0;
     while (index_f < m && index_g < n) 
          if (f[index_f] < g[index_g]) /* if f[] is less  */
               index_f++;              /* then move f     */
          else if (f[index_f] > g[index_g]) /* if f[] >   */
               index_g++;              /* then move g     */
          else
               count++, index_f++, index_g++; /* EQUAL    */
     return count;
}

【习题】

(1)请修改程序，把相同的元素的脚码显示出来。

(2)如果f[]或g[]中有相同的元素，但仍然是从小到大排列，这个程序还能正常运 行吗？问题何在？修改程序，使得可以处理这个问题。例如，如果ft ]是1，3，3，5，7而g[]是 1，3，3，8，9，于是就有 4 对 3 是相同的：f[0]与 g[0]，f[l]与 g[l]，f[l]与 g[2], f[2]与 g[1]。程 序的效率还是一样好吗？

(3)为什么一方的元素用完了就可以停止工作呢？

(4)请证明这个程序的比较次数绝对不会超过2n次，n是f[]与g[]中的元素个数。 

问题1.4两数组最短距离(MINDIST.C )

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值中最小的一个数，此值称做数组的距离。

【说明】

如果x[i]与y[j]是两个元素，那么lx[i]-y[j]l就是这两个元素之间的距离,所有填些距离 的极小值，称为数组的距离。比如说x[]有1，3，5，7，9，y[]有2，6，8，那么最短距离是1， 因为x[0]与y[0]、x[1]与y[0〗、x[2]与y[1]、x[3]与y[l]，还有x[4]与y[2]的距离都是1。

注意，如果x[]与y[]各有m与n个元素，那么元素之间的距离就一共有m*n个；事实上往往用不着这么多个值，应该活用对x[]与y[]已经排列好的特性，不要把所有的距离都算出来。

【解答】

注意一点，如果x[i]与y[j]的距离是d,而且x[i]>y[j],那么排在y[j]前面的元素与x[i] 的距离一定大于d。为什么呢？如果y[k]排在y[j]前面，则y[k]<y[j],因此就得到d=x[i] -y[j] <x[i]-y[k]。

当程序运行的过程中发现了 x[i]>y[j]，就可以确定i而不断增加j,于是距离就会越来 越小，一直到会变成y[k]>x[i]为止。但是，反过来，又可以固定k而一直增加i，距离又会下降，程序就是这样写成的。

引入文件<limits.h>中的INT_MAX指出int类型的极大值，用它来定出变量minimum的初值。

【问题实现】

#define  min(x, y)     ((x) < (y) ? (x) : (y))

int  min_distance(int x[], int y[], int m, int n)
{
     int  minimum = INT_MAX;  /* INT_MAX is from limits.h */
     int  index_x = 0, index_y = 0;

     while (index_x < m && index_y < n)
          if (x[index_x] >= y[index_y]) {
               minimum = min(minimum, x[index_x]-y[index_y]);
               index_y++;
          }
          else {
               minimum = min(minimum, y[index_y]-x[index_x]);
               index_x++;
          }
     return minimum;
}

【习题】

(1)这个程序可以写成函数来帮助解下一个相等的前置和与后置和的问题，虽然解法不会很好。请改写程序试一试。

(2)如果有一个数组没依顺序排列，程序还能正常工作吗？如果两个都没排好又如何 呢？请克服这个问题。

(3)请修改程序，找出造成最短距离的那两个元素的位置与它们的值。

(4)本题程序中的if段落与else都有两行叙述，如果分别把index_x++与index_y++ 写到它上面设定的叙述中，会有相同的结果吗？

 

问题1.5等值首尾和(HEADTAIL.C )

假设有一个数组x[],它有n个元素，每一个都大于零；称x[0]+x[1]+…+x[i]为前置和(Prefix Sum),而 x[j]+xlj+1]+…+x[n-1]为后置和（Suffix Sum)。试编写一个程序，求出 x[]中有多少组相同的前置和与后置和。

【说明】

如果x[]的元素是3,6,2,1,4,5,2,于是x[]的前置和有以下7个，即3,9,11,12, 16,21,23；后置和则是2，7,11，12，14，20,23;于是11、12与23这3对就是值相同的前置和与后置和， 因为：

11=3+6+2 (前置和）=2+5+4 (后置和）

12=3+6+2+1 (前置和）=2+5+4+1 (后置和）

由于23是整个数组元素的和，因此前置和与后置和一定相同。

当然，也可以用上面的方法把前置和与后置和都先算出来（两者都是从小到大的递增 序列，为什么？），再进行比较，但建议不要使用这种方法，因为它需要额外的内存。

【解答】

既然不用额外的数组，前置和与后置和又不能省略而不算，就只能用两个指针，一个 指针从头到尾走，并且记录下到目前为止的前置和；再用另一个指针从尾到头走，并且记 录下到目前为止的后置和。接着，比较目前的前置和与后置和，如果相等，就得到了一组， 然后增加往后走的指针，降低往回走的指针，继续工作。如果前置和大于后置和，这就表 示要增加后置和才能比较长短，所以就降低往回走的指针，更新后置和，再继续；至于后 置和大于前置和的情况则是相对称的，就省略了，请自行阅读程序。

【问题实现】

int  head_tail(int  x[], int n)
{
     int  prefix     = 0, suffix     = 0;
     int  prefix_idx = 0, suffix_idx = n-1;
     int  count = 0;

     while (suffix_idx >= 0 && prefix_idx <= n-1)
          if (prefix < suffix)      /* prefix too small   */
               prefix += x[prefix_idx++];
          else if (prefix > suffix) /* suffix too small   */
               suffix += x[suffix_idx--];
          else {                    /* get an equal pair: */
               count++;             /* increase count and */
               prefix += x[prefix_idx++]; /* advance pref.*/
               suffix += x[suffix_idx--]; /* and suffix   */
          }
     return count;
}

【习题】

(1)这个程序要求所有元素都大于零，是否有此必要？如果没有这个条件，程序还能 运行吗？如果可以，请证明它；如果不行，请改写程序。

(2)请改写程序，把造成前置和与后置和相同的指针连同这个相等的值一并显示出来。

参考：

①C语言名题精选百则技巧篇 冼镜光编著 第一章

②zhang_xzhi_xjtu： http://zhang-xzhi-xjtu.iteye.com/blog/506185