軟件水平考試常用算法設(shè)計(jì)方法

　　分治法的合并步驟是算法的關(guān)鍵所在。有些問(wèn)題的合并方法比較明顯，有些問(wèn)題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒(méi)有統(tǒng)一的模式，需要具體問(wèn)題具體分析。
　　【問(wèn)題】 大整數(shù)乘法
　　問(wèn)題描述：
　　通常，在分析一個(gè)算法的計(jì)算復(fù)雜性時(shí)，都將加法和乘法運(yùn)算當(dāng)作是基本運(yùn)算來(lái)處理，即將執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個(gè)僅取決于計(jì)算機(jī)硬件處理速度的常數(shù)。

　　這個(gè)假定僅在計(jì)算機(jī)硬件能對(duì)參加運(yùn)算的整數(shù)直接表示和處理時(shí)才是合理的。然而，在某些情況下，我們要處理很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。若用浮點(diǎn)數(shù)來(lái)表示它，則只能近似地表示它的大小，計(jì)算結(jié)果中的有效數(shù)字也受到限制。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。

　　請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算。

　　設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY。我們可以用小學(xué)所學(xué)的方法來(lái)設(shè)計(jì)一個(gè)計(jì)算乘積XY的算法，但是這樣做計(jì)算步驟太多，顯得效率較低。如果將每2個(gè)1位數(shù)的乘法或加法看作一步運(yùn)算，那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。下面我們用分治法來(lái)設(shè)計(jì)一個(gè)更有效的大整數(shù)乘積算法。
　　
　　圖6-3 大整數(shù)X和Y的分段
　　我們將n位的二進(jìn)制整數(shù)X和Y各分為2段，每段的長(zhǎng)為n/2位（為簡(jiǎn)單起見(jiàn)，假設(shè)n是2的冪），如圖6-3所示。
　　由此，X=A2n/2+B，Y=C2n/2+D。這樣，X和Y的乘積為：
　　XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
　　如果按式（1）計(jì)算XY，則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過(guò)n位的整數(shù)加法（分別對(duì)應(yīng)于式（1）中的加號(hào)），此外還要做2次移位（分別對(duì)應(yīng)于式（1）中乘2n和乘2n/2）。所有這些加法和移位共用O（n）步運(yùn)算。設(shè)T（n）是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)，則由式（1），我們有：
　　 （2）由此可得T（n）=O（n2）。因此，用（1）式來(lái)計(jì)算X和Y的乘積并不比小學(xué)生的方法更有效。要想改進(jìn)算法的計(jì)算復(fù)雜性，必須減少乘法次數(shù)。為此我們把XY寫成另一種形式：
　　XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
　　雖然，式（3）看起來(lái)比式（1）復(fù)雜些，但它僅需做3次n/2位整數(shù)的乘法（AC，BD和（A-B）（D-C）），6次加、減法和2次移位。由此可得：
　　 （4）
　　用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O(n1.59)。利用式（3），并考慮到X和Y的符號(hào)對(duì)結(jié)果的影響，我們給出大整數(shù)相乘的完整算法MULT如下：
　　function MULT(X，Y，n); {X和Y為2個(gè)小于2n的整數(shù)，返回結(jié)果為X和Y的乘積XY}
　　begin
　　S=SIGN(X)*SIGN(Y); {S為X和Y的符號(hào)乘積}
　　X=ABS(X);
　　Y=ABS(Y); {X和Y分別取絕對(duì)值}
　　if n=1 then
　　if (X=1)and(Y=1) then return(S)
　　else return(0)
　　else begin
　　A=X的左邊n/2位;
　　B=X的右邊n/2位;
　　C=Y的左邊n/2位;
　　D=Y的右邊n/2位;
　　ml=MULT(A,C,n/2);
　　m2=MULT(A-B,D-C,n/2);
　　m3=MULT(B,D,n/2);
　　S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
　　return(S);
　　end;
　　end;
　　上述二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法以提高乘法的效率減少乘法次數(shù)。
　　【問(wèn)題】 最接近點(diǎn)對(duì)問(wèn)題
　　問(wèn)題描述：
　　在應(yīng)用中，常用諸如點(diǎn)、圓等簡(jiǎn)單的幾何對(duì)象代表現(xiàn)實(shí)世界中的實(shí)體。在涉及這些幾何對(duì)象的問(wèn)題中，常需要了解其鄰域中其他幾何對(duì)象的信息。例如，在空中交通控制問(wèn)題中，若將飛機(jī)作為空間中移動(dòng)的一個(gè)點(diǎn)來(lái)看待，則具有最大碰撞危險(xiǎn)的2架飛機(jī)，就是這個(gè)空間中最接近的一對(duì)點(diǎn)。這類問(wèn)題是計(jì)算幾何學(xué)中研究的基本問(wèn)題之一。下面我們著重考慮平面上的最接近點(diǎn)對(duì)問(wèn)題。

