C语言名题精选百则——查找

 

 

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

本篇博文，D.S.Qiu将对《C语言名题精选百则——排列，组合和集合》进行整理推出，不光只是书上的名题，还会依据互联网的资源进行不断补充，加强。等全书各个章节都整理完，会做一个总汇。如果你有建议、批评或补充，请你不吝提出（email:[e-mail]，或者直接在本文末评论）。你的支持和鼓励（一个人整理真的很累，几度想放弃），我将渐行渐远！

《排列，组合和集合》主要是介绍了关于有序数组的几个问题，相对简单比较好能理解（点击查看更多数组和字符串问题），主要是对效率的改进，但是要是尽善进美还有待不断的挖掘。下一篇是《排序》（其实就是数论的一些问题），更多关注：http://dsqiu.iteye.com。

问题4.1寻找脚码(ISEARCH.C )

 

已知一个整数数组x[]，其中的元素彼此都不相同，而且也已经从小到大排列好。请用 比较大小、相等的方式编写一个程序，找出给定的数组中是否有一个元素满足x[i]=i的关系。举例而言，如果x[]={-2，-1，3，7，8}, x[3]=3,因此3就是答案。

 

【说明】

用笨方法，一个循环就可以找出答案，如程序4-1所示。

 

【程序】

 

程序4-1

for (index = -1, i=0; i<n, i++)

if (x[i] == i) {

index = i; break;

}

if (index >= 0)

printf("\nFound at x[%d]", index);

else

printf ("\nNot Found")

 

这个程序在最坏的情况下，for —共绕了 n圈，作了 n次比较，但却没有用到x[]的元素已经排列好的条件。事实上，如果输入有n个元素，应该可以写出与log2n次成正比的比较的程序，关键是X[]的元素是排好顺序的。

 

 

【解答】

如果要在一个己经排列好的数组中查找元素，那多半会用到二分查找法，不过这个题 目有点不一样，因为“不知道”要找的数据的值，因此要有点变化才行。首先，要注意两 种情况：

(1)如果x[i]>i,那么对于比i大的任何一个脚码k而言，都会得到x[k]>k,因此 一旦发现了某个i满足x[i]>i时，满足x[j]=j的j就一定只会发生在j<i的所在。

(2)如果x[i]<i,那么对于比i小的任何一个脚码k而言，都会得到x[k]<k,于是 一旦发现了某个i满足x[i]<i时，满足x[j]=j的j就一定只会发生在j>l的所在。

基于上述两种情况，程序就可以找出中间的元素，令它的脚码为middle,比较x[middle] 与middle是否相等，相等的话就找到解答方法了。如果不相等，就看x[middle]>middle 是否成立，如果成立， 那么满足x[i]=i就一定在middle的左边；反之，则在右边。所以这 是一个标准的二分查找法（Binary Search)的变形。

程序要作多少次比较呢？在while中每一个循环都比较两次，一次比相等，一次比大 于。在最坏的情况下，while —共会绕log2n圈，因为每一次要查找的部分都减半，所以总

共会用21og2n次比较。这一项分析与二分查找法完全相同，肯定会比在问题说明中的方法快。

 

 

【问题实现】

 

int  index_search(int x[], int n)
{
     int  first = 0;
     int  last  = n-1;
     int  middle, index;

     index = -1;
     while (first <= last) {  /* a modified binary search*/
          middle = (first + last) / 2;
          if (x[middle] == middle) {
               index = middle;
               break;
          }
          else if (x[middle] > middle)
               last = middle - 1;
          else 
               first = middle + 1;
     }
     return index;
}

 

【习题】

(1)请证明上述的两种情况。

(2)这个程序是基于数组中元素完全相异的前提下做出来的，请问当有重复的元素， 但仍然从小到大排好时，这个程序还能够正常运行吗？为什么？如果不能正常运行，请改 写这个程序。 

 

 

问题4.2寻找固定的和（FIXSUM.C)

 

有两个数组x[]与y[],各有m与n个元素，而且各个元素并没有依顺序排烈；且d是 一个已知的值。编写一个程序，看看在对x[]与y[]中有没有满足x[i]+y[j]=d的元素。例如，若 x[]={3,7，2,4}，y[]={1,5,2,3}, d 为 9;那么 x[1]+y[2]与 x[3]+y[1]都合乎条件，亦即都是 9。

 

【说明】

当然，一个初学者很可能会编写出如程序4-2所示的程序。

程序4-2

for (i = 0; i < m; i + +}

for (j = 0; j<n; j++)

if (x[i] + y[j] ==d)

return ;

但是这不是一个好程序，因为在最坏的情况下（也就是根本不会有x[i]+y[j]==d的i与 j时)，一共要比释m*n次，因为每一个x[i]与每一个y[j]都相加，与d相比，当m与n很大时，这样写法的效率是很慢的。

因此,要求写一个次数少于m*n次的程序。

【解答】

