遞歸與分治策略

• 【Master定理】
• 快速排序
• • 優化
• 逆序對(歸并算法)
• • 火柴排隊[NOIP2013 提高組]
• 集合求和
• • 方法一: 遞歸 (2^n )
  • 方法二: 組合數學知識
• [HNOI2008]越獄(快速冪分治)
• 平面上的最接近點對
• 棋盤覆蓋(地毯填補問題)

【Master定理】

主定理【Master定理】提供了分治方法帶來的遞歸表達式的漸進復雜度分析。
將規模為 n 的問題通過分治，得到 a 個規模為 n/b 的問題，每次遞歸帶來的額外計算為 $c(n^d)$
即 $T(n)=a(n/b)+c(nd)$

• 若 $a=bd,T(n)=O(ndlog(n))$
• 若 $a<bd,T(n)=O(nd)$
• 若$a>bd,T(n)=O(nlogb(a))$

快速排序

快速排序算法是基于分治策略的另一個排序算法。其基本思想是，對于輸入的子數組a【p:r】，按以下三個步驟進行排序。
①分解(Divide) :以a【p】為基準元素將a【p : 】劃分成3段a 【p : q-1) ,a 【g】和a【g+1 :r】，使ap : q-1】中任何一個元素小于等于a 【g】，而a【q+1:】中任何一個元素大于等于a【g】 】。下標q在劃分過程中確定。
②遞歸求解(Conquer):通過遞歸調用快速排序算法，分別對a 【p : q-1】和a【g+1:】進行排序。
③合并(Merge):由于對a 【p: q-1】和a【g+1 : r】的排序是就地進行的，因此在a【p: g-1】和a 【g+1 :r】都已排好的序后，不需要執行任何計算，a【p: r】則已排好序。
基于這個思想，可實現快速排序算法如下:

根據基本思路，得到以下代碼:

對應的題目【模板】快速排序

代碼:

#include<iostream> #include<algorithm> using namespace std;const int N = 1E5 + 10;int n , a[N];int Partition(int a[] , int p ,int r){int i = p , j = r + 1 ;int x = a[p];while(true){while(a[++i] < x && i < r ); // 我們向右拓展，直到找到一個比 x 大或者等于的while(a[--j] > x ); // 我們向左延伸，直到遇到一個 <= x 的數if(i >= j)break; // 因為有不等式 a[i] >= x >= a[j] ，也就是最終i應該在x 右邊，j在其左邊swap(a[i],a[j]); // 但 j 如果在右邊，i在左邊，則交換}a[p] = a[j] , a[j] = x; // j為劃分點return j; }void qsort(int a[] , int p , int r){if(p < r){int q = Partition(a , p ,r); // 分解，分為以 a[q]為界限分為三段qsort(a , p ,q - 1); // 對左半段排序qsort(a , q + 1 ,r); // 對右半段排序} }int main(){cin>>n;for(int i = 1 ; i <= n ; ++i)cin>>a[i];qsort(a , 1 , n);for(int i = 1 ; i <= n ; ++i)cout<<a[i]<<" ";return 0; }