　　最接近點(diǎn)對(duì)問(wèn)題的提法是：給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)的距離最小。

　　嚴(yán)格地說(shuō)，最接近點(diǎn)對(duì)可能多于1對(duì)。為了簡(jiǎn)單起見(jiàn)，這里只限于找其中的一對(duì)。

　　這個(gè)問(wèn)題很容易理解，似乎也不難解決。我們只要將每一點(diǎn)與其他n-1個(gè)點(diǎn)的距離算出，找出達(dá)到最小距離的兩個(gè)點(diǎn)即可。然而，這樣做效率太低，需要O(n2)的計(jì)算時(shí)間。我們能否找到問(wèn)題的一個(gè)O (nlogn)算法。

　　這個(gè)問(wèn)題顯然滿足分治法的第一個(gè)和第二個(gè)適用條件，我們考慮將所給的平面上n個(gè)點(diǎn)的集合S分成2個(gè)子集S1和S2，每個(gè)子集中約有n/2個(gè)點(diǎn)，然后在每個(gè)子集中遞歸地求其最接近的點(diǎn)對(duì)。在這里，一個(gè)關(guān)鍵的問(wèn)題是如何實(shí)現(xiàn)分治法中的合并步驟，即由S1和S2的最接近點(diǎn)對(duì)，如何求得原集合S中的最接近點(diǎn)對(duì)，因?yàn)镾1和S2的最接近點(diǎn)對(duì)未必就是S的最接近點(diǎn)對(duì)。如果組成S的最接近點(diǎn)對(duì)的2個(gè)點(diǎn)都在S1中或都在S2中，則問(wèn)題很容易解決。但是，如果這2個(gè)點(diǎn)分別在S1和S2中，則對(duì)于S1中任一點(diǎn)p，S2中最多只有n/2個(gè)點(diǎn)與它構(gòu)成最接近點(diǎn)對(duì)的候選者，仍需做n2/4次計(jì)算和比較才能確定S的最接近點(diǎn)對(duì)。因此，依此思路，合并步驟耗時(shí)為O(n2)。整個(gè)算法所需計(jì)算時(shí)間T(n)應(yīng)滿足：

　　T(n)=2T(n/2)+O(n2)

　　它的解為T(n)=O(n2)，即與合并步驟的耗時(shí)同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們看到問(wèn)題出在合并步驟耗時(shí)太多。這啟發(fā)我們把注意力放在合并步驟上。

　　為了使問(wèn)題易于理解和分析，我們先來(lái)考慮一維的情形。此時(shí)S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)x1、x2、…、xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。我們顯然可以先將x1、x2、…、xn排好序，然后，用一次線性掃描就可以找出最接近點(diǎn)對(duì)。這種方法主要計(jì)算時(shí)間花在排序上，因此如在排序算法中所證明的，耗時(shí)為O(nlogn)。然而這種方法無(wú)法直接推廣到二維的情形。因此，對(duì)這種一維的簡(jiǎn)單情形，我們還是嘗試用分治法來(lái)求解，并希望能推廣到二維的情形。

