分治法---基礎(chǔ)算法

有許多算法在結(jié)構(gòu)上是遞歸的：為了解決一個(gè)給定問(wèn)題， 算法要一次或多次地調(diào)用其自身來(lái)解決相關(guān)的子問(wèn)題。這些算法通常采用分治策略:將原問(wèn)題分成n 個(gè)規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題，然后合并其結(jié)果就得到原問(wèn)題的解。 n＝2時(shí)的分治法又稱二分法。

用分治法求解一個(gè)問(wèn)題，所需的時(shí)間是由子問(wèn)題的個(gè)數(shù)， 大小以及把這個(gè)問(wèn)題分解為子問(wèn)題所需的工作總量來(lái)確定。一般來(lái)說(shuō)，二分法(即把任意大小的問(wèn)題盡可能地等分兩個(gè)子問(wèn)題)較為有效。

分治法在每一層遞歸上都有三個(gè)步驟:

分解:將原問(wèn)題分解成一系列子問(wèn)題;

解決:遞歸地解各子問(wèn)題。若子問(wèn)題足夠小，則直接解;

合并:將子問(wèn)題的結(jié)果合并成原問(wèn)題的解;

【例1】合并排序

對(duì)序列A〔1〕，A〔2〕，……，A〔n〕進(jìn)行合并排序。

算法分析:

合并排序的算法就是二分法

分解:將n個(gè)元素各含n/2個(gè)元素的子序列;

解決:用合并排序法對(duì)兩個(gè)子序列遞歸地排序;

合并:合并兩個(gè)已排序的子序列以得到排序結(jié)果;

在對(duì)子序列排序時(shí)，當(dāng)其長(zhǎng)度為1時(shí)遞歸結(jié)束。單個(gè)元素被視為是已排好序的。合并排序的關(guān)鍵步驟在于合并步驟中產(chǎn)生的兩個(gè)已排好序的子序列

A〔P..Q〕和A〔Q+1..R〕

將它們合并成一個(gè)已排好序的子序列〔P..R〕。我們引入一個(gè)輔助過(guò)程merge(A,P,Q,R)來(lái)完成這一合并工作，其中A是數(shù)組，P，Q ，R是下標(biāo)。這個(gè)過(guò)程如果用玩撲克來(lái)比喻，就可以看作桌上有兩堆牌，每一堆都是排好序的，最小的牌在最上面， 我們希望把這兩堆牌合并成排好序的一堆加以輸出�；�本步驟包括:先取面朝上的兩堆牌的頂上兩張中較小的一張，將它取出面朝下地放到輸出堆中。重復(fù)這個(gè)步驟直到某一輸入堆為空。 這時(shí)把另一個(gè)輸入堆中余下的牌面朝下放入即可。

Procedure Merge(Var A: ListType; p, q, r : Integer);
          {將兩個(gè)已排好序的子序列A[p..q]和A[q+1..r]合并成一個(gè)已排好序的序列A[p..r]}
          Var
            i, j, t : Integer;{左子序列指針;右子序列指針;合并后的序列的指針}
            Lt      : ListType;{暫存合并的序列}
          Begin
            t := p; i := p; j := q + 1;
            While t <= r Do Begin{若合并未完成,則循環(huán)}
              If (i <= q) And ((j > r) Or (A[i] <= A[j]))  Then Begin
             {若左序列剩有元素并且右序列元素全部合并或者左序列的首元素小于等于右序列的首元素,
              則左序列的首元素進(jìn)入合并序列,左序列的首指針+1}
                Lt[t] := A[i]; Inc(i)
              End{then}
              Else Begin{否則左序列的首元素進(jìn)入合并序列,右序列的首指針+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)

現(xiàn)在就可以把merge過(guò)程作為合并排序的一個(gè)子過(guò)程來(lái)用了。下面是merge_sort(A,P,R)對(duì)數(shù)組A〔P..R〕進(jìn)行排序。若P ≥R，該子數(shù)組至多只有一個(gè)元素， 當(dāng)然就是已排序的。否則，分解步驟就計(jì)算出一個(gè)中間下標(biāo)Q，而將A〔P..R〕分成A〔P..Q〕和A〔Q+1..R 〕。若數(shù)組A〔P..R〕的元素個(gè)數(shù)K＝R－P+1為偶數(shù)，則兩個(gè)數(shù)組各含K/2個(gè)元素;否則A〔P..Q〕含[k/2]+1( k/2 )元素、A〔Q+1，R〕含[k/2]( k /2 )個(gè)元素。

