C语言名题精选百则——终曲?第9章终 曲?W?闼题9.1等璗正负号段落（BALANCE.C )?已知一个数组，其中有正数、0、负
C语言名题精选百则——终曲
?
第9章终 曲
?
W
?
闼题9.1等璗正负号段落（BALANCE.C )
?
已知一个数组，其中有正数、0、负数，请写一个函数，找出这个数组中最长的而且正 数与负数个数相同的部分数组的长度。
?
【说明】
?
在数组中的0既不是正数，又不是负数。如果数组的元素为1、1、-1、-2、0、1、3、
?
-1、-2与1这10个数，于是前9个数的这一段就是所要的，它有4个正数、4个负数。
?
注意，它不可能是后9个数，负数比正数少了一个；自然也不可能是整个数组，因为数组
?
中负数的个数比正数个数多1。
?
对初学程序写作的朋友而言，这个题目并不难，因为他们多半会想到用两个矩阵P与 N，Pij与表示输入数组中i?j (含）的正数个数与负数个数，求得1^与>^并不难，把
?
输入数据从i起到j只查一遍就行了。求出P与W之后，就把P;j与Nij—个接一个地比过
?
去，一旦发现PijzNij,就把Pij (或Np的值与已经记住的极大值相比，并且更正极大值
?
的内容，当所有P(j与％都比完之后，就有了的极大值，这就是该部分数组的长度
?
了。然而这个方法却很慢，应该是入门者的写法。一般的程序员马上就可以看出P与iV只 要一半，上半或下半三角形都行；有一点门道的或许用P或AT就足够了，因为可以令Pi3是
?
正数个数与负数个数之差，到时查1^为0的地方；再好一点的程序员或许发现两列就足够 了。您是哪一类呢？
?
提示：任何人在想一个程序时往往是越想越筒捷的，上面已经给了很好的提示，重点就在 于如何记录正数与负数个数的改变。
问题9.2寻找长方形（RECXC )
?
在圆周上有若干个点，已经知道这些点与点之间的弧长，依圆弧顺序排列，请写一个 程序，找出这些点中有没有4个可以围成长方形，为了方便计算，弧长均为正整数。
?
【说明】
?
在图9.1a中，弧长是1、3、1、1、4、1、2、1、2、2、2,很明显地可以得到若干长
?
方形，不过图中只画出了两个而已，事实上，它一共有6个。不过在图94b,却没有办法
找出4个点围成长方形。程序的任务，就是先从简单的开始，回答“有”或“没有”就足 够了。图9-1注意，因为给的是弧长，所以“点在圆上”这一事实是不重要的，程序只需要在弧长 上动动脑筋就可以了，与圆无关。事实上，有很多问题是可以转化成与原来的面目完全不 同的。那么，这个问题要转换成哪一个熟悉的技巧呢？如果把本书前面的题目都浏览或做 过一次，就应该发现有相似的题目。另外，这不是一个所谓计算几何学（Computational Germetry)的问题，因为它简单到只能放在此地当作一个小题目做做而已^~一如果看得出 诀穷的话。问题9.3多边形的直径(DIAMETER.C )假设平面上的点Pq，PpP2，…,Pnq围成一个多边形，…，为 这个n边多边形的边。这个多边形的直径（Diameter)的定义是这样的：找出多边形的两 I 点 Pi 与 Pj，CXi<j<n，使得 pipi+1 + Pi+1pi+2 +?? + pj—A 与 PjPj+i + Pn-2Pn-l + Pn-lPo +
^+…+^^^^^对值力^小，^ Pi ^ Pj zmg然,
直径可能不止一条。把—，叾，的长度记成，…，l等，找出两 个点i与j，0^i<j<n,使得Pi与Pj的连线为该多边形的直径。
【说明】
如图9-2所示，各边的边长都己经标在边线旁边。很明显地，这一段折线的总长为5，而P4，P5，P6，P。这一段为4，差的 绝对值为1，因此pQ~p4的连线是一条直径；同理，？1与？5的连线也是直径，因为
P0，P1，P2，P3，P4这一段折线长度为5，而P^PpPo’Pi的长度为4，差的绝对值也是1;另 外？1与？4的连线也是直径。还有其他的直径吗？自己找找看。因此，当程序收到输入1、 1、1、2、1、1、2时，至少要能报告出pQ，p4; p,,p5 ； p1?p4 ;…这些直径其中的一组。
提示：在此之前已经做过许多个类似的题目了，这个题目并不难。首要工作，就是看看如 何表示差的绝对值；也要注意到，两个决定直後的点把多边形分成两部分，这两部 分边的总长正好就是整个多边形边长之和。闼题9.4机器人旋转甭度（TURNS.C)平面上有n个点，有一个机器人目前放在Pi上，而且面向X轴的正方 向，这个机器人会WPl出发，沿途依次经过Pl，P2，…，？。这些点，最后回到Pi并且面向X 轴的正方向。当机器人到达某个点Pl时，它会以逆时针方向旋转，使自己面对pi+1,再沿 直线方向从Pi走到pi+1。编写一个程序，读入Pi，P2,…，pn的坐标值，求出这个机器人总 共做了多少次360°的旋转o【说明】
下面是一个有4个点的例子，如图9-3所示。图9-3
从图9-3可以看出机器人一共转了两次360°的旋转；图中的箭头指出机器人在Pi时 所面对的方向，而弧型的箭头则指出旋转方向与大小。可以发现，从？1到02面对p3时， 旋转度数还不到180° ,到了 p3要转成面对p4时就做了一次大于180°的旋转，不过总度数还是不足360o直到达p4而旋转成面对Pl时才是第一次超过360°，然后到了 ？1而旋转成面对X轴时，正好满足两个360°。注意，所有旋转都是逆时针方向。
有些朋友必定会觉得这个题目很容易，因为沿Pi到pi+1的方向是J=pi+1 —Pi,而从
Pi+i到Pi+2的方向是P =Pi+2 — Pi+i ,于是求这两个向量（Vector) J与7的夹角，就会知道在pi+I这个点转多少度，由此在每一点计算一次，且累计下来，这样就可以求出旋转的总
度数，再用360°去除，不就求出有多少个360°的旋转了吗？不错，想法完全正确，但是 却太慢了，因为要算出5与f的夹角，先要算出丨^1、Ifl与K-JI,再用余弦定律才能求出 夹角0，如图9-4所示。= arccos -
2IJII7I图9-4
因此，5与f之间的旋转角度就是e或2tc_0，视旋转方向是从7到J还是从^到F而 定。用了多少个运算呢？连三角函数都用上了，当n很大，而且又在没有算术处理单元的 机器之下运行时，速度之慢可想而知。?
所以，要求是，把问题仔细想一想，用最省时间的办法把程序写出来。特别是，当坐 标都是整数时（比如荧光幕上的点坐标)，程序能够不用实数，而单靠整数进行运算吗？
问题9.5最大涵盖距离（MAXCOVER.C )已知一个数组x[],说x[j]是i?j之间的极大点，指的就是对于任一在i与j之间（含 i与j)的k而言，如果x[k]小于等于x[j]的绝对值k，则x[j]的绝对值涵盖（Cover)住[i，j] 这个区间。请写一个程序，找出最长的、被涵盖的区间。
【说明】
如果数组的元素是1，-3，2，1，-2，3，5，2,-4，3。对于第一个1而言，它只涵盖了自己，故长 度为1;对于-3而言，它的绝对值为3，自然地就涵盖住1与-3，故长度为2;对于2来 说，1，-3,2都小于2,故涵盖的长度为3。如果继续看下去，5所涵盖的长度最长（值为7), 涵盖住1，-3，2，1，-2，3，5。请问要如何编写一个高效率的程序呢？
事实上这是一个非常简单的程序，建议从右往左处理比较合理些，原因是被涵盖住的 区间是在涵盖它的元素的左边，因此往左找不到比较合理。程序主体部分应该要做到10列
之内写完，不要有多余的部分。
这个题目最好从右往左处理，根据这个提示，最有可能会想到下面的写法，它从右向 左处理，而且也不足10列，如程序9-1所示。
【程序】
程序9-1
for (i 二 n—1, max—len =1; i >=1; i—}{
for (j = i-1; j >= 0 && x[j] <= abs(x[i]； j——）max_len - MAX(max_len, i-j);
}II但是这个程序却不够快（虽然够短），如果X[]中的元素是从小到大排好了的，对i而 那么中间的循环就会绕i圈，因为i可以为1?n-1,所以循环就一共绕了 1+2+…+(n-l)=n(n-l)/2l,程序就变为与n2成正比的速度了。并不期望做出这样的结果，事实上 希望做到与n成正比。Ili??问题9.6最大连续元素和(MAXSUM.C，MAXSUM1.C )已知数组x[]储存了一组整数，请写一个程序，找出在数组中连续元素的和中最大的 一个。举例而言，如果有数组1，2，-6，3，-2，4，-1,3,2，-4，那么连续的元素的和有1+2=3, l+2+(-6)=-3, 2+(~6)=-4,…，但值最大的就是 3+(-2)+4+(_1)+3+2 这一段，值为 9。规定: 和为负值时就定成0,所以结果永远不为负。这个题目通常叫做最大连续元素和（Maximum Consecutive Sum )问题。
【说明】
这个问题有个很简单的解法，但效率很低，一般采用效率很高的方法的程序比使用不 好的方法的要长。m般人看到这个问题的自然反应就是用两个循环，如程序9-2所污【程序】程序9-2
i= maxsum =0; i < n； i++){Forsum = 0;
for {j = 1; j >= 0; j--){
sum += x[j]； if (sum > maxsum) maxsum =想法是很简单的，当固定在某个x[i]之后，把x[i],x[i-l]+x[i],x[i-2]+ x[i-l]+x[i]，…， x[0]+x[l]+"_+X[i]求出来，一边算，一边找出极大值，这就是上面片段所隐含的意义。
但是，当处理到i时要查i个元素，所以要把n个数都处理完，就要查l+2+3f+i+… +n-n(n+l)/2.与n2成正比的元素了。如果仔细看就会发现做了很多重复的工作，为什么？ 当i是2时,算了 x[2],x[l]+x[2],x[0]+x[l]+x[2],但当i进到下一个位置变成3时，又算 x[3],x[2]+x[3],x[l]+x[2] +x[3]，x[0]+x[l]+x[2]+x[3]，于是 x[l]+x[2]与 x[0]+x[l]+ x[2]不都是 重复算了吗？因此，程序如果能够避免这些重复的部分，就一定会非常快。93
?
