【正文】 最大加數(shù) n1實際上不能大于 n。因此， q(1,m)=1。 (1) q(n,1)=1,n?1。 當最大加數(shù) n1不大于 1時，任何正整數(shù) n只有一種劃分形式， 即 ????? ?nn 111 ???? (4) q(n,m)=q(n,m1)+q(nm,m),nm1。 正整數(shù) n的最大加數(shù) n1不大于 m的劃分由 n1=m的劃分和 n1≤n 1 的劃分組成。 (3) q(n,n)=1+q(n,n1)。 正整數(shù) n的劃分由 n1=n的劃分和 n1≤n 1的劃分組成。 遞歸的概念 例 5 整數(shù)劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設 p(n)為正整數(shù) n的劃分數(shù)，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)?？梢越?q(n,m)的如下遞歸關系。 ???????????????????11,1),()1,()1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq 遞歸的概念 例 5 整數(shù)劃分問題 前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設 p(n)為正整數(shù) n的劃分數(shù)，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數(shù) n1不大于 m的劃分個數(shù)記作 q(n,m)?？梢越?q(n,m)的如下遞歸關系。 正整數(shù) n的劃分數(shù) p(n)=q(n,n)。 遞歸的概念 例 6 Hanoi塔問題 設 a,b,c是 3個塔座。開始時，在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為 1,2,… ,n,現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則： 規(guī)則 1：每次只能移動 1個圓盤； 規(guī)則 2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則 3：在滿足移動規(guī)則 1和 2的前提下，可將圓盤移至 a,b,c中任一塔座上。 在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術來解決這個問題。 當 n=1時，問題比較簡單。此時，只要將編號為 1的圓盤從塔座 a直接移至塔座 b上即可。 當 n＞ 1時，需要利用塔座 c作為輔助塔座。此時若能設法將 n1個較小的圓盤依照移動規(guī)則從塔座 a移至塔座 c，然后，將剩下的最大圓盤從塔座 a移至塔座 b，最后，再設法將 n1個較小的圓盤依照移動規(guī)則從塔座 c移至塔座 b。 由此可見， n個圓盤的移動問題可分為 2次 n1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設計出解 Hanoi塔問題的遞歸算法如下。 遞歸的概念 例 6 Hanoi塔問題 void hanoi(int n, int a, int b, int c) { if (n 0) { hanoi(n1, a, c, b)。 move(a,b)。 hanoi(n1, c, b, a)。 } } 遞歸小結 優(yōu)點： 結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。 缺點： 遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。 解決方法： 在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。 采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。 用遞推來實現(xiàn)遞歸函數(shù)。 通過 變換能 將一些遞歸轉化為尾遞歸，從而迭代求出結果。 后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。 遞歸小結 分治法的適用條件 分治法所能解決的問題一般具有以下幾個特征： ? 該問題的規(guī)?？s小到一定的程度就可以容易地解決； ? 該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有 最優(yōu)子結構性質 ? 利用該問題分解出的子問題的解可以合并為該問題的解； ? 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。 這條特征是應用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用 能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮 貪心算法 或 動態(tài)規(guī)劃 。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用 動態(tài)規(guī)劃 較好。 divideandconquer(P) { if ( | P | = n0) adhoc(P)。 //解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,...,Pk； //分解問題 for (i=1,i=k,i++) yi=divideandconquer(Pi)。 //遞歸的解各子問題 return merge(y1,...,yk)。 //將各子問題的解合并為原問題的解 } 分治法的基本步驟 人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的 k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種 平衡(balancing)子問題 的思想，它幾乎總是比子問題規(guī)模不等的做法要好。 分治法的復雜性分析 一個分治法將規(guī)模為 n的問題分成 k個規(guī)模為 n／ m的子問題去解。設分解閥值 n0=1，且 adhoc解規(guī)模為 1的問題耗費 1個單位時間。再設將原問題分解為 k個子問題以及用 merge將 k個子問題的解合并為原問題的解需用 f(n)個單位時間。用 T(n)表示該分治法解規(guī)模為 |P|=n的問題所需的計算時間，則有： 11)()/()1()(???????nnnfmnkTOnT通過迭代法求得方程的解： ? ????1l o g0l o g )/()(nmjjjkm mnfknnT注意 ： 遞歸方程及其解只給出 n等于 m的方冪時 T(n)的值，但是如果認為 T(n)足夠平滑，那么由 n等于 m的方冪時 T(n)的值可以估計 T(n)的增長速度。通常假定 T(n)是單調上升的，從而當 mi≤nmi+1時， T(mi)≤T(n)T(mi+1)。 分析： 如果 n=1即只有一個元素，則只要比較這個元素和 x就可以確定 x是否在表中。因此這個問題滿足分治法的第一個適用條件 分析： 比較 x和 a的中間元素 a[mid]，若 x=a[mid]，則 x在 L中的位置就是 mid；如果 xa[mid]，由于 a是遞增排序的，因此假如 x在 a中的話， x必然排在 a[mid]的前面，所以我們只要在a[mid]的前面查找 x即可；如果 xa[i]，同理我們只要在 a[mid]的后面查找 x即可。無論是在前面還是后面查找 x，其方法都和在 a中查找 x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析： 很顯然此問題分解出的子問題相互獨立，即在 a[i]的前面或后面查找 x是獨立的子問題，因此滿足分治法的第四個適用