解题的关键还是在二分查找法，但是因为两个数组都没有依顺序排列，要选其中之一排好才行。假设x[]已经排好，排x[]—般要用cmlog2m次比较，在此c是一个与m无关的常数。排好之后，对于任何一个y[j]而言，都可以在x[]中查找有没有d-y[j]这个数了，如果找到了某个x[i]=d-y[j]，那么就有x[i]+y[j]==d的关系。因为x[]有m个元素，对于 每一个y[j]而言，在x[]中的二分查找法要用log2m次比较，但很可能所有y[j]都比较后才 能得到根本没有x[i]+y[j]==d成立的结论，这就一共比较了 nlog2m次。加上排序的比较次 数,就一共比了 (cm + n)log2n次。一般而言，当m与n比较大时，m • n也会比(cm + n)log2m 大，所以此程序的效率要比一般的写法高。

【问题实现】

#define  YES   1
#define  NO    0

void  sort(int [], int);

int fix_sum(int x[], int y[], int m, int n, int given)
{
     int  first;
     int  last;
     int  middle;
     int  i;

     sort(x, m);              /* sort array x[]           */

     for (i = 0; i < n; i++)  /* for each y[j], do a bin. */
          for (first=0, last=m-1; first <= last; ) {
               middle = (first + last)/2;
               if (x[middle] + y[i] == given)
                    return YES;
               else if (x[middle] + y[i] > given)
                    last  = middle - 1;
               else
                    first = middle + 1;
          }
     return NO;
}


/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>

void main(void)
{
     int  x[] = { 3, 7, 1, 2, 9, 4, 5};
     int  y[] = { 4, 2, 0, 3, 2, 7, 1, 9, 8};
     int  m   = sizeof(x)/sizeof(int);
     int  n   = sizeof(y)/sizeof(int);
     int  data, i;
     char line[100];

     printf("\nFixed Sum Search Program");
     printf("\n\nGiven Array #1 :");
     for (i = 0; i < m; i++)
          printf("%4d", x[i]);
     printf("\n\nGiven Array #2 :");
     for (i = 0; i < n; i++)
          printf("%4d", y[i]);

     printf("\n\nFixed Sum to be searched --> ");
     gets(line);
     data = atoi(line);

     if (fix_sum(x, y, m, n, data) == YES)
          printf("\nYES!, there is a pair summing up to %d", data);
     else
          printf("\nNO! no such sum exits");
}

 

【习题】

(1)如果也将y[]排序，比较的次数会不会降低？为什么？

(2)程序fix一sum()只报告有没有x[i]+y[j]==d这样的条件成立而已，请修改程序，连 同满足上述关系的i与j都显示出来。

(3)请修改程序，找出所有满足x[i]+y[j]==d的i与j。请问在这一要求下，比较次数 有没有增加？换言之，程序效率是否降低？

问题4.3无限式査找（ INF—SRCH.C)

已知一个数组，元素个数有多少并不很清楚，但是数组元素已经依顺序从小到大排好， 而且在数组最后添加了足够多的记号；表示最大的值，比数组中每一个元素都大，而且个数足够多。编写一个程序，在这个数组中找出某个给定的值。

【说明】

因为并不知道数组中有多少个元素，所以虽然数组中元素已经依顺序排列好，也不能套用二分查找法（Binary Search)。不过，二分查找法仍然是最有效率的、在已排好顺序的数组中查找数据的方法。请问，有没有办法克服有关不知道有多少元素的限制呢？

还有一点很重要，很可能不知道那个∞的值究竟是多少；惟一可以确定的就是∞比每一个数组中的值都大，不一定是该类型的最大值。例如，如果数组中的元素是int类型，它 可能是1，3，5，7，9，50，50，50，…，于是50在此就具有∞的作用。

提示：二分法还是可以用的，不过关键是要如何运用它，为了方便起见，假设∞正是该类 型最大的值。

【解答】

在使用二分查找的技巧时，要有左边的边界到右边的边界。当然，如果输入值是放在数组中，左边的边界是0，但右边就不知道了。不过因为数组在最后是放了一连串所以很多人就想到一个方法，从头查到尾，想要找出∞这个值。但这很危险：第一，不知道的的真正的值为何，只知道它比数组中其他数都大，所以没有办法确定如的位置；第二，纵使有办法认出∞，比如它在第k个位置，因而就对0与k这一段数据进行二分查找，但是这可能会浪费时间，因为数组中不是∞的元素可能十分多。

在此提供一个做法,它并非是最好的，但效率却与二分查找法相当。第一步是找出一个合理的、距离不太长的范围给二分查找法使用。想法是这样的，先看给定的值GIVEN是

否是x[0],如果不是，就去查x[1]与x[2]，如果不在这个范围中，则查x[3]〜x[6],若还不 在，再查x[7]〜x[14]…。换句话说，永远在[start,end)这个区间中查有没有GIVEN，因为