快速排序的運行時間與劃分是否對稱有關，其最壞情況發生在劃分過程產生的兩個區域分別包含n-1個元素和1個元素的時候。由于函數Partition)的計算時間為O(n)，所以如果算法Partition的每步都出現這種不對稱劃分，則其計算時間復雜性T(n)滿足
$$T（n）=\{\begin{array}{ll}O(1)& n<=1\\ T(n?1)O(n)& x>1\end{array}$$

我們可以通過遞歸子樹來求解。如下圖

這很明顯是一個等差數列，我們利用求和公式很容易解出，此遞歸方程，可得 $T(n)=O(n^2)$。
在最好情況下，每次劃分所取的基準都恰好為中值，即每次劃分都產生兩個大小為n/2的區域，此時，Partition算法的計算時間T(n)滿足
$$T（n）=\{\begin{array}{ll}O(1)& n<=1\\ 2T(n/2)+O(n)& x>1\end{array}$$
由Master定理其解為T(n)=O(nlogn)。

優化

容易看到，快速排序算法的性能取決于劃分的對稱性。通過修改函數Partition()，可以設計出采用隨機選擇策略的快速排序算法。在快速排序算法的每步中，當數組還沒有被劃分時，可以在alp:r]中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的,從而可以期望劃分是較對稱的。隨機化的劃分算法可實現如下:

// 在[p,r]中隨機選一個作為劃分點，而不總是以最左邊的作為 int Randomize(int a[] ,int p ,int r){srand((unsigned)time(NULL)); //這里利用時間進行播種，需要time.hint i = rand()%(r - p + 1) + p;swap(a[i],a[p]);return Partition(a,p,r); }

代碼:

#include<iostream> #include<algorithm> #include<cstdlib> #include<time.h> using namespace std;const int N = 1E5 + 10;int n , a[N];int Partition(int a[] , int p ,int r){int i = p , j = r + 1 ;int x = a[p];while(true){while(a[++i] < x && i < r );while(a[--j] > x );if(i >= j)break;swap(a[i],a[j]);}a[p] = a[j] , a[j] = x;return j; } // 在[p,r]中隨機選一個作為劃分點，而不總是以最左邊的作為 int Randomize(int a[] ,int p ,int r){srand((unsigned)time(NULL)); //這里利用時間進行播種，需要time.hint i = rand()%(r - p + 1) + p;swap(a[i],a[p]);return Partition(a,p,r); }void qsort(int a[] , int p , int r){if(p < r){int q = Randomize(a , p ,r);qsort(a , p ,q - 1);qsort(a , q + 1 ,r);} }int main(){cin>>n;for(int i = 1 ; i <= n ; ++i)scanf("%d",&a[i]);qsort(a , 1 , n);for(int i = 1 ; i <= n ; ++i)cout<<a[i]<<" ";return 0; }

結果
快了很多，上面代碼還需要吸氧才能過

逆序對(歸并算法)

合并排序算法是用分治策略實現對n個元素進行排序的算法，其基本思想是:將待排序元素分成大小大致相同的兩個子集合，分別對兩個子集合進行排序，最終將排好序的子集合合并成要求的排好序的集合。
由于我們在和并的時候，左右兩邊的集合都是排好序的，那么如果后一個集合中有一個元素小于前一個集合，那么就存在從前一個集合到其末尾的元素個數的逆序對個數，因此在當前元素后邊的值都大于等于該元素，那么當前元素比后面集合中的元素大，那么其后邊的元素也一定會比它大。

相關題目：逆序對

代碼:

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 5e5 + 10;int n ,a[N],c[N]; long long cnt;void mgsort(int a[],int p ,int r){if(p >= r)return ;int mid = (p + r)>>1;mgsort(a , p , mid);mgsort(a , mid + 1 ,r);int k = p , i = p , j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j]) c[k++] = a[i++];else c[k++] = a[j++] , cnt += mid - i + 1;}while(i <= mid)c[k++] = a[i++];while(j <= r)c[k++] = a[j++] , cnt += mid - i + 1;for( i = p ; i <= r ; ++i)a[i] = c[i]; }int main(){scanf("%d",&n);for(int i = 1 ; i <= n ; ++i)scanf("%d",&a[i]);mgsort(a,1,n);cout<<cnt<<endl;return 0; }

火柴排隊[NOIP2013 提高組]

題目鏈接: 火柴排隊

解題思路:
首先要想按什么排法，才能使得距離(題目定義的)的最小呢？當時我想到的是用貪心來證明兩個序列相對位置相同的在一行能使得距離最小。貪心證明如下

可能證明得不是很嚴謹，這里附上較嚴謹的證明

題目的意思：min{∑（ai-bi）^2 (1<=i<=n)}
展開：min{∑（ai^2+bi2-2aibi）}=min{∑ai^2+∑bi2-∑2aibi}
仔細觀察，可以發現∑ai^2和∑bi2的值是不會變的，所以只能在∑2aibi上做文章。
為使得和最小，那么∑2aibi要最大，本題的模型就轉變為max{∑ai*bi}。

轉化為證明：順序之乘>=亂序之乘

設有序數列k1_kn,p1pn，取k1<k2、p1<p2
因此容易得到：k1p1+k2p2>k1p2+k2p1;
將上述不等式變形一下：
k2p2-k2p1>k1p2-k1p1 即k2(p2-p1)>k1(p2-p1)
∵k2>k1,p2>p1 ∴k2(p2-p1)>k1(p2-p1)
證畢；
推廣2中的結論到1中，亂序就是不斷將順序交換打亂的過程，最終結果符合2的結論，因此 順序之乘>=亂序之乘，證畢。

實現方法

首先，我們先求出去，序列中數字應該所在的位置，而現在所處在的位置的序列，這里應該在的位置我們可以用一個數組的下標表示，當前所處的置，我們可以讓這個數組剛開始的值是每一個值所在的標號，然后排序，排序代碼如下，

bool cmp1(int x , int y){ return a[x] < a[y];}

之后，我們令 q[a[i]] = b[i]，相當于以 a[i]為關鍵字對序列 b[i] 排序。
若序列 a 與序列 b 相等，那么此時 q[a[i]]應該等于 a[i] 的，也就是 q[i] = i。
那么也就是說如果我們想讓序列 a 與序列 b 相等，那么我們需要讓 q 升序排列。
問題就變為，將原本亂的 q 序列升序排列的最少交換次數。那么我們需要對這個數組求逆序對即可。

