【正文】 第 4章 算法設計策略 ? 分治策略 ? 回溯策略 ? 貪心策略 ? 分枝界定策略 ? 動態(tài)規(guī)劃 算法設計策略 分治策略 任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關。直接求解一個規(guī)模較大的問題，往往是相當困難的。但是當問題的規(guī)?？s小到一定程度時，一個量變到質變的現(xiàn)象就可能發(fā)生，問題的求解變得比較容易。這時，如果能找到小規(guī)模的該類問題與大規(guī)模的該類問題之間的關系，就可以使用分治策略對大規(guī)模的問題進行求解了。 分治法所能解決的問題一般具有以下幾個特征： （ 1）該問題可以分解為若干個規(guī)模較小的相同問題。 （ 2）各個子問題相互獨立，子問題之間不包含公共的子子問題。 （ 3）該問題的規(guī)?？s小到一定的程度可以容易地求解。 （ 4）利用該問題分解出的子問題的解可以合并為該問題的解。 ? 二分查找 ? 快速排序 ? 自行車帶人問題 分治法往往要依靠遞歸過程，并且大致有如下三個步驟： 分解：將原問題分解為若干個規(guī)模較小、相互獨立，與原問題形式相同的子問題。 解決：若子問題規(guī)模較小而容易被解決則直接解決，否則遞歸地解決各個子問題。 合并：將各個子問題的解合并為原問題的解。 這一節(jié)，介紹幾種使用分治策略的例子。 二分查找 一、問題描述 在 N個已排序（設為從小到大）的數(shù)據(jù)（數(shù)或字符串），查詢某一個數(shù)據(jù)：如果找到了，就指出其在 N個數(shù)據(jù)中的位置；否則給出無該數(shù)據(jù)的信息，如給出“ 1”。 查詢是在一個數(shù)據(jù)集中，查找給定數(shù)據(jù)的過程。查詢的結果有兩種情形：找到給定的數(shù)據(jù)，并給出其位置；找不到給定數(shù)據(jù)。 二、算法分析 采用二分法求解本問題的基本思路是：如 圖 ，設數(shù)列為 aa …a n，被查找的數(shù)據(jù)為 x，則查找首先對 am(m=(1+n)/2)進行，于是得到如下 3種情形： 若 xam，則 x可能在區(qū)間 [ am+1,an]中。 若 xam，則 x可能在區(qū)間 [a1,am1]中。 若 x=am，則以 am為所查找數(shù)據(jù) x，求解結束。 這樣，當一次搜索沒有找到解時，便把搜索范圍縮小一半，可以再在新的搜索范圍內按上述原則進行搜索，不斷二分，直到得出結論（找到或找不到）為止。 a1 a2 … … a m am＋ 1 … x … a n 第 1次 s m r 第 2次 s’ r’ 圖 二分查詢 為了使算法更具一般性，設數(shù)列為 as、 as+ … 、 ar、 s為數(shù)列的起始元素序號（開始時為 1）， r為數(shù)列的終止元素序號（開始時為 n），則利用二分查找法在其中找出元素 x的遞歸函數(shù) binsrch（ s,r,x）可描述為： binsrch（ s,r,x） { m=(s+r)/2。 if(x==am) 打印找到信息后返回 。 else if(s=r) 打印找不到信息 ,結束程序執(zhí)行 。 else if(xam) 調用函數(shù) binsrch（ m+1,r,x） 。 else 調用函數(shù) binsrch（ s,m1,x） 。 } 三、程序 include float a[10]={,, ,}。 /* 數(shù)組聲明及初始化，外部數(shù)組 */ void main() { float x=。 int s=0,r=9。 void binsrch(int s,int r,float x)。 /* 函數(shù)聲明 */ binsrch(s,r,x)。 /* 函數(shù)調用 */ } 三、程序（續(xù)） void binsrch(int s,int r,float x) { int m。 m=(s+r)/2。 if(a[m]==x) { printf(The order of % is %d in this sequence.,x,m+1)。 return。 } else if(s=r) { printf(%f is not exist in the seguense.,x)。 exit(1)。 } else if(xa[m]) binsrch(m+1,r,x)。 /* 遞歸調用 */ else binsrch(s,m1,x)。 /* 遞歸調用 */ } 四、說明 1. 外部數(shù)組 在本例中，聲明語句 float a[10]={,,,}。 定義在所有函數(shù)的外部，即不在任何一個函數(shù)內。這種定義在函數(shù)外部的數(shù)組，稱為外部數(shù)組。一般來說，定義在外部的變量稱為外部變量。外部變量是在每一個函數(shù)中都可以使用的變量。相對而言，前面使用過的、定義在某一個函數(shù)內部的變量稱為局部變量，它只能在所定義的局部使用。 五、編程練習 1. 用二分法求一元方程式的根（提示：用二分迭代法）。 2. 用二分法計算 xn的值（提示：當 n為偶數(shù)時，使用xn=xp*xp；當 n為奇數(shù)時，使用 xn=x*xp*xp）。 3. 用二分法找出一個數(shù)組中的最大值和最小值。 快速排序 一、快速排序的基本思想： 快速排序（ quick sort）是由著名計算機科學家 排序方法。 它的基本思想是：在待排序序列中選定一個元素 X(可以任選，也可以選第一個元素 )，稱為劃分元素，用它將原序列整理 ——劃分（ partitioning）為兩個子序列，使其左邊的元素不比它大，使其右邊的元素不比它??；然后再對兩個子序列進行上述劃分；經(jīng)過不斷劃分，直至將原序列整理完畢為止，如 圖 。 5 7 9 8 1 6 3 4 2 開始： 2 4 3 1 6 8 9 7 p 5 6 5 2 1 4 8 9 7 3 4 p p p p p 9 7 5 6 1 2 3 8 p p p 結果： 圖 快速排序示例 二、算法框架 qksort(int m,int n) /* 序列由 m到 n */ { if(mn) { 調用劃分函數(shù) part(m,n,i)。 遞歸調用 qksort(m,i1)。 遞歸調用 qksort(i+1,m)。 } else { 輸出排序結束信息 return。 } } 下面進一步考慮如何描述函數(shù) part()?；舅悸啡缦拢? 基本思路 步驟 1：準備： 步驟 ：設置兩個指針 i和 j，分別指向待劃分序列的首尾元素 a[m]和 a[n]； 步驟 ：選取劃分元素 p=a[k]（ k屬于 [m,n]）， 將 a[m]移至 k，即令 a[k]=a[m]。 步驟 2：劃分：當 ij時，反復執(zhí)行下面的操作（參見 圖 ）： 步驟 ：逐步減小 j：將 a[j]與 p比較，若 a[j]p,則令 j（ j左移一個數(shù)據(jù)位） 。否則，令 a[i]=a[j](將 a[j]放在 i位置 )。 步驟 ：逐步增加 i：將 a[i]與 p比較，若 a[i]p,則令 i++（ i右移一個數(shù)據(jù)位） 。否則，令 a[j]=a[i](將 a[i]放在 j位置 )。 步驟 3：如果 i=j,放置劃分元素：令 A[i]=p。 5 7 9 8 1 6 3 4 2 i j p = 5 2 7 9 8 1 6 3 4 2 i j a[j]p, a[i] = a[j] 轉向逐步增大 i 2 7 9 8 1 6 3 4 7 a[i]p, a[j] = a[i] 轉向減少 j j i j 2 4 9 8 1 6 3 4 7 a[j]p, a[i] = a[j] 轉向逐步增大 i i 2 4 9 8 1 6 3 9 7 a[i]p, a[j] = a[i] 轉向減少 j i j 2 4 3 8 1 6 3 9 7 a[j]p, a[i] = a[j] 轉向逐步增大 i i j 2 4 3 8 1 6 8 9 7 a[i]p, a[j] = a[i] 轉向減少 j i j 2 4 3 8 1 6 8 9 7 a[j]p, 繼續(xù)減少 j j 2 4 3 1 1 6 8 9 7 a[j]p, a[i] = a[j] 轉向逐步增大 i i i j 2 4 3 1 1 6 8 9 7 i = j,放置劃分元素 5 圖 一次劃分示意圖 劃分函數(shù) int part(int low,int high) { int i,j。 float p。 i=low。 j=high。 /* 準備 */ p=a[low]。 while(ij) { while(ij amp。amp。 a[j]=p) /* 逐步減小 j */ j。 a[i]=a[j]。 while(ij amp。amp。 a[i]=p) /* 逐步增大 i */ i++。 a[j]=a[i]。 } a[i]=p。 /* 放置劃分元素 */ return(i)。 } 三、程序 include define N 10 float a[]={,,,}。 void main() { int m=0,n=N1。 void qksort(int m,int n)。 int part(int m,int n)。 void prnt()。 qksort(m,n)。 prnt()。 } 三、程序（續(xù)） void qksort(int low,int high) { int i。 if(lowhigh) { i=part(low,high)。 qksort(low,i1)。 qksort(i+1,high)。 } else return。 } 三、程序（續(xù)） int part(int low,int high) { 參見前面“劃分函數(shù)”部分 } void prnt() { int i。 printf(\nsorted sequence is:\n)。 for(i=0。i=N1。i++) printf(%,a[i])。 } 四、運行結果 sorted sequenc is: ,