x[]是排好的，这相当于x [start] <= GIVEN && GIVEN < xtend]。如果不在，就把范围推到end开始的区域。这些区域的长度自1 = 2G起，长度分别为2、 2^2、2^3、2^4等，所以查找的范围愈来愈大。在程序中，bound()函数就做这样的工作，用delta表示区间中元素的个数，start是左边起点，而end则是终点的下一个，所以用的区间 是[start,end)，而不是[start，end]。很自然地，如果start已知，end就是start+delta。在一开始时，start是0, delta是1,因此范围是[0，1)。接下来，delta要加倍，因此自己相加，再 把start移到end的位置，这就是下一个区间了。可以一再重复，直到[start,end)中包含了GIVEN为止。因为∞比所有的数都大，所以这一定可以做得到，除非GIVEN比∞还大， 但这样就没有意义了。

【问题实现】

#define  NOT_FOUND   -1

/* ------------------------------------------------------ */
/*                  function prototypes                   */
/* ------------------------------------------------------ */

void  bound(int [], int, int *, int *);
int   search(int [], int, int, int);

/* ------------------------------------------------------ */
/* FUNCTION inf_search :                                  */
/*    The control routine.                                */
/* ------------------------------------------------------ */

int  inf_search(int x[], int GIVEN)
{
     int  left, right;

     bound(x, GIVEN, &left, &right);        /* dound      */
     return search(x, GIVEN, left, right);  /* then search*/
}

/* ------------------------------------------------------ */
/* FUNCTION bound :                                       */
/*    Given a sorted infinite array and a key GIVEN, this */
/* function returns two subscripts, namely start and end, */
/* which bound the given key.                             */
/* ------------------------------------------------------ */

void  bound(int x[], int GIVEN, int *start, int *end)
{
     int  delta = 1;          /* interval length          */

     *start  = 0;             /* starting from the 1st pos*/
     *end = *start + delta;   /* interval ends before *end*/
     while (!(x[*start] <= GIVEN && GIVEN < x[*end])) {
          delta += delta;     /* if [start,end) can not   */
          *start = *end;      /* bound, then double length*/
          *end   = *start+delta; /* and try again.        */
     }
     (*end)--;                /* returns the true bound   */
}


/* ------------------------------------------------------ */
/* FUNCTION search :                                      */
/*    The traditional binary search function.             */
/* ------------------------------------------------------ */

int  search(int x[], int GIVEN, int low, int high)
{
     int  mid;

     while (low <= high) {
          mid = (low + high)/2;
          if (GIVEN < x[mid])
               high = mid - 1;
          else if (GIVEN > x[mid])
               low = mid + 1;
          else 
               return mid;
     }
     return NOT_FOUND;
}


/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>          /* for atoi()               */
#include  <limits.h>          /* for INT_MAX              */

void main(void)
{
     int  number[30] = {   1,   3,   5,   8,  10, 
                          21,  25,  50,  67,  68,
                          70,  84, 100, 130, 150, 
                         151, 170, 180, 200, 300,
                         459, 480, 499, 503, 555,
                         570, 623, 699, 784, 981};
     int  input[100];
     int  i, key, answer;
     char line[100];

     for (i = 0; i < 30; i++)
          input[i] = number[i];
     for (i = 30; i < 100; i++)
          input[i] = INT_MAX;

     printf("\nInfinite Search Program");
     printf("\n=======================");
     printf("\n\nGiven Infinite Sorted Array :");
     for (i = 0; i < 100; i++) {
          if (i % 15 == 0) printf("\n");
          if (input[i] < INT_MAX) 
               printf("%4d", input[i]);
          else
               printf(" inf");
     }
     printf("\n\nYour Search Key Please --> ");
     gets(line);
     key = atoi(line);

     if ((answer = inf_search(input, key)) >= 0)
          printf("\nKey found at position %d", answer);
     else
          printf("\nKey NOT FOUND!");
}

【习题】

(1)另一个常见的写法是在bound()函数中用Fibonacci数1,1，2,3，5，8，13，…，而不是

1,2^1,2^2,2^3,请把程序改成这个做法，看看程序效率有何差异。

(2)如果数组中有n个元素，请问这个程序一共作了多少个比较？

(3)为了方便起见，把~定成该类型的极大值，如果-只是比数组中每一个元素都大, 而又不知道这个值是多少，这个程序还輯够正常运行吗？为什么？如果不能，用什么方法 克服?程序效率会不会大打折扣？请举一个程序不能正常运行的例子（如果程序真的不能正考运行的话)。

(4)如果薮组中除了之外，其他元素都不相同；在这种情况下有没有办法找出~的 值是卄么？需要很多次比较吗？请在这个条件下重做第（3)题。 

问题4.4寻找扱小值（CYCLEMIN.C )

一个数组是以循环顺序排列的，也就是说在数组中有某个元素i,从Xi开始有这样的的关系，X0<X1<X2<…<Xi-1<Xi<…<Xn<X0。例如，8,10,14,15,2,6 这 7 个元素就是循环顺序排列的，因为从2开始为递增，到了最后一个元素就转换为第1个元素，再 依顺序递增。换句话说，如果把Xi,Xi+1，…，Xn取出，并且接到数组开头，于是就是一个从小到大的顺序（这不是个旋转的动作吗？）。编写一个程序，接收一个以循环顺序排列的数组，把它的极小值找出来，以上面数据为例，程序应该会输出2