代碼:

#include<iostream> #include<algorithm> using namespace std; const int N = 1e5 + 10 , mod = 99999997; int n ; int a[N],b[N],c[N],d[N]; int q[N],cnt , t[N];bool cmp1(int x , int y){ return a[x] < a[y];} bool cmp2(int x, int y){ return b[x] < b[y] ; }void mgsort(int a[] , int p , int r){if(p >= r)return ;int mid = (p + r) >>1;mgsort(a , p , mid) , mgsort(a , mid + 1 ,r);int i = p , k = p , j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j])t[k++] = a[i++];else t[k++] = a[j++] , cnt =( cnt + mid - i + 1) % mod;}while(i <= mid) t[k++] = a[i++];while(j <= r) t[k++] = a[j++] , cnt =( cnt + mid - i + 1) % mod;for(i = p ; i <= r ; ++i)a[i] = t[i]; }int main(){cin>>n;for(int i = 1 ; i <= n ; ++i)scanf("%d",&a[i]) , c[i] = i;for(int j = 1 ; j <= n ; ++j)scanf("%d",&b[j]) , d[j] = j;sort(c + 1 , c + 1 + n , cmp1) ,sort(d + 1 , d + 1 + n , cmp2);for(int i = 1; i <= n ; ++i)q[c[i]] = d[i];mgsort(q , 1 , n);cout<<cnt % mod<<endl;return 0; }

集合求和

題目鏈接:集合求和

方法一: 遞歸 (2^n )

對于一個數我們有選和不選兩種情況，因此我們在dfs的時候分兩種情況。不過這個題目的n = 30 ，很明顯會超時。

代碼:

#include<iostream> #include<cmath> using namespace std;typedef long long LL; const int N = 31; LL sum ; int a[N] , n;void dfs(LL s , int u){if(u == n){sum += s;return ;}dfs(s + a[u] , u + 1);dfs(s , u + 1); }int main(){while(cin>>a[n++]);n--;dfs(0,0);cout<<sum<<endl;return 0; }

方法二: 組合數學知識

由于是求出子集的和，我們不一定要枚舉所有子集的情況。我們只需要知道，一個數出現在子集中的次數即可。那么對于集合中的一個數，它出現在不同子集中的次數是多少次呢？ 那么如果我們選了當前數 ， 那么能出現這個數的子集個數，是由剩余的n-1個數來決定的，那么對于其余的n-1的數，每一個都有選與不選兩種可能，所以一共有 $2^{n?1}$中。也就是一個數會出現$2^{n?1}$ 。因此子集和就是：
$$\sum _{i=1}^n{2}^{n?1}?a[i]$$

代碼:

#include<iostream> #include<cmath> using namespace std;typedef long long LL; const int N = 31; LL sum ; int a[N] , n;void dfs(LL s , int u){if(u == n){sum += s;return ;}dfs(s + a[u] , u + 1);dfs(s , u + 1); }int main(){while(cin>>a[n++]);n--;for(int i = 0 ; i < n ; ++i) sum += a[i] * (LL)pow(2,n-1);cout<<sum<<endl;return 0; }

[HNOI2008]越獄(快速冪分治)

題目鏈接:越獄

解題思路
這其實思路來自于組合數學，我們正難則反，我們知道，m個信仰，n個房間，那么總的方案數有$m^n$中，那么不會出現越獄的情況是有多少種呢？對于第一個監獄我們有m中選擇，那么第二個為了不沖突只有m-1中選擇，那么第三個呢？m-2？ 不是的也是m-1種，因為第一個房間的選擇它也可以選擇，只是不能選與第二個房間相同的，類比，我們發現，從第二個房間開始后邊的房間都有 m - 1 種選擇，那么我們答案就是
$$ans=m^n?m?(m?1{)}^{n?1}$$ ，其中m 可以提出來，就是$$ans=m?（m^n?(m?1{)}^{n?1}）$$

這里可能屬于分治類的可能是我們求解這個答案的時候用到了快速冪吧，

ps ： 注意輸入會爆int ，同時相減的時候可能會變成負數，因此我們相減的時候 再 + mod 再取模
代碼

#include<iostream> using namespace std; const int mod = 100003; typedef long long LL;LL n , m, ans ;LL qmi(LL a , LL b){LL ans = 1;for( ; b ; b >>= 1){if(b & 1)ans = (ans * a) % mod;a = a * a % mod;}return ans % mod; }int main(){cin>>m>>n;LL a = qmi(m , n - 1) ;LL b = qmi(m - 1 , n - 1);ans = (a - b + mod) % mod;cout<<(ans * m) % mod <<endl;return 0; }