　　假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S | x>m}。這樣一來(lái)，對(duì)于所有p∈S1和q∈S2有p　　遞歸地在S1和S2上找出其最接近點(diǎn)對(duì){p1，p2}和{q1，q2}，并設(shè)δ=min{|p1-p2|，|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1，p2}，或者是{q1，q2}，或者是某個(gè){p3，q3}，其中p3∈S1且q3∈S2。如圖1所示。
　　
　　圖1 一維情形的分治法
　　我們注意到，如果S的最接近點(diǎn)對(duì)是{p3，q3}，即 | p3-q3 | < δ，則p3和q3兩者與m的距離不超過(guò)δ，即 | p3-m | < δ，| q3-m | < δ，也就是說(shuō)，p3∈(m-δ，m)，q3∈(m，m+δ)。由于在S1中，每個(gè)長(zhǎng)度為δ的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于δ），并且m是S1和S2的分割點(diǎn)，因此(m-δ，m)中至多包含S中的一個(gè)點(diǎn)。同理，(m，m+δ)中也至多包含S中的一個(gè)點(diǎn)。由圖1可以看出，如果(m-δ，m)中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。同理，如果(m，m+δ)中有S中的點(diǎn)，則此點(diǎn)就是S2中最小點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-δ，m)和(m，m+δ)中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。也就是說(shuō)，按這種分治策略，合并步可在O(n)時(shí)間內(nèi)完成。這樣是否就可以得到一個(gè)有效的算法了呢？

　　還有一個(gè)問(wèn)題需要認(rèn)真考慮，即分割點(diǎn)m的選取，及S1和S2的劃分。選取分割點(diǎn)m的一個(gè)基本要求是由此導(dǎo)出集合S的一個(gè)線性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1 {x | x≤m}；S2 {x | x>m}。容易看出，如果選取m=[max（S）+min（S）]/2，可以滿足線性分割的要求。選取分割點(diǎn)后，再用O(n)時(shí)間即可將S劃分成S1={x∈S | x≤m}和S2={x∈S | x>m}。然而，這樣選取分割點(diǎn)m，有可能造成劃分出的子集S1和S2的不平衡。例如在最壞情況下，|S1|=1，|S2|=n-1，由此產(chǎn)生的分治法在最壞情況下所需的計(jì)算時(shí)間T（n）應(yīng)滿足遞歸方程：
　　T（n）=T（n-1）+O（n）

　　它的解是T（n）=O（n2）。這種效率降低的現(xiàn)象可以通過(guò)分治法中“平衡子問(wèn)題”的方法加以解決。也就是說(shuō)，我們可以通過(guò)適當(dāng)選擇分割點(diǎn)m，使S1和S2中有大致相等個(gè)數(shù)的點(diǎn)。自然地，我們會(huì)想到用S的n個(gè)點(diǎn)的坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。在選擇算法中介紹的選取中位數(shù)的線性時(shí)間算法使我們可以在O（n）時(shí)間內(nèi)確定一個(gè)平衡的分割點(diǎn)m。

