【問題】       馬的遍歷

    問題描述：在8×8方格的棋盤上，從任意指定的方格出發(fā)，為馬尋找一條走遍棋盤每一格并且只經(jīng)過一次的一條路徑。

       馬在某個方格，可以在一步內(nèi)到達的不同位置最多有8個，如圖所示。如用二維數(shù)組board[ ][ ]表示棋盤，其元素記錄馬經(jīng)過該位置時的步驟號。另對馬的8種可能走法（稱為著法）設(shè)定一個順序，如當前位置在棋盤的（i，j）方格，下一個可能的位置依次為（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-1）、（i-1，j-2）、（i+1，j-2）、（i+2，j-1），實際可以走的位置盡限于還未走過的和不越出邊界的那些位置。為便于程序的同意處理，可以引入兩個數(shù)組，分別存儲各種可能走法對當前位置的縱橫增量。

 

       對于本題，一般可以采用回溯法，這里采用Warnsdoff策略求解，這也是一種貪婪法，其選擇下一出口的貪婪標準是在那些允許走的位置中，選擇出口最少的那個位置。如馬的當前位置（i，j）只有三個出口，他們是位置（i+2，j+1）、（i-2，j+1）和（i-1，j-2），如分別走到這些位置，這三個位置又分別會有不同的出口，假定這三個位置的出口個數(shù)分別為4、2、3，則程序就選擇讓馬走向（i-2，j+1）位置。

       由于程序采用的是一種貪婪法，整個找解過程是一直向前，沒有回溯，所以能非�？斓卣业浇�。但是，對于某些開始位置，實際上有解，而該算法不能找到解。對于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找到解。改變出口選擇順序，就是改變有相同出口時的選擇標準。以下程序考慮到這種情況，引入變量start，用于控制8種可能著法的選擇順序。開始時為0，當不能找到解時，就讓start增1，重新找解。細節(jié)以下程序。

【程序】

# include <stdio.h>

int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};

int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};

int board[8][8];

int exitn(int i,int j,int s,int a[ ])

{     int i1,j1,k,count;

       for (count=k=0;k<8;k++)

       {     i1=i+delta_i[(s+k)%8];

              j1=i+delta_j[(s+k)%8];

              if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)

                     a[count++]=(s+k)%8;

       }

       return count;

}

 

int next(int i,int j,int s)

{     int m,k,mm,min,a[8],b[8],temp;

       m=exitn(i,j,s,a);

       if (m==0)              return –1;

       for (min=9,k=0;k<m;k++)

       {     temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);

              if (temp<min)

              {     min=temp;

kk=a[k];

              }

       }

       return  kk;

}

 

void main()

{     int sx,sy,i,j,step,no,start;

       for (sx=0;sx<8;sx++)

       for (sy=0;sy<8;sy++)

       {     start=0;

              do {

                     for (i=0;i<8;i++)

                            for (j=0;j<8;j++)

                                   board[i][j]=0;

                     board[sx][sy]=1;

                     I=sx;       j=sy;

                     For (step=2;step<64;step++)

                     {     if ((no=next(i,j,start))==-1)   break;

                            I+=delta_i[no];

                            j+=delta_j[no];

                            board[i][j]=step;

                     }

                     if (step>64)    break;

                     start++;

              } while(step<=64)

              for (i=0;i<8;i++)

              {     for (j=0;j<8;j++)

                            printf(“%4d”,board[i][j]);

                     printf(“\n\n”);

              }

              scanf(“%*c”);

       }

}

七、分治法

1、分治法的基本思想

    任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模N有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當困難的。

    分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

    如果原問題可分割成k個子問題（1<k≤n），且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。

2、分治法的適用條件

    分治法所能解決的問題一般具有以下幾個特征：

（1）該問題的規(guī)�？s小到一定的程度就可以容易地解決；

（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；

（3）利用該問題分解出的子問題的解可以合并為該問題的解；

（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

    上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是應用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心法或動態(tài)規(guī)劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好。

3、分治法的基本步驟

    分治法在每一層遞歸上都有三個步驟：

（1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；

（2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；

（3）合并：將各個子問題的解合并為原問題的解。

    它的一般的算法設(shè)計模式如下：

Divide_and_Conquer（P）

if |P|≤n₀

then return（ADHOC（P））

將P分解為較小的子問題P₁、P₂、…、P_k

for i←1 to k

do

y_i ← Divide-and-Conquer（P_i）               △ 遞歸解決Pi

T ← MERGE（y₁，y₂，…，y_k）                          △ 合并子問題

Return（T）

    其中 |P| 表示問題P的規(guī)模；n₀為一閾值，表示當問題P的規(guī)模不超過n₀時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當P的規(guī)模不超過n₀時，直接用算法ADHOC（P）求解。

    算法MERGE（y₁，y₂，…，y_k）是該分治法中的合并子算法，用于將P的子問題P₁、P₂、…、P_k的相應的解y₁、y₂、…、y_k合并為P的解。

    根據(jù)分治法的分割原則，原問題應該分為多少個子問題才較適宜？各個子問題的規(guī)模應該怎樣才為適當？這些問題很難予以肯定的回答。但人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子問題規(guī)模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。

    分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應該怎樣合并，沒有統(tǒng)一的模式，需要具體問題具體分析。