平面上的最接近點對

題目鏈接:題目鏈接

這個博客講的好，下面將其代碼進行了一些優化。
題解

代碼

#include<iostream> #include<algorithm> #include<cmath> using namespace std; #define x first #define y second const int N = 1e4 + 10;typedef pair<double,double>PDD;PDD p[N],t[N]; int n ;double distance(PDD a , PDD b){double x = a.x - b.x , y = a.y - b.y;return sqrt(x * x + y * y); }double merge(int left , int right){double dis = 1e18; // 左，右兩邊點對之間的最小值if(left == right)return dis;// 只有兩個點，返回就兩個點之間的距離就可以了if(left + 1 == right)return distance(p[left] , p[right]);int mid = (left + right) >> 1;dis = min(dis , merge(left , mid));dis = min(dis , merge(mid + 1 ,right));int k = 0;// 將 這個區間 T 中距離小于 dis 的點加入// 這些點有可能是比 dis 小的點for(int i = left ; i <= right ; ++i)if(fabs(p[i].x - p[mid].x) <= dis)t[k++] = p[i];// 枚舉選出集合點之間的距離，第層循環由性質會減少很多，// 不會超過6 個for(int i = 0 ; i < k - 1 ; ++i)for(int j = i + 1 ; j < k && t[j].y - t[i].y < dis; ++j)dis = min(dis , distance(t[i],t[j]));return dis; }int main(){cin>>n;for(int i = 0 ; i < n ; ++i)cin>>p[i].x>>p[i].y;sort(p , p + n);printf("%.4lf\n",merge(0 , n - 1));return 0; }

棋盤覆蓋(地毯填補問題)

相關題目鏈接：地毯填補問題

解題思路
相信來看這篇博客的都知道這個題目為什么能用分治法做吧，因此就不說明了。首先理解題意，題目所說的拐角是什么意思？如圖

那么我們什么依據思路來解決這個問題呢？回顧課本中所說的解法，是分為四個部分后，對著四個部分進行分情況討論。我們就以左上角為例，如果特殊方格出現在這里，由上面拐角的定義，這個時候我們就要輸出如圖拐角的坐標 ， 同時這里題目給我們L型方塊的標號很有意思，左上角是 1 ，右上角是2 ，左下角是3 ，右下角是4 。之后遞歸處理，那么如果不在什么辦呢？那么我們就會有一個L型方塊來使得這個區域存在特除方格，但是我們不用確定方塊用了哪一個，但是我們知道，一定有一個特殊方格存在如圖所在位置，因此我們遞歸的參數也要改變

為什么是這樣判斷特殊方格在那一個部分的？
首先我們明確我們的圖是一個一個點構成的不會有一個明顯的中點，如一個4 * 4 的矩陣就會是

相信畫到這里聰明的你一定能知道了吧

參數意義：

• tr:棋盤左上角方格的行號;
• dc:特殊方格所在的列號;
• tc:棋盤左上角方格的列號;
• s: $s=2^k$，棋盤規格為$2^k\times 2^k$;
• dr:特殊方格所在的行號。

代碼：

#include<iostream> #include<cmath> #include<cstring> using namespace std; int k; int dr,dc;void show(int x ,int y , int k){printf("%d %d %d\n",x ,y , k); }void dfs(int tr , int tc , int dr ,int dc ,int s){if(s == 1)return ;s >>= 1;int mr = tr + s , mc = tc + s;// 左上角if(dc < mc && dr < mr){show(mr ,mc ,1 );//printf("%d %d 1\n",tr + s - 1 , tc + s - 1);dfs(tr , tc , dr,dc , s);}elsedfs(tr,tc, mr - 1, mc - 1, s);// 右上角if(dr < mr && dc >= mc ){show(mr ,mc - 1 ,2);// printf("%d %d 2\n",tr + s - 1 , tc + s );dfs(tr , tc + s , dr,dc , s);}elsedfs(tr , tc + s , mr - 1 , mc ,s);// 左下角if(dr >= mr && dc < mc){show(mr - 1 ,mc ,3 );//printf("%d %d 3\n",tr + s , tc + s - 1);dfs(tr + s , tc , dr , dc , s);}elsedfs(tr + s , tc , mr ,mc - 1 , s);// 右下角if(dr >= mr &&dc >= mc){show(mr - 1 ,mc - 1 ,4 );// printf("%d %d 4\n",mr , mc );dfs(mr , mc , dr , dc , s);}elsedfs(tr + s , tc + s ,mr ,mc ,s); }int main(){cin>>k>>dr>>dc;dfs(1 , 1 ,dr,dc,1 << k );return 0; }

總結

以上是生活随笔為你收集整理的计算机算法设计与分析之----- 递归与分治策略的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。