　　至此，我們可以設(shè)計(jì)出一個(gè)求一維點(diǎn)集S中最接近點(diǎn)對(duì)的距離的算法pair如下。
　　Float pair（S）;
　　{ if | S | =2 δ= | x[2]－x[1] | /*x[1..n]存放的是S中n個(gè)點(diǎn)的坐標(biāo)*/
　　else
　　{ if ( | S | =1) δ=∞
　　 else
　　{ m=S中各點(diǎn)的坐標(biāo)值的中位數(shù);
　　 構(gòu)造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
　　δ1=pair(S1);
　　 δ2=pair(S2);
　　 p=max(S1);
　　 q=min(S2);
　　 δ=min(δ1，δ2，q-p);
　　}
　　return(δ);
　　}
　　由以上的分析可知，該算法的分割步驟和合并步驟總共耗時(shí)O(n)。因此，算法耗費(fèi)的計(jì)算時(shí)間T(n)滿足遞歸方程：
　　
　　解此遞歸方程可得T(n)=O(nlogn)。
　　
　　【問(wèn)題】循環(huán)賽日程表
　　問(wèn)題描述：設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽�，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：
　�。�1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次；
　�。�2）每個(gè)選手一天只能參賽一次；
　�。�3）循環(huán)賽在n-1天內(nèi)結(jié)束。
　　請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個(gè)表。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n-1。

　　按分治策略，我們可以將所有的選手分為兩半，則n個(gè)選手的比賽日程表可以通過(guò)n/2個(gè)選手的比賽日程表來(lái)決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這兩個(gè)選手進(jìn)行比賽就可以了。
　　
　　 1 2 3 4 5 6 7
　　 1 2 3 4 5 6 7 8
　　 2 1 4 3 6 7 8 5
　　 3 4 1 2 7 8 5 6
　　 1 2 3 4 3 2 1 8 5 6 7
　　 1 2 3 4 5 6 7 8 1 4 3 2
　　 1 2 1 4 3 6 5 8 7 2 1 4 3
　　1 2 3 4 1 2 7 8 5 6 3 2 1 4
　　2 1 4 3 2 1 8 7 6 5 4 3 2 1
　�。�1） （2） （3）
　　圖1 2個(gè)、4個(gè)和8個(gè)選手的比賽日程表
　　圖1所列出的正方形表（3）是8個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對(duì)位置抄到右下角，又將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個(gè)比賽日程表推廣到具有任意多個(gè)選手的情形。

　　八、動(dòng)態(tài)規(guī)劃法

　　 經(jīng)常會(huì)遇到復(fù)雜問(wèn)題不能簡(jiǎn)單地分解成幾個(gè)子問(wèn)題，而會(huì)分解出一系列的子問(wèn)題。簡(jiǎn)單地采用把大問(wèn)題分解成子問(wèn)題，并綜合子問(wèn)題的解導(dǎo)出大問(wèn)題的解的方法，問(wèn)題求解耗時(shí)會(huì)按問(wèn)題規(guī)模呈冪級(jí)數(shù)增加。

　　 為了節(jié)約重復(fù)求相同子問(wèn)題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問(wèn)題的解存于該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法。以下先用實(shí)例說(shuō)明動(dòng)態(tài)規(guī)劃方法的使用。

　　【問(wèn)題】 求兩字符序列的最長(zhǎng)公共字符子序列
　　問(wèn)題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個(gè)字符（可能一個(gè)也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列，使得對(duì)所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。

　　給定兩個(gè)序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問(wèn)題要求已知兩序列A和B的最長(zhǎng)公共子序列。

　　如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時(shí)記錄所發(fā)現(xiàn)的子序列，最終求出最長(zhǎng)公共子序列。這種方法因耗時(shí)太多而不可取。

　　考慮最長(zhǎng)公共子序列問(wèn)題如何分解成子問(wèn)題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì)：
　　（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列；
　�。�2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；
　�。�3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。
　　這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問(wèn)題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè)最長(zhǎng)公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問(wèn)題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列，再取兩者中較長(zhǎng)者作為A和B的最長(zhǎng)公共子序列。
　　定義c[i][j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長(zhǎng)公共子序列的長(zhǎng)度，計(jì)算c[i][j]可遞歸地表述如下：
　�。�1）c[i][j]=0 如果i=0或j=0；
　�。�2）c[i][j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
　�。�3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
　　按此算式可寫出計(jì)算兩個(gè)序列的最長(zhǎng)公共子序列的長(zhǎng)度函數(shù)。由于c[i][j]的產(chǎn)生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開(kāi)始，跟蹤c[i][j]的產(chǎn)生過(guò)程，逆向構(gòu)造出最長(zhǎng)公共子序列。細(xì)節(jié)見(jiàn)程序。
　　# include
　　# include
　　# define N 100
　　char a[N],b[N],str[N];
　　
　　int lcs_len(char *a, char *b, int c[ ][ N])
　　{ int m=strlen(a), n=strlen(b), i,j;
　　 for (i=0;i<=m;i++) c[i][0]=0;
　　 for (i=0;i<=n;i++) c[0][i]=0;
　　 for (i=1;i<=m;i++)
　　 for (j=1;j<=m;j++)
　　 if (a[i-1]==b[j-1])
　　 c[i][j]=c[i-1][j-1]+1;
　　 else if (c[i-1][j]>=c[i][j-1])
　　 c[i][j]=c[i-1][j];
　　 else
　　 c[i][j]=c[i][j-1];
　　 return c[m][n];
　　}
　　
　　char *buile_lcs(char s[ ],char *a, char *b)
　　{ int k, i=strlen(a), j=strlen(b);
　　 k=lcs_len(a,b,c);
　　 s[k]=’\0’;
　　 while (k>0)
　　 if (c[i][j]==c[i-1][j]) i--;
　　 else if (c[i][j]==c[i][j-1]) j--;
　　 else { s[--k]=a[i-1];
　　 i--; j--;
　　 }
　　 return s;
　　}
　　
　　void main()
　　{ printf (“Enter two string