【说明】

因为从X()起顺序是递增的，一直到极小值出现，马上就会出现相反顺序，于是很多人 马上就会想出这个做法：

for ( i = 1 ； i < n && x [i ] >-=x [i-1 ] ; i + +)

一旦这个循环停下来了，如果i等于n那就表示每一个元素都大于在它前面的那一个, 因而极小值为x[0];但若i<n,且x[i]<x[i-l],因此极小值为x[i]。

这是个正确的做法，但效率却不够高，因为在最坏的情况下可能要做n-1次的比较。 不过，这个数组严格说还是有顺序性的，根据这一特性应该可以找出更好、更快的方法， 不妨试试看。

【解答】

解决的办法还是二分查找法，也许会质疑这个数组并没有完全依顺序排列。不错，但不要以为二分查找法只能做那么一点事，事实上，只要能够把问题剖成两部分，而有办法判定解答在其中的一部分的话，这就是个二分查找法。例如，现在处理XL与XM之间的元素（含两个端点），取中间元素XM，M = (L + R)/2。于是就会出现下面两种情况：

(1) xL<=xM：换句话说，xM比左边的元素大，因为从左到右是递增的，一直到极小值出现才不升反降，但xL<=xM明确指出；xL到xM是递增，因而极小元素不会在L与M之间，因此下一个L就是M +1。

(2) xL>xM：因为从xL起是递增，一直到极小值出现才会降下来，然后自极小值起才再度上升，而且XL>=XR。现在有XL>Xm,这表示L与M中一定有极小值才会出现这个现象，所以下一个R是M。就这样一直反复，总会出现L=R的时候，于是\就是极小值，L就是它的所在。

在程序CYCLEMIN.C中，left、right与mid分别取代此地为L、R与M,而且cyclejnin() 函数只返回极小值的脚码，而不是返回极小值，所以要找出极小值，就要用该脚码取出数 组中对应的元素。

【问题实现】

int  cyclic_min(int  x[], int n)
{
     int  left  = 0;
     int  right = n - 1;
     int  mid;

     while (left < right) {        /* if there is a gap : */
          mid = (left + right)/2;  /* get the middle item */
          if (x[mid] < x[right])   /* if < the right most */
               right = mid;        /* then chop right part*/
          else                     /* if >= the left part */
               left  = mid + 1;    /* then chop right part*/
     }
     return left;                  /* answer is the item  */
}

/* ------------------------------------------------------ */

#include  <stdio.h>

void  main(void)
{
     int  x[] = { 20, 23, 28, 35, 39, 40, 42, 8, 10, 15, 17, 19};
     int  n   = sizeof(x)/sizeof(int);
     int  loc, i;

     printf("\nFind Cyclic Minimum");
     printf("\n===================");
     printf("\n\nGiven Array Sorted in Cyclic Fashion :\n");
     for (i = 0; i < n; i++)
          printf("%3d", x[i]);
     
     loc = cyclic_min(x, n);
     printf("\n\nMinimum is located at x[%d] = %d", loc, x[loc]);
}

 

【习题】

(1)在程序中只要加一行叙述就可以找出最大值，再加一行叙述则可以求出中位数，请试试看。

(2)请证明极小值永远在xL与xR之间。

(3)程序一共作了多少次比较，请求出一个确切的公式。

问题4.5两个数组的中位数（MEDIAN2.C )

已知两个数组x[]与y[]，各有n个元素，并且也已经以从小到大的顺序排好，编写一 个程序，用少于n次比较找出x[]与y[]合并后的中位数。

【说明】

因为x[]与y[]都已经排好，而且各有n个元素，因此一般最自然的想法就是把x[]与 y[]做合并的工作，一直合并到得出第a个元素时，这就是中位数了，这一共会用n次比较。 注意，为方便起见，把中位数定成在中间的两个及其中之一，这是个方便的定义，因为x[] 与y[]合起来有2n个元素,因此真正的中位数的定义应该是第n与第n+1个元素的平均数； 所以为了方便，只要求找出第n个或第n+1个元素即可。

上面提到的，用合并的方法会用到与II成正比的比较次数，并不是所期望的做法，所希望的，是要比n少很多的做法。可能会想到的改善是：因为x[]与y[]是排好的，可以用 x[]的中间元素，例如x[mid]，通过二分查找法找出它在y[]数组中的位置，例如：

y[i] < x [mid] < y [i + 1]

所以在合并起来之后，x[mid]前面的元素就有mid+i+1个，如果这个值大于n,那么中位数就必定在这mid+i+1个元素内，因此x[mid+l]〜x[n-1]，y[i+1]〜y[n-1]都可以去掉，接着在x[0]〜x[mid]，y[0]〜y[i]之间找中位数就行了。但若mid+i+1比n小，在合并起来后中 位数在元素多的那一半，所以把x[0]〜x[mid]，y[0]〜y[i]去掉，而在x[mid+1]〜x[n-1]，y[i+1]〜x[n-1]之间找中位数。反复这个过程，就不难找出中位数了。需要多少次比较呢？大约与 (log2n)^2成正比，道理为何请读者自己证明。