Procedure Merge_Sort(Var A : ListType; p, r : Integer);
          Var
            q : Integer;
          Begin
            If p <> r Then Begin{若子序列A中不止一個(gè)元素}
              q := (p + r - 1) div 2;{計(jì)算中間下標(biāo)q}
              Merge_Sort(A, p, q);{繼續(xù)對(duì)左子序列A[p..q]遞歸排序}
              Merge_Sort(A, q + 1, r);{繼續(xù)對(duì)右子序列A[q+1..r]遞歸排序}
              Merge(A, p, q ,r){對(duì)左子序列和右子序列合并排序}
            End{then}
          End;{Merge_sort}

我們只要調(diào)用merge_sort(A，1，N)便可對(duì)整個(gè)序列A〔1〕……A〔n〕進(jìn)行合并排序。如果我們自底向上(此處“底”為n是2的冪時(shí))來(lái)看這個(gè)過(guò)程的操作時(shí)，算法將兩個(gè)長(zhǎng)度為1的序列合并成排好序的長(zhǎng)度為2的序列，繼而合并成長(zhǎng)度為4的序列……，依次類推。 隨著算法自底向上執(zhí)行，被合并的排序序列長(zhǎng)度逐漸增加，一直進(jìn)行到將兩個(gè)長(zhǎng)度為n／2 的序列合并成最終排好序的長(zhǎng)度為n的序列。下圖列出了對(duì)序列(5，2，4，6，1，3，2，6)進(jìn)行合并排序的過(guò)程。

( 圖1.4-1 )

當(dāng)然，排序算法很多，但合并排序法也有其本身的特點(diǎn)──當(dāng)輸入的規(guī)模足夠大時(shí)，合并排序的運(yùn)行時(shí)間要比最壞情況下的插入排序好。分治算法不僅可應(yīng)用于排序，而且還可應(yīng)用于許多重要的場(chǎng)合，甚至有些問(wèn)題看起來(lái)非得采用分治法求解不可。

【例2】導(dǎo)線和開(kāi)關(guān)

如(圖1.4-2)所示，具有3根導(dǎo)線的電纜把A區(qū)和B區(qū)連接起來(lái)。在A區(qū)3根導(dǎo)線標(biāo)以1，2，3;在B區(qū)導(dǎo)線1和3被連到開(kāi)關(guān)3，導(dǎo)線2連到開(kāi)關(guān)1。

一般說(shuō)來(lái)，電纜含m(1≤m≤90)根導(dǎo)線，在A區(qū)標(biāo)以1，2，...m。在B區(qū)有m個(gè)開(kāi)關(guān)， 標(biāo)為1，2，...m。每一根導(dǎo)線都被嚴(yán)格地連到這些開(kāi)關(guān)中的某一個(gè)上;每一個(gè)開(kāi)關(guān)上可以連有0根或多根導(dǎo)線。

( 圖1.4-2 )

測(cè)量

你的程序應(yīng)作某些測(cè)量來(lái)確定，導(dǎo)線和開(kāi)關(guān)怎樣連。 每個(gè)開(kāi)關(guān)或處于接通或處于斷開(kāi)狀態(tài)，開(kāi)關(guān)的初始狀態(tài)為斷開(kāi)。我們可用一個(gè)探頭(probe)P在A區(qū)進(jìn)行測(cè)試: 如果探頭點(diǎn)到某根導(dǎo)線上，當(dāng)且僅當(dāng)該導(dǎo)線連到處接通狀態(tài)的開(kāi)關(guān)時(shí)，燈L才會(huì)點(diǎn)亮。

你的程序從標(biāo)準(zhǔn)輸入(standard input)讀入一行以得到數(shù)字m; 然后可以通過(guò)向標(biāo)準(zhǔn)輸出(standard output)寫入一行以發(fā)出命令(共3種命令)。每種命令的開(kāi)頭是一個(gè)大寫字母:

○測(cè)試導(dǎo)線命令T:T后面跟一個(gè)導(dǎo)線標(biāo)號(hào);

○改變開(kāi)關(guān)狀態(tài)命令C:C后面跟一個(gè)開(kāi)關(guān)標(biāo)號(hào);

○完成命令D:D后面跟的是一個(gè)表列(LIST)，該表列中的第ｉ個(gè)元素代表與導(dǎo)線ｉ相 連的開(kāi)關(guān)號(hào)。

在命令T和C之后，你的程序應(yīng)從標(biāo)準(zhǔn)輸入(standard input)讀入一行。 若開(kāi)關(guān)狀態(tài)能使燈亮，則命令T的回答應(yīng)是Y;反之，回答應(yīng)是N。命令C的作用是改變開(kāi)關(guān)的狀態(tài)( 若原來(lái)是接通則變?yōu)閿嚅_(kāi);若原來(lái)是斷開(kāi)則變?yōu)榻油?。對(duì)C命令的回答是作為一種反饋信號(hào)。

