軟件水平考試常用算法設計方法

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

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

　　請設計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算。

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

　　最接近點對問題的提法是：給定平面上n個點，找其中的一對點，使得在n個點的所有點對中，該點對的距離最小。

　　嚴格地說，最接近點對可能多于1對。為了簡單起見，這里只限于找其中的一對。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。

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

　　考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：
　�。�1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；
　�。�2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；
　�。�3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。
　　這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
　　定義c[i][j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長公共子序列的長度，計算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]。
　　按此算式可寫出計算兩個序列的最長公共子序列的長度函數(shù)。由于c[i][j]的產生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開始，跟蹤c[i][j]的產生過程，逆向構造出最長公共子序列。細節(jié)見程序。
　　# 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