事实上，问题还可以做得更好，而且也不必那么复杂，在与log2n成正比的比较次数

之下就可以找出中位数的。

【解答】

其实在问题说明中的(log2n)2方法已经差不多可以说是涉及到重点所在了，它之所以 到不了 log2ii的境界，是因为每次所去掉的、不可能包含了中位数的元素个数不够多。为了要去掉足够多的、不适合的元素，要把那个办法动一点手脚才行。想法是，一次要去掉 将近一半的元素（就像是二分搜寻法一样），大约log2n次之后，就可以得到结果了。

首先，拿x[mid_x]与y[mid_y]这两个在x[]与y[]中央的元素比较。如果x[mid_x]比 y[mid_y]小，那么在合并后的结果中x[mid_x]就排在y[mid_y]前面，而且中位数一定在这 两者之间。原因是在x[]中，在x[mid_x]之前有n/2个元素，同理，y[]中在y[mid_y]之前也有n/2个元素，所以合并后至少会包含了所有小于等于x[mid一x]与y[mid_y]的元素，这样就有了 n个。但因为x[mid_x]小于等于y[mid_y+1]，所以x[]中比x[mid_x]大的部分也有 若干元素落在y[mid_j]的前面，所以合并后在y[mid_j]之前就有不止n个元素。换句话说， 中位数一定在y[mid_y]之前。正因为如此，在y[]中比y[mid_j]大的元素中就不可能含有中位数了，所以y[mid_y+1]〜y[n-1]的元素就可以去掉，只留下y[0]〜y[mid_y],这样y[]中 就被去掉了差不多一半的元素。

再看x[mid_x]。在x[]中比它小的不足n/2个元素，可以把x[]中x[0]~x[mid_x-1]的元素去掉，因此x[]几乎去掉了一半的元素。

【问题实现】

void  sort(int [], int);

int  median(int x[], int y[], int n)
{
     int  first_X = 0;        /* lower element of x[]     */
     int  first_Y = 0;        /* lower element of y[]     */
     int  last_X  = n-1;      /* higher element of x[]    */
     int  last_Y  = n-1;      /* higher element of y[]    */
     int  count   = 0;        /* # of smaller items elim. */
     int  mid_X, mid_Y;       /* middle element pointers  */
     int  number;             /* # of elements left       */
     int  z[4];               /* working array            */

     while ((last_X - first_X > 1) || (last_Y - first_Y > 1)) {
          mid_X = (first_X + last_X)/2;  /* get mid ptrs  */
          mid_Y = (first_Y + last_Y)/2;
          if (x[mid_X] <= y[mid_Y]) {   
               count   += (mid_X - first_X); /* inc. count*/
               first_X =  mid_X; /* elim. lower half x[]  */
               last_Y  =  mid_Y; /* elim. higher half x[] */
          }
          else {
               count   += (mid_Y - first_Y);
               first_Y =  mid_Y; /* elim. lower half y[]  */
               last_X  =  mid_X; /* elim. higher half x[] */
          }
     }

     for (number = 0; first_X <= last_X; first_X++)
          z[number++] = x[first_X];  /* collect remainder */
     for ( ; first_Y <= last_Y; first_Y++)
          z[number++] = y[first_Y];

     sort(z, number);         /* sort them                */
     return z[n-count-1];     /* pick up appropriate item */
}

/* ------------------------------------------------------ */
/* FUNCTION  sort :                                       */
/*    Special routine to sort small arrays with 2, 3 and  */
/* 4 elements.                                            */
/* ------------------------------------------------------ */

#define  SWAP(x, y)  { temp = x; x = y; y = temp; }

void  sort(int z[], int n)
{
     int  temp;

     switch (n) {
          case 4 : if (z[0] >= z[3])  SWAP(z[0], z[3]);
                   if (z[1] >= z[3])  SWAP(z[1], z[3]);
                   if (z[2] >= z[3])  SWAP(z[2], z[3]);
          case 3 : if (z[0] >= z[2])  SWAP(z[0], z[2]);
                   if (z[1] >= z[2])  SWAP(z[1], z[2]);
          case 2 : if (z[0] >= z[1])  SWAP(z[0], z[1]);
     }
}

/* ------------------------------------------------------ */

#include  <stdio.h>

void  main(void)
{
     int  x[] = { 1, 3, 6,  7,  8,  9, 10};
     int  y[] = { 2, 4, 5, 11, 12, 13, 14};
     int  n   = sizeof(x)/sizeof(int);
     int  i;

     printf("\nMedian of Two Sorted Arrays");
     printf("\n===========================");
     printf("\n\nArray #1     Array #2");
     printf(  "\n--------     --------");
     for (i = 0; i < n; i++)
          printf("\n%6d%13d", x[i], y[i]);
     printf("\n\nMedian is %d", median(x, y, n));
}

 