你的程序可以給出一系列命令，將T命令與C命令以任意順序混合使用。最后給出命令D，并結(jié)束。你的程序給出的命令總數(shù)應(yīng)不大于900。

注意

為了在此任務(wù)中能正確使用標(biāo)準(zhǔn)輸入(standard input)和標(biāo)準(zhǔn)輸出(standard output)。若你使用pascal，請(qǐng)不要使用其中的CRT單元(unit CRT)。

舉例

(圖1.4-3)給出了一個(gè)實(shí)例，對(duì)應(yīng)于(圖1.4-2)，這是一個(gè)有8條命令的對(duì)話。

┌──────────┐ ┌─────────┐
│  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           │ │                  │
└──────────┘ └─────────┘

算法分析:

這是一道通過(guò)人機(jī)對(duì)話解答的程序題。程序執(zhí)行時(shí)，由計(jì)算機(jī)發(fā)出T或C命令。 用戶通過(guò)鍵盤輸入應(yīng)答信號(hào)。人與計(jì)算機(jī)間幾次交互信息后，最終由計(jì)算機(jī)給出命令D并顯示導(dǎo)線和開(kāi)關(guān)怎樣連接的。對(duì)于編程序者來(lái)說(shuō)，要解決的問(wèn)題是如何設(shè)計(jì)命令順序， 使得用戶在依次應(yīng)答后，程序能自動(dòng)給出問(wèn)題的解。

1.T命令和C命令的作用

初始時(shí)，B區(qū)M個(gè)開(kāi)關(guān)斷開(kāi)。此時(shí)無(wú)論用探頭P在A區(qū)測(cè)哪根導(dǎo)線，燈L也不會(huì)亮。因此，程序首先必須使用C命令和用戶應(yīng)答將B區(qū)的部分開(kāi)關(guān)閉合。然后發(fā)出測(cè)試某些導(dǎo)線的T命令，通過(guò)用戶應(yīng)答確定這些導(dǎo)線在B區(qū)的準(zhǔn)確位置或范圍。若尚有導(dǎo)線未連接，則再通過(guò)C 命令和用戶應(yīng)答來(lái)改變某些開(kāi)關(guān)的狀態(tài)，隨后發(fā)出T命令……，C命令和T命令交替使用，直到完成導(dǎo)線和開(kāi)關(guān)的連接 。例如 M＝3。初始時(shí)

( 圖1.4-4 )

對(duì)話序號(hào)         計(jì)算機(jī)命令    用戶應(yīng)答      結(jié)果
                 1               C3            Y          開(kāi)關(guān)3閉合
                 2               T1            Y          L燈亮，導(dǎo)線1與開(kāi)關(guān)3連接
                 3               T2            N          導(dǎo)線2不與開(kāi)關(guān)3連接
                 4               T3            Y          導(dǎo)線3與開(kāi)關(guān)3連接

( 圖1.4-5 )

對(duì)話序號(hào)         計(jì)算機(jī)命令      用戶應(yīng)答    結(jié)果     
                5                C3              N        開(kāi)關(guān)3斷開(kāi)
                6                C2              Y        開(kāi)關(guān)2閉合
                7                T2              N        導(dǎo)線1與開(kāi)關(guān)3連結(jié)

( 圖1.4-6 )

由此可見(jiàn),改變開(kāi)關(guān)狀態(tài)的C命令在人機(jī)對(duì)話中最先使用,然后發(fā)出T命令測(cè)試部分導(dǎo)線。若不能確定每根導(dǎo)線的連接位置，則還得對(duì)一些開(kāi)關(guān)使用C命令，改變其開(kāi)關(guān)狀態(tài)，直到最后一個(gè)T命令完成導(dǎo)線與開(kāi)關(guān)的連接為止。注意，用戶對(duì)C 命令的回答僅是作為開(kāi)關(guān)狀態(tài)改變的一種反饋信號(hào)。即無(wú)論用戶怎樣應(yīng)答， 開(kāi)關(guān)狀態(tài)總是由應(yīng)答前的斷開(kāi)變?yōu)閼?yīng)答后的閉合，或者由應(yīng)答前的閉合變?yōu)閼?yīng)答后的斷開(kāi)。

繼C命令后使用T命令測(cè)試導(dǎo)線。測(cè)試導(dǎo)線i的過(guò)程中

若僅一個(gè)開(kāi)關(guān)閉合且燈亮(即Ti的應(yīng)答為Y)，則被測(cè)導(dǎo)線i與閉合的開(kāi)關(guān)連接;