【問題】       大整數(shù)乘法

問題描述：

    通常，在分析一個算法的計算復雜性時，都將加法和乘法運算當作是基本運算來處理，即將執(zhí)行一次加法或乘法運算所需的計算時間當作一個僅取決于計算機硬件處理速度的常數(shù)。

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

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

     設(shè)X和Y都是n位的二進制整數(shù)，現(xiàn)在要計算它們的乘積XY。我們可以用小學所學的方法來設(shè)計一個計算乘積XY的算法，但是這樣做計算步驟太多，顯得效率較低。如果將每2個1位數(shù)的乘法或加法看作一步運算，那么這種方法要作O(n²)步運算才能求出乘積XY。下面我們用分治法來設(shè)計一個更有效的大整數(shù)乘積算法。

圖6-3 大整數(shù)X和Y的分段

    我們將n位的二進制整數(shù)X和Y各分為2段，每段的長為n/2位（為簡單起見，假設(shè)n是2的冪），如圖6-3所示。

由此，X=A2^n/2+B，Y=C2^n/2+D。這樣，X和Y的乘積為：

XY=(A2^n/2+B)(C2^n/2+D)=AC2ⁿ+(AD+CB)2^n/2+BD    （1）

    如果按式（1）計算XY，則我們必須進行4次n/2位整數(shù)的乘法(AC，AD，BC和BD)，以及3次不超過n位的整數(shù)加法（分別對應于式（1）中的加號），此外還要做2次移位（分別對應于式（1）中乘2ⁿ和乘2^n/2）。所有這些加法和移位共用O（n）步運算。設(shè)T（n）是2個n位整數(shù)相乘所需的運算總數(shù)，則由式（1），我們有：

                  （2）

    由此可得T（n）=O（n²）。因此，用（1）式來計算X和Y的乘積并不比小學生的方法更有效。要想改進算法的計算復雜性，必須減少乘法次數(shù)。為此我們把XY寫成另一種形式：

XY=AC2ⁿ+[(A-B)(D-C)+AC+BD]2^n/2+BD          （3）

    雖然，式（3）看起來比式（1）復雜些，但它僅需做3次n/2位整數(shù)的乘法（AC，BD和（A-B）（D-C）），6次加、減法和2次移位。由此可得：

                      （4）

    用解遞歸方程的套用公式法馬上可得其解為T(n)=O(n^log3)=O(n^1.59)。利用式（3），并考慮到X和Y的符號對結(jié)果的影響，我們給出大整數(shù)相乘的完整算法MULT如下：

function MULT(X，Y，n); {X和Y為2個小于2n的整數(shù)，返回結(jié)果為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(n²)的計算時間。我們能否找到問題的一個O (nlogn)算法。

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

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

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

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

    假設(shè)我們用x軸上某個點m將S劃分為2個子集S₁和S₂，使得S₁={x∈S | x≤m}；S₂={x∈S | x>m}。這樣一來，對于所有p∈S₁和q∈S₂有p<q。

    遞歸地在S₁和S₂上找出其最接近點對{p₁，p₂}和{q₁，q₂}，并設(shè)δ=min{|p₁-p₂|，|q₁-q₂|}，S中的最接近點對或者是{p₁，p₂}，或者是{q₁，q₂}，或者是某個{p₃，q₃}，其中p₃∈S₁且q₃∈S₂。如圖1所示。

圖1 一維情形的分治法

    我們注意到，如果S的最接近點對是{p₃，q₃}，即 | p₃-q₃ | < δ，則p₃和q₃兩者與m的距離不超過δ，即 | p₃-m | < δ，| q₃-m | < δ，也就是說，p₃∈(m-δ，m)，q₃∈(m，m+δ)。由于在S₁中，每個長度為δ的半閉區(qū)間至多包含一個點（否則必有兩點距離小于δ），并且m是S₁和S₂的分割點，因此(m-δ，m)中至多包含S中的一個點。同理，(m，m+δ)中也至多包含S中的一個點。由圖1可以看出，如果(m-δ，m)中有S中的點，則此點就是S₁中最大點。同理，如果(m，m+δ)中有S中的點，則此點就是S₂中最小點。因此，我們用線性時間就能找到區(qū)間(m-δ，m)和(m，m+δ)中所有點，即p₃和q₃。從而我們用線性時間就可以將S₁的解和S₂的解合并成為S的解。也就是說，按這種分治策略，合并步可在O(n)時間內(nèi)完成。這樣是否就可以得到一個有效的算法了呢？

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

T（n）=T（n-1）+O（n）

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

    至此，我們可以設(shè)計出一個求一維點集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ù);

               構(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(δ);

}

  

上一頁  [1] [2] [3] [4] [5] [6] 下一頁

轉(zhuǎn)帖于：計算機等級考試_考試吧