【习题】

(1)请把(log2n)2次比较的方法写成程序，与这里的程序就时间上作一比较。

(2)请把这里的程序扩充成x[]与y□的元素个数不同，请问程序要作多少次比较？

(3)请举出一个例子，说明while中如果改成first_X==last_X，以及first_Y ==last_Y是不智之举。请问这样做会有什么后果？

(4)程序中不要sort()可不可以？因为并不需要把对]中元素排出顺序。修改程序，修改后会比较快吗？程序会比较简单吗？

问题4.6寻找中间值（B_SEARCH.C)

已知一个整数数组X[], 一共有n个元素。对于任意两个相邻元素X[i]与x[i+1]而言， 它们的差的绝对值都不超过1,用数学式来写就是丨x[i]-x[i+l]丨≤1;而且还有x[0]<x[n-1]。 编写一个程序，在x[]数组中找出它是否有某一个输入的值a, x[0]≤a≤x[n-1],程序一共用了多少次比较？能够做到少于n次吗？

【说明】

这个题目看起来有不少条件，其实它非常简单。有很多程序设计的题目原本都是很容 易的，只不过常常看不清它的真面目，以致于做不出来或者是用了很笨拙的方法，这个题目就是一例。

提示没有什么必要，不过如果实在没有头绪，那就不妨用I作横坐标，x[i]作纵坐标， 然后运用在微积分成数值分析中学过的东西。这是笔者的想法，不过有的朋友根本不这么 想，而把它与每一本C语言教科书中都可能会有的例题产生联系，从书上马上取出那个例 题，什么都不改就算是答案了。

那么把这道题放在此地有什么用处？也骗骗读者，唬一唬而已。不妨也可以拿它来唬人。 记住，正因为它那么容易（但找不到窍门可就难啦！），还是要动动脑筋，不要看后面的解答。

【问题实现】

#define   ERROR    -1

int  bolzano_search(int x[], int n, int key)
{
     int  low  = 0;
     int  high = n-1;
     int  mid;

     if (key > x[n-1] || key < x[0]) /* reject illegal in */
          return ERROR;

     while (low <= high) {    /* simply a binary search   */
          mid = (low + high)/2;
          if (key > x[mid])
               low  = mid + 1;
          else if (key < x[mid])
               high = mid - 1;
          else
               return mid;    /* search succeeds always   */
     }
}

/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

void  main(void)
{
     int  x[] = { 1, 2, 3, 2, 3, 4, 3, 2, 1, 0, 
                  1, 2, 3, 4, 5, 6, 5, 6, 7, 8 };
     int  n   = sizeof(x)/sizeof(int);
     int  key, answer, i;
     char line[100];

     printf("\nBolzano Type Binary Search");
     printf("\n==========================");
     printf("\n\nThe Given Array :\n\n");
     for (i = 0; i < n; i++)
          printf("%3d", x[i]);
     printf("\n\nWhat is the key to be searched --> ");
     gets(line);
     key = atoi(line);
     if ((answer = bolzano_search(x, n, key)) >= 0)
          printf("\nKey found at location %d", answer);
     else
          printf("\n*** Input error ***\n Should be in the range"
                 " of %d and %d (the first and the last element)",
                 x[0], x[n-1]);
}

 

问题4.7 3个数组的共同元素（SEARCH3.C )

有3个数组x[]、y[]与z[]，各有x、y与z个元素，而且三者都已经从小到大依序排 列。编写一个程序，找出值最小的共同元素（也就是同时在3个数组中出现，并且值最小的元素)；但若没有共同元素，请显示合适的信息。

【说明】

通常寻找数据的工作都是给了一个数据，看看在某个数组中有没有它，但是这个问题却是另一个目的，要找出一个共同的元素。其实在实际应用中这种类型是屡见不鲜的。例 如，警察知道犯人是台北市人，有大学学历，有窃盗前科，因此就可能从台北市得到这个 台北人的档案，从教育部取得历年大学毕业生的档案，再从警察局取得有窃盗前科的人的 档案，如果这些档案已经依人名从小到大排好了，那么找出嫌疑人的工作就与本题差不多， 所不同的是：第一，只要找出第一个，而警察局可能要找出所有的；第二，用数组处理，所 以得知该元素个数，而警察局收到的是档案，也许不知道各个档案有多少笔数据而已。 因为不知道要找的是什么，所以二分查找法没有多大用处，要另外想办法来解题，据

我所知，最多用3min(x，y，z)次比较就可以决定答案，更重要的是程序将不超过10列，所以要往深处思考。

【问题实现】

#define  FOUND       1
#define  NOT_FOUND   0

int  search(int x[], int y[], int z[], int X, int Y, int Z,
                                       int *XX, int *YY, int *ZZ)
{
     *XX = *YY = *ZZ = 0;
     while (*XX < X && *YY < Y && *ZZ < Z) 
          if (x[*XX] < y[*YY])
               (*XX)++;
          else if (y[*YY] < z[*ZZ])
               (*YY)++;
          else if (z[*ZZ] < x[*XX])
               (*ZZ)++;
          else
               return FOUND;
     return NOT_FOUND;
}

 