若僅一個(gè)開(kāi)關(guān)斷開(kāi)且燈暗(即Ti的應(yīng)答為N)，則被測(cè)導(dǎo)線i與斷開(kāi)的開(kāi)關(guān)連接;

若多個(gè)開(kāi)關(guān)閉合時(shí)燈亮(Ti的應(yīng)答為Y)或者多個(gè)開(kāi)關(guān)斷開(kāi)時(shí)燈暗(Ti的應(yīng)答為N)) ，而先前的測(cè)試已確定導(dǎo)線i只能與這些開(kāi)關(guān)中的某一個(gè)相連，則導(dǎo)線與之相連。

例如:第7次對(duì)話，用戶應(yīng)答T2的命令為N，而此時(shí)開(kāi)關(guān)1、3斷開(kāi)，看來(lái)導(dǎo)線2 即可能與開(kāi)關(guān)1相連，也可能與開(kāi)關(guān)3相連。但是先前第3次對(duì)話，用戶應(yīng)答T2命令為N，確認(rèn)導(dǎo)線2不與開(kāi)關(guān)3連接。無(wú)庸置疑，導(dǎo)線2的連接對(duì)象僅一個(gè)─開(kāi)關(guān)1。

2.用二分法連接

為了使導(dǎo)線和開(kāi)關(guān)間的連接工作有規(guī)律地進(jìn)行，我們不妨采用二分法。

設(shè)當(dāng)前待連接的開(kāi)關(guān)為HEAD.. TAIL，初始時(shí)為1..M。將這些開(kāi)關(guān)一分為二:

左區(qū)間HEAD..[(HEAD+TAIL－1)/2];

右區(qū)間[(HEAD+TAIL－1)/2]+1..TAIL;

連接到左區(qū)間開(kāi)關(guān)的導(dǎo)線集合為P1。初始時(shí)P1＝〔1..M〕;

連接到右區(qū)間開(kāi)關(guān)的導(dǎo)線集合為P2。顯然初始時(shí)P2＝〔 〕;

左區(qū)間或右區(qū)間開(kāi)關(guān)狀態(tài)是同一的，設(shè)為STATE。

┌1      區(qū)間的所有開(kāi)關(guān)閉合;
                                │
                         STATE＝│
                                │
                                └0      區(qū)間所有開(kāi)關(guān)斷開(kāi);
                         顯然初始時(shí)STATE＝0;

首先，P2集合設(shè)空并發(fā)出C命令，將左區(qū)間的所有開(kāi)關(guān)取反。然后對(duì)P1集合中的每根導(dǎo)線發(fā)出T命令。若用戶應(yīng)答N(燈暗)而左區(qū)間開(kāi)關(guān)閉合，或者用戶應(yīng)答Y(燈亮)而左區(qū)間開(kāi)關(guān)斷開(kāi)，則說(shuō)明相連的導(dǎo)線不在P1中，應(yīng)從P1集合移入P2集合。

接下去，設(shè)左區(qū)間開(kāi)關(guān)為待接開(kāi)關(guān)，與之相連的導(dǎo)線集合為P1，開(kāi)關(guān)狀態(tài)已由先前的C命令取反。繼續(xù)上述過(guò)程，直至出現(xiàn)下述兩種情況之一為止:

①P1的集合為空;

②區(qū)間內(nèi)的開(kāi)關(guān)僅剩一個(gè)，將P1集合中所有導(dǎo)線連接到這個(gè)開(kāi)關(guān);最后再將右區(qū)間開(kāi)關(guān)設(shè)為待連接開(kāi)關(guān)，與之相連的導(dǎo)線集合為P2，開(kāi)關(guān)狀態(tài)不變。仍按上述方法進(jìn)行連接。

顯然，可以用一個(gè)二分法的遞歸過(guò)程來(lái)描述導(dǎo)線與開(kāi)關(guān)間的連接:

procedure check(P1，開(kāi)關(guān)區(qū)間，state);
            begin  
              if P1 <>〔〕then
              if  區(qū)間內(nèi)剩一個(gè)開(kāi)關(guān)
              then P1集合中的所有導(dǎo)線與之相連
              else  begin 
                通過(guò)C命令和用戶應(yīng)答將左區(qū)間取反;
                P2集合設(shè)空;
                對(duì)P1集合中的每根導(dǎo)線發(fā)出T命令:
                if((用戶應(yīng)答N)and(state=0))or((用戶應(yīng)答Y)and(state=1))   
                  then   導(dǎo)線從P1集合移出，移入P2集合;
                check(P1，左區(qū)間，1－state);
                check(P2，右區(qū)間，state);
              end;    {else}
            end;     {check}