2.2 分治法

2.2.1 分治法的設計思想

分治者，分而治之也。分治法（divideandconquermethod）的設計思想是將一個難以直接解決的大問題，劃分成一些規(guī)模較小的子問題，以便各個擊破，分而治之。由分治法產生的子問題往往是原問題的較小模式，反復應用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到能夠直接求解，這自然導致遞歸。分治與遞歸經常同時應用在算法設計之中，并由此產生許多高效的算法。

一般來說，分治法的求解過程由以下三個階段組成：

（1）劃分：把規(guī)模為n的原問題劃分為k個規(guī)模較小的子問題。

（2）求解：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環(huán)來實現(xiàn)。

（3）合并：把各個子問題的解合并起來，合并的代價因情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實現(xiàn)。

人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。也就是將一個問題劃分成大小相等的k個子問題（通常k=2），這種使子問題規(guī)模大致相等的做法是出自一種平衡（bal-ancing）子問題的啟發(fā)式思想。另外，在用分治法設計算法時，最好使各子問題之間相互獨立，這涉及到分治法的效率，如果各子問題不是獨立的，則分治法需要重復地求解公共的子問題，此時雖然也可以用分治法，但一般用動態(tài)規(guī)劃法較好。圖2-2所示是分治法的典型情況。

圖2-2 分治法的典型情況

例如，對于給定的整數(shù)a和非負整數(shù)n，采用分治法計算an的值，如果n=1，可以簡單地返回a的值；如果n＞1，可以把該問題分解為兩個子問題：計算前└n/2」個a的乘積和后「n/2┐個a的乘積，再把這兩個乘積相乘得到原問題的解。所以，應用分治技術得到如下遞推關系式：

同應用蠻力法把1和a相乘n次相比，這是一個更高效的算法嗎？由于把原問題an分解為兩個子問題a└n/2」和a「n/2┐，這兩個子問題需要分別求解，根據(jù)1.4.3節(jié)通用分治遞推式的定理，其時間復雜度為O（nlog2n），而蠻力法計算an的值，其時間復雜度為O（n）。因此，不是所有的分治法都比簡單的蠻力法更有效，但是，正確使用分治法往往比使用其他算法設計方法的效率更高，事實上，分治法孕育了計算機科學中許多重要的和有效的算法。在本書中，二叉樹的遍歷、圖的深度優(yōu)先遍歷、快速排序、歸并排序等都是分治法的應用實例。

2.2.2 算法設計實例——數(shù)字旋轉方陣

【問題】 輸出如圖2-3（a）所示N×N（1≤N≤10）的數(shù)字旋轉方陣。

圖2-3 數(shù)字旋轉方陣示例

【想法】 用二維數(shù)組data[N][N]表示N×N的方陣，觀察方陣中數(shù)字的規(guī)律，可以從外層向里層填數(shù)，如圖2-3（b）所示。在填數(shù)過程中，每一層的起始位置很重要。設變量size表示方陣的大小，則初始時size=N，填完一層則size=size-2；設變量begin表示每一層的起始位置，變量i和j分別表示行號和列號，則每一層初始時i=begin，j=begin。將每一層的填數(shù)過程分為A、B、C、D四個區(qū)域，每個區(qū)域需要填寫size-1個數(shù)字，且填寫區(qū)域A時列號不變行號加1，填寫區(qū)域B時行號不變列號加1，填寫區(qū)域C時列號不變行號減1，填寫區(qū)域D時行號不變列號減1。顯然，遞歸的邊界條件是size等于0或size等于1。

【算法】 設遞歸函數(shù)Full實現(xiàn)填數(shù)過程，算法用偽代碼描述如下 ：

【程序】 由于遞歸函數(shù)Full在調用過程中需要對同一個數(shù)組data[N][N]填數(shù)，為避免傳遞參數(shù)，將數(shù)組data[N][N]設為全局變量，程序如下：

            #include＜stdio.h＞                            //使用庫函數(shù)printf和scanf
            #defineN10                                     //定義符號常量N
            intdata[N][N]={0}；                            //定義全局數(shù)組data[N][N]并初始化為0
            voidFull（intnumber，intbegin，intsize）；     //函數(shù)聲明，填寫旋轉方陣
            voidOutPrint（intsize）；                      //函數(shù)聲明，輸出旋轉方陣
                                                           //空行，以下是主函數(shù)
            intmain（）
            {
              intn；
              printf（＂請輸入方陣的階數(shù)（小于10）：＂）； //輸出提示信息
              scanf（＂%d＂，&n）；
              Full（1，0，n）；                            //函數(shù)調用，從1開始填寫n階方陣，左上角的下標為（0，0）
              OutPrint（n）；                              //函數(shù)調用，輸出n階方陣
              return0；                                    //將0返回操作系統(tǒng)，表明程序正常結束
            }
                                                           //空行，以下是其他函數(shù)定義
            voidFull（intnumber，intbegin，intsize）
            {                                              //從number開始填寫size階方陣，左上角的下標為（begin，begin）
              inti，j，k；
              if（size==0）                                //遞歸的邊界條件，如果size等于0，則無須填寫
                  return；
              if（size==1）                                //遞歸的邊界條件，如果size等于1
              {
                  data[begin][begin]=number；              //則只須填寫number

                  return；
              }
              i=begin；j=begin；                           //初始化左上角下標
              for（k=0；k＜size-1；k++）                   //填寫區(qū)域A，共填寫size-1個數(shù)
              {
                  data[i][j]=number；number++；            //在當前位置填寫number
                  i++；                                    //行下標加1
              }
              for（k=0；k＜size-1；k++）                   //填寫區(qū)域B，共填寫size-1個數(shù)
              {
                  data[i][j]=number；number++；            //在當前位置填寫number
                  j++；                                    //列下標加1
              }
              for（k=0；k＜size-1；k++）                   //填寫區(qū)域C，共填寫size-1個數(shù)
              {
                  data[i][j]=number；number++；            //在當前位置填寫number
                  i--；                                    //行下標減1
              }
              for（k=0；k＜size-1；k++）                   //填寫區(qū)域D，共填寫size-1個數(shù)
              {
                  data[i][j]=number；number++；            //在當前位置填寫number
                  j--；                                    //列下標減1
              }
              Full（number，begin+1，size-2）；            //遞歸調用，左上角下標為begin+1
              return；                                     //結束函數(shù)Full的執(zhí)行
            }
            voidOutPrint（intsize）                        //函數(shù)調用，輸出size階方陣
            {
              inti，j；
              for（i=0；i＜size；i++）                     //輸出第i行
              {
                  for（j=0；j＜size；j++）                 //輸出第j列
                    printf（＂%4d＂，data[i][j]）；
                  printf（＂\n＂）；                       //輸出一行后輸出換行符
              }
              return；                                     //結束函數(shù)OutPrint的執(zhí)行
            }