问题4.8寻找最小与次小元素（1ST&2ND.C )

编写一个程序，接收一个数组，找出该数组中最小与次小的元素的值。

【说明】

这是个十分简单的问题，通常会如程序4-3所示。

【程序】

程序4-3

void first_and_second(int x[], int n, int*first, int*second) {

int i;

if (x[0]<= x[l])

*first =x[0], *second =x[1l];

else

*first =x[1], *second =x[0];

for (i = 2; i < n; i++)

if (x [i] < *first)

*second =*first; *first=x[i];

else if (x[i] <*second)

*second =x [ i ];

}

它很简洁而且容易懂，重要的是，它相当快。它一共做了多少次比较呢？开始时有一 次，对于i从2至n-1而言，最坏的情况是两次，第一次是if，第二次在elseif,因此就一 共有 1+2[(n-l)-2+1]=2n-3 次比较。

不过，希望能从另一个角度来看这个问题，能不能用“分而治之”的策略，通过递归 方法来写程序呢？程序进行了多少次比较？会比上面的程序快吗？仔细想想这个问题。注 意，并不期望找出最快的方法，只是建议用“分而治之”（Divide.and.Conquer)的方法而已。

【问题实现】

#include  <limits.h>

void  f_and_s(int [], int, int, int *, int *);

void  first_second(int x[], int n, int *first, int *second)
{
     f_and_s(x, 0, n-1, first, second);
}

/* ------------------------------------------------------ */
/* FUNCTION  f_and_s :                                    */
/*    This function accepts the input array x[] and the   */
/* left and right bounds, then returns the smallest and   */
/* the second smallest elements in this range by using    */
/* divide-and-conquer method.                             */
/* ------------------------------------------------------ */

void  f_and_s(int x[], int left, int right, int *f, int *s)
{
     int  mid;
     int  F1, F2;             /* returned smallest items  */
     int  S1, S2;             /* returned second smallest */

     if (left > right)        /* range empty ?            */
          *f = *s = INT_MAX;  /* YES, return INT_MAX      */
     else if (left == right)  /* exactly one item ?       */
          *f = x[left], *s = INT_MAX; /* return it and inf*/
     else {
          mid = (left + right)/2; /* now cut from middle  */
          f_and_s(x, left, mid, &F1, &S1);    /* left     */
          f_and_s(x, mid+1, right, &F2, &S2); /* right    */
          if (F1 < F2)        /* pick 1st and 2nd items.  */
               *f = F1, *s = (S1 < F2) ? S1 : F2;
          else
               *f = F2, *s = (S2 < F1) ? S2 : F1;
     }
}

 

问题4.9査找矩砗(M_SEARCRC )

已知一个n列n行的矩阵M,它的元素满足一个很特殊的性质，即任一元素M(i,j)都小于在它右边与下方的元素（如果存在的话）。现在又有一 个值K,编写一个程序，检查矩阵M中是否有K。

【说明】

这个矩阵有了一种很特殊的结构，换言之，每一列与每一行都从小到大排列’所以在做寻找的工作时就可以通过这个特殊的顺序来编写程序。

注意，虽然有n²个元素，但理论上可以证明，在最坏的情况下，就可以决定K在不在M中；关键所在，就是如何模仿二分查找法的技巧在一次比较之后就尽可能去掉多余不要的元素。

【问题实现】

#define  MAXSIZE  10                    /* matrix size    */

typedef  int MATRIX[MAXSIZE][MAXSIZE];  /* matrix type    */

void matrix_search(MATRIX mat, int n, int key, int *index_x, int *index_y)
{
     int  i = 0, j = n-1;     /* start from upper right   */

     for (*index_x = *index_y = -1; i < n && j >= 0; )
          if (mat[i][j] < key)/* element too small ?      */
               i++;           /* move down one row.       */
          else if (mat[i][j] > key) /* element to large ? */
               j--;           /* move left one column     */
          else {
               *index_x = i;  /* found, record locations  */
               *index_y = j;
               return;        /* and return               */
          }
     return;
}

 

问题4.10表示成两个数平方和(TWOSQUAR.C )

己知一个正整数R，编写一个程序找出所有满足X²+Y² =R的正整数对X与Y。

【说明】

例如，如果R是10000，那么因为10000 = 282+962 =602 + 802，所以就有4组X，Y满足条件，也就是28与96、96与28、60与80、80与60。要解这个题目很简单，因为X与Y的值都小于或等于R的平方根，所以用两个嵌套的 循环，分别以X与Y作变量，每次比较X²+Y²是否与R相等，如果是，就把X与Y显 示出来。至少这是一个解答，但这个做法却做了太多不应该做的事，换言之，它做了R次 比较；因为X与Y是在1与R^½之间的任意整数，所以就应该有R组，每一组都作了一次比较。

不过，事实上使用与R^½成正比的比较就可以做到，换句话说，程序可以快倍， 试一试。

