( 圖1.4-1 )
有許多算法在結構上是遞歸的：為了解決一個給定問題， 算法要一次或多次地調用其自身來解決相關的子問題。這些算法通常采用分治策略:將原問題分成n 個規模較小而結構與原問題相似的子問題。遞歸地解這些子問題，然后合并其結果就得到原問題的解。 n＝2時的分治法又稱二分法。
用分治法求解一個問題，所需的時間是由子問題的個數， 大小以及把這個問題分解為子問題所需的工作總量來確定。一般來說，二分法(即把任意大小的問題盡可能地等分兩個子問題)較為有效。
分治法在每一層遞歸上都有三個步驟:
分解:將原問題分解成一系列子問題;
解決:遞歸地解各子問題。若子問題足夠小，則直接解;
合并:將子問題的結果合并成原問題的解;
【例1】合并排序
對序列A〔1〕，A〔2〕，……，A〔n〕進行合并排序。
算法分析:
合并排序的算法就是二分法
分解:將n個元素各含n/2個元素的子序列;
解決:用合并排序法對兩個子序列遞歸地排序;
合并:合并兩個已排序的子序列以得到排序結果;
在對子序列排序時，當其長度為1時遞歸結束。單個元素被視為是已排好序的。合并排序的關鍵步驟在于合并步驟中產生的兩個已排好序的子序列
A〔P..Q〕和A〔Q+1..R〕
將它們合并成一個已排好序的子序列〔P..R〕。我們引入一個輔助過程merge(A,P,Q,R)來完成這一合并工作，其中A是數組，P，Q ，R是下標。這個過程如果用玩撲克來比喻，就可以看作桌上有兩堆牌，每一堆都是排好序的，最小的牌在最上面， 我們希望把這兩堆牌合并成排好序的一堆加以輸出。基本步驟包括:先取面朝上的兩堆牌的頂上兩張中較小的一張，將它取出面朝下地放到輸出堆中。重復這個步驟直到某一輸入堆為空。 這時把另一個輸入堆中余下的牌面朝下放入即可。
Procedure Merge(Var A: ListType; p, q, r : Integer);
{將兩個已排好序的子序列A[p..q]和A[q+1..r]合并成一個已排好序的序列A[p..r]}
Var
i, j, t : Integer;{左子序列指針;右子序列指針;合并后的序列的指針}
Lt : ListType;{暫存合并的序列}
Begin
t := p; i := p; j := q + 1;
While t <= r Do Begin{若合并未完成,則循環}
If (i <= q) And ((j > r) Or (A[i] <= A[j])) Then Begin
{若左序列剩有元素并且右序列元素全部合并或者左序列的首元素小于等于右序列的首元素,
則左序列的首元素進入合并序列,左序列的首指針+1}
Lt[t] := A[i]; Inc(i)
End{then}
Else Begin{否則左序列的首元素進入合并序列,右序列的首指針+1}
Lt[t] := A[j]; Inc(j)
End;{else}
Inc(t){合并序列的指針+1}
End;{while}
For i := p to r Do A[i] := Lt[i]{合并后的序列賦給A}
End;{Merge)
現在就可以把merge過程作為合并排序的一個子過程來用了。下面是merge_sort(A,P,R)對數組A〔P..R〕進行排序。若P ≥R，該子數組至多只有一個元素， 當然就是已排序的。否則，分解步驟就計算出一個中間下標Q，而將A〔P..R〕分成A〔P..Q〕和A〔Q+1..R 〕。若數組A〔P..R〕的元素個數K＝R－P+1為偶數，則兩個數組各含K/2個元素;否則A〔P..Q〕含[k/2]+1( k/2 )元素、A〔Q+1，R〕含[k/2]( k /2 )個元素。
Procedure Merge_Sort(Var A : ListType; p, r : Integer);
Var
q : Integer;
Begin
If p <> r Then Begin{若子序列A中不止一個元素}
q := (p + r - 1) div 2;{計算中間下標q}
Merge_Sort(A, p, q);{繼續對左子序列A[p..q]遞歸排序}
Merge_Sort(A, q + 1, r);{繼續對右子序列A[q+1..r]遞歸排序}
Merge(A, p, q ,r){對左子序列和右子序列合并排序}
End{then}
End;{Merge_sort}
我們只要調用merge_sort(A，1，N)便可對整個序列A〔1〕……A〔n〕進行合并排序。如果我們自底向上(此處“底”為n是2的冪時)來看這個過程的操作時，算法將兩個長度為1的序列合并成排好序的長度為2的序列，繼而合并成長度為4的序列……，依次類推。 隨著算法自底向上執行，被合并的排序序列長度逐漸增加，一直進行到將兩個長度為n／2 的序列合并成最終排好序的長度為n的序列。下圖列出了對序列(5，2，4，6，1，3，2，6)進行合并排序的過程。
當然，排序算法很多，但合并排序法也有其本身的特點──當輸入的規模足夠大時，合并排序的運行時間要比最壞情況下的插入排序好。分治算法不僅可應用于排序，而且還可應用于許多重要的場合，甚至有些問題看起來非得采用分治法求解不可。
【例2】導線和開關
如(圖1.4-2)所示，具有3根導線的電纜把A區和B區連接起來。在A區3根導線標以1，2，3;在B區導線1和3被連到開關3，導線2連到開關1。
一般說來，電纜含m(1≤m≤90)根導線，在A區標以1，2，...m。在B區有m個開關， 標為1，2，...m。每一根導線都被嚴格地連到這些開關中的某一個上;每一個開關上可以連有0根或多根導線。
測量
你的程序應作某些測量來確定，導線和開關怎樣連。 每個開關或處于接通或處于斷開狀態，開關的初始狀態為斷開。我們可用一個探頭(probe)P在A區進行測試: 如果探頭點到某根導線上，當且僅當該導線連到處接通狀態的開關時，燈L才會點亮。
你的程序從標準輸入(standard input)讀入一行以得到數字m; 然后可以通過向標準輸出(standard output)寫入一行以發出命令(共3種命令)。每種命令的開頭是一個大寫字母:
○測試導線命令T:T后面跟一個導線標號;
○改變開關狀態命令C:C后面跟一個開關標號;
○完成命令D:D后面跟的是一個表列(LIST)，該表列中的第ｉ個元素代表與導線ｉ相 連的開關號。
在命令T和C之后，你的程序應從標準輸入(standard input)讀入一行。 若開關狀態能使燈亮，則命令T的回答應是Y;反之，回答應是N。命令C的作用是改變開關的狀態( 若原來是接通則變為斷開;若原來是斷開則變為接通)。對C命令的回答是作為一種反饋信號。
你的程序可以給出一系列命令，將T命令與C命令以任意順序混合使用。最后給出命令D，并結束。你的程序給出的命令總數應不大于900。
注意
為了在此任務中能正確使用標準輸入(standard input)和標準輸出(standard output)。若你使用pascal，請不要使用其中的CRT單元(unit CRT)。
舉例
(圖1.4-3)給出了一個實例，對應于(圖1.4-2)，這是一個有8條命令的對話。
┌──────────┐ ┌─────────┐ │ Standard Output │ │ Standard Input │ ├──────────┤ ├─────────┤ │ │ │ 3 │ │ C 3 │ │ Y │ │ T 1 │ │ Y │ │ T 2 │ │ N │ │ T 3 │ │ Y │ │ C 3 │ │ N │ │ C 2 │ │ Y │ │ T 2 │ │ N │ │ D 3 1 3 │ │ │ └──────────┘ └─────────┘( 圖1.4-3 )
算法分析:
這是一道通過人機對話解答的程序題。程序執行時，由計算機發出T或C命令。 用戶通過鍵盤輸入應答信號。人與計算機間幾次交互信息后，最終由計算機給出命令D并顯示導線和開關怎樣連接的。對于編程序者來說，要解決的問題是如何設計命令順序， 使得用戶在依次應答后，程序能自動給出問題的解。
1.T命令和C命令的作用
初始時，B區M個開關斷開。此時無論用探頭P在A區測哪根導線，燈L也不會亮。因此，程序首先必須使用C命令和用戶應答將B區的部分開關閉合。然后發出測試某些導線的T命令，通過用戶應答確定這些導線在B區的準確位置或范圍。若尚有導線未連接，則再通過C 命令和用戶應答來改變某些開關的狀態，隨后發出T命令……，C命令和T命令交替使用，直到完成導線和開關的連接 。例如 M＝3。初始時
對話序號 計算機命令 用戶應答 結果 1 C3 Y 開關3閉合 2 T1 Y L燈亮，導線1與開關3連接 3 T2 N 導線2不與開關3連接 4 T3 Y 導線3與開關3連接
對話序號 計算機命令 用戶應答 結果 5 C3 N 開關3斷開 6 C2 Y 開關2閉合 7 T2 N 導線1與開關3連結
由此可見,改變開關狀態的C命令在人機對話中最先使用,然后發出T命令測試部分導線。若不能確定每根導線的連接位置，則還得對一些開關使用C命令，改變其開關狀態，直到最后一個T命令完成導線與開關的連接為止。注意，用戶對C 命令的回答僅是作為開關狀態改變的一種反饋信號。即無論用戶怎樣應答， 開關狀態總是由應答前的斷開變為應答后的閉合，或者由應答前的閉合變為應答后的斷開。
繼C命令后使用T命令測試導線。測試導線i的過程中
若僅一個開關閉合且燈亮(即Ti的應答為Y)，則被測導線i與閉合的開關連接;
若僅一個開關斷開且燈暗(即Ti的應答為N)，則被測導線i與斷開的開關連接;
若多個開關閉合時燈亮(Ti的應答為Y)或者多個開關斷開時燈暗(Ti的應答為N)) ，而先前的測試已確定導線i只能與這些開關中的某一個相連，則導線與之相連。
例如:第7次對話，用戶應答T2的命令為N，而此時開關1、3斷開，看來導線2 即可能與開關1相連，也可能與開關3相連。但是先前第3次對話，用戶應答T2命令為N，確認導線2不與開關3連接。無庸置疑，導線2的連接對象僅一個─開關1。
2.用二分法連接
為了使導線和開關間的連接工作有規律地進行，我們不妨采用二分法。
設當前待連接的開關為HEAD.. TAIL，初始時為1..M。將這些開關一分為二:
左區間HEAD..[(HEAD+TAIL－1)/2];
右區間[(HEAD+TAIL－1)/2]+1..TAIL;
連接到左區間開關的導線集合為P1。初始時P1＝〔1..M〕;
連接到右區間開關的導線集合為P2。顯然初始時P2＝〔 〕;
左區間或右區間開關狀態是同一的，設為STATE。
┌1 區間的所有開關閉合; │ STATE＝│ │ └0 區間所有開關斷開; 顯然初始時STATE＝0;
首先，P2集合設空并發出C命令，將左區間的所有開關取反。然后對P1集合中的每根導線發出T命令。若用戶應答N(燈暗)而左區間開關閉合，或者用戶應答Y(燈亮)而左區間開關斷開，則說明相連的導線不在P1中，應從P1集合移入P2集合。
接下去，設左區間開關為待接開關，與之相連的導線集合為P1，開關狀態已由先前的C命令取反。繼續上述過程，直至出現下述兩種情況之一為止:
①P1的集合為空;
②區間內的開關僅剩一個，將P1集合中所有導線連接到這個開關;最后再將右區間開關設為待連接開關，與之相連的導線集合為P2，開關狀態不變。仍按上述方法進行連接。
顯然，可以用一個二分法的遞歸過程來描述導線與開關間的連接:
procedure check(P1，開關區間，state);
begin
if P1 <>〔〕then
if 區間內剩一個開關
then P1集合中的所有導線與之相連
else begin
通過C命令和用戶應答將左區間取反;
P2集合設空;
對P1集合中的每根導線發出T命令:
if((用戶應答N)and(state=0))or((用戶應答Y)and(state=1))
then 導線從P1集合移出，移入P2集合;
check(P1，左區間，1－state);
check(P2，右區間，state);
end; {else}
end; {check}
| 歡迎光臨 (http://www.zg4o1577.cn/bbs/) | Powered by Discuz! X3.1 |