C语言精选名题百则——第一章（序曲）

问题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就是该数组中最长的平台。

//最长平台问题 
int longest_plateau(int x[],int n)
{
	int length = 1;
	for(int i =1;i<n;i++)
	{
		if(x[i]==x[i-length])
			length++;
	}
	return length;
}

问题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_1(int f[],int g[],int m,int n) 
{
	int sum=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(f[j]>g[i])
			{
				sum +=m-j;
				break;
			}	
		}
	}
	return sum;
}

标答：

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.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是第二组。

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

问题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[]已经排列好的特性，不要把所有的距离都算出来。

//1.4两数组最短问题 
#include <limits.h>

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

int min_distance(int x[],int y[],int m,int n)
{
	int minimum=INT_MAX;
	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.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是整个数组元素的和，因此前置和与后置和一定相同。

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

【解答】

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

//1.5等值首尾和问题
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)
	{
		if(prefix < suffix)
			prefix +=x[prefix_idx++];
		else if(prefix > suffix)	
			suffix +=x[suffix_idx++];
		else{
			count++;
			prefix +=x[prefix_idx++];
			suffix +=x[suffix_idx++];
		}	
	}
	return count;
}