提示：仔细研究例题的解答。

【问题实现】

#include  <stdio.h>           /* for I/O functions        */
#include  <stdlib.h>          /* for atoi()               */
#include  <math.h>            /* for sqrt()               */

void  main(void)
{
     int  given;              /* the given number         */
     int  row, column;        /* row and column indicators*/
     int  count;              /* number of solutions      */
     char line[100];

     printf("\nRepresenting a Given Number as the Sum of Two Squares");
     printf("\n=====================================================\n");
     printf("\nAn Integer Please ---> ");
     gets(line);
     given = atoi(line);
     printf("\nCount      X      Y");
     printf("\n-----  -----  -----");

     row    = 1;              /* starts from far enough   */
     column = (int) (sqrt((double) given) + 0.5);
     count  = 0;              /* so solution yet          */
     while (row <= given && column > 0)  /* scan down...  */
          if (row*row + column*column == given) {
               count++;
               printf("\n%5d%7d%7d", count, row, column);
               row++;
               column--;
          }
          else if (row*row + column*column > given)
               column--;
          else
               row++;

     if (count == 0)
          printf("\n\nSorry, NO ANSWER found.");
     else
          printf("\n\nThere are %d possible answers.");
}

 

问题4.11最大方玦区域(MAXSQR.C，MAXSQR2.C )

在一个矩阵中，相连在一起的一块正方形区域就叫做子区域（Subblock)。 编写一个程序，接收一个方阵（列数与行数相同），并且再接收一个已知的值，设为K，找 出在给定方阵中值全部是K的最大一个子区域,并且提示出这个子区域的位置与它的大小。

【说明】

这个题目并不十分容易，但也不难。如图4-1所示是一个8X8的方阵，元素值为0或 1，如果K是1的话，那么最大的子区域就有好几个，但都是3X3 (如程序4-3所示）。

 

这是绝大多数程序员都会想到的办法，但是这个方法却要比较与n^4成正比的次数是方阵的列数)。为什么？方阵有n^2个元素，每一个元素最多比较n^2次，所以是n^2 次。当然，事实上不会有那么多次，会少一些，但总是与n^4成正比。做这个题目的基本要求是打破比较n^4次的限制，例如n^3次，或进一步比较n^2次。与n^2 成正比的比较次数是最低限度了，因为矩阵本身就有n^2个元素，至少每一个元素都会比

次。

【问题实现】

#define   MAXSIZE     10
#define   min(a,b,c)  (((a) < (b)) ? ((a) < (c) ? (a) : (c)) \
                                   : ((b) < (c) ? (b) : (c)))

typedef   int MATRIX[MAXSIZE][MAXSIZE];

void maxsquare(MATRIX x, int n, int key, int *row, int *column, int *width)
{
     MATRIX  size;            /* a working matrix         */
     int     i, j;            /* working storages         */

     for (j = 0; j < n; j++)  /* copy last row of matrix  */
          size[n-1][j] = x[n-1][j]; /* x[][] to size[][]  */

     for (i = n-2; i >= 0; i--) { /* process bottom-up    */
          size[i][n-1] = x[i][n-1]; /* copy i-th row and  */
          for (j = n-2; j >= 0; j--)/* update size value  */
               size[i][j] = (x[i][j] == key) ? 
                    1 + min(size[i+1][j],size[i][j+1],size[i+1][j+1]) :
                    0;
     }

     *width = 0;              /* assume width is zero     */
     for (i = 0; i < n; i++)  /* scan size[] matrix for   */
          for (j = 0; j < n; j++)  /* the maximum and the */
               if (size[i][j] > *width) { /* cooresponding*/
                    *width  = size[i][j]; /* locations.   */
                    *row    = i;
                    *column = j;
               }
}


/* ------------------------------------------------------ */

#include  <stdio.h>

void main(void)
{
     MATRIX  x = { { 1, 1, 1, 0, 0, 0, 0, 0},
                   { 0, 1, 1, 1, 1, 0, 0, 0},
                   { 0, 0, 1, 1, 1, 1, 1, 0},
                   { 0, 0, 0, 1, 1, 1, 1, 1},
                   { 0, 1, 1, 1, 1, 1, 1, 1},
                   { 0, 1, 1, 1, 1, 0, 1, 1},
                   { 0, 0, 1, 1, 1, 0, 0, 0},
                   { 0, 0, 1, 1, 1, 1, 0, 0}};
     int  n = 8;
     int  row, column, width, key = 1;

     printf("\nFind Maximum Size Square of Same Data");
     printf("\n=====================================");
     printf("\n\nGiven Matrix : \n");
     for (row = 0; row < n; row++) {
          for (column = 0; column < n; column++)
               printf("%2d", x[row][column]);
          printf("\n");
     }
     printf("\nKey to be searched = %d", key);

     maxsquare(x, n, key, &row, &column, &width);

     printf("\nMaximum Square is located at x[%d][%d] with size %d",
            row, column, width);
}

 

 

参考：

C语言明天精选百则 冼镜光著