遞回與分治策略
遞回與分治策略是五大常見演算法策略之一，分治策略的思想就是分而治之，即先將一個規模較大的大問題分解成若干個規模較小的小問題，再對這些小問題進行解決，得到的解，在將其組合起來得到最終的解，而分治與遞回很多情況下都是一起結合使用的，能發揮出奇效（1+1>2），這篇文章我們將先從遞回說起，再逐漸向分治過渡，主要講解方式是通過9個例題來說明問題的，問題都是根據難度由簡到難，由淺入深，對遞回與分治能有個大概的了解雛形，當然最重要還是要做大量練習才能掌握，
0、遞回
??0.0、Fibonacci數列(易)
??0.1、階乘(易)
??0.2、小青蛙跳臺階(易)
??0.3、全排列問題(偏難)
??0.4、整數劃分(偏難)
1、分治策略
??1.0、歸并排序(一般)
??1.1、二分查找(易)
??1.2、棋盤覆寫(偏難)
??1.3、日程表問題(偏難)
遞回
我們第一次接觸遞回一般都是在初學C語言時候的一道題目——Fibonacci數列中看到的，可能剛開始感覺有點不可思議，函式居然可以呼叫自己！Amazing！但事實如此，它確實存在，而遞回也為我們某些演算法的設計提供很大的便利，一般來說遞回函式在理解起來并不是很難，甚至可以通過數學歸納法給予證明，但一直讓人詬病的一點莫過于Debug的時候了，有時候除錯一個較為復雜的遞回函式能把人逼瘋，
我們在這里將會由易到難，用一些例題先來講解遞回函式，采用Fibonacci數列來做這個引例來介紹遞回函式，
Fibonacci
??第一個數是1，第二個數也是1，從第三個數開始，后面每個數都等于前兩個數之和，要求：輸入一個n，輸出第n個斐波那契數，
我們先來整理一下思路，分下面三步來看：
- 1、明確函式的輸入和輸出(即函式的作用)
- 2、明確遞回終止條件
- 3、尋找函式的遞回關系式
第一步，函式輸入n，輸出(也就是回傳)第n個斐波那契數：
public static int fibonacci(int n){
}
第二步，明確遞回終止條件：
public static int fibonacci(int n){
if(n == 1) return 1;
else if (n == 2) return 1;
}
第三步，尋找函式的遞回關系：
public static int fibonacci(int n){
if(n == 1) return 1;
else if(n == 2) return 1;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
就這樣，我們的一個斐波那契數列的遞回函式就寫完了，當然，這只是我們的一個開胃小菜，下面繼續是入門級別的一個題，算階乘，
階乘
輸入一個數，輸出它的階乘，我們同樣用那三步往下走，
第一步，函式輸入n，回傳n的階乘
public static int factorial(int n){
}
第二步，明確遞回終止條件：
public static int factorial(int n){ //0的階乘等于1
if(n == 0) return 1;
}
第三步，尋找函式的遞回關系
public static int factorial(int n){ //0的階乘等于1
if(n == 0) return 1;
else return factorial(n - 1) * n;
}
做完前兩個你肯定會覺得這不是很簡單嗎，不要急，我們要由易到難，由淺入深，這樣階梯式的科學學習，下面這個例子是小青蛙跳臺階問題，這個問題被用于遞回和動態規劃類問題的例題，我們這里先用遞回解答，后面還會用動態規劃策略來解決這個問題，
小青蛙跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階共有多少種跳法，
還是三步走，第一步，明確函式的輸入及回傳
public static int Jump_Floor1(int n){
}
第二步，明確遞回終止條件
如果n=1，那小青蛙只能一次跳上第一節臺階，所以一種跳法，如果n=2，那小青蛙可以一次跳一節跳兩次，或者直接一次跳兩節，所以兩種跳法，
public static int Jump_Floor1(int n){
if(n <= 2){
return n;
}
}
第三步，尋找函式的遞回條件
這里可不能簡單的return Jump_Floor1(n-1)就完事兒了，分了兩種情況：1、第一次跳1級就還有n-1級要跳，2、第一次跳2級就還有n-2級要跳
public static int Jump_Floor1(int n){
if(n <= 2){
return n;
}else{ //這里涉及到兩種跳法，1、第一次跳1級就還有n-1級要跳，2、第一次跳2級就還有n-2級要跳
return Jump_Floor1(n-1)+Jump_Floor1(n-2);
}
}
下面這個例題是排列問題，就是求出一組數的全排列，
全排列問題
我們在全排列問題種需要用到一個交換函式swap用于交換兩個數的位置，作如下定義：k陣列種元素為待排列元素，k和m為待交換兩元素的下標
private static void swap(int a[], int k, int m){ //交換k和m下標的元素的值
int temp = a[k];
a[k] = a[m];
a[m] = temp;
}
接下來繼續回到遞回函式
第一步，明確函式的輸入以及回傳，這里我們需要輸入待排列元素組成的陣列，陣列的第一個元素的下標，以及最后一個元素的下標
public static void perm(int a[], int k, int m){
}
第二步，明確遞回終止條件,就是當只剩下一個元素時
public static void perm(int a[], int k, int m){
if(k == m) { //只有一個元素
for (int i = 0; i <= m; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
}
第三步，尋找遞回條件
public static void perm(int a[], int k, int m){
if(k == m) { //只有一個元素
for (int i = 0; i <= m; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}else{ //還有多個元素，遞回產生排列
for (int i = k; i <= m; i++) {
swap(a,k,i); //排列到這個元素就要將其放在第一個位置
perm(a,k+1,m);
swap(a,k,i); //從此出口出去后還需要將剛剛調換的位置換回來
}
}
}
下面是遞回這塊的最后一個例題了，整數劃分問題，
整數劃分
說明一下問題，什么是整數劃分？
- n=m1+m2+...+mi; （其中mi為正整數，并且1 <= mi <= n），則{m1,m2,...,mi}為n的一個劃分，
- 如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬于n的一個m劃分，這里我們記n的m劃分的個數為f(n,m);
- 舉個例子，當n=5時我們可以獲得以下這幾種劃分（注意，例子中m>=5）
5 = 5
= 4 + 1
= 3 + 2
= 3 + 1 + 1
= 2 + 2 + 1
= 2 + 1 + 1 + 1
= 1 + 1 + 1 + 1 + 1
撰寫程式，輸入整數n,m，回傳n的所有m的劃分個數，
演算法思路：我們用q(n,m)表示將n用不大于m的數字劃分的方法的個數
- 1、n = 1時：只有一種劃分法就是1
- 2、m = 1時：也只有一種劃分法就是n個1相加
- 3、n < m時: 劃分的方法也就只限于q(n,n)了，畢竟比n大的數也取不到嘛（不能取負數，要不然無限多了）
- 4、n = m時：就是1+(m-1)這一種情況加q(n,m-1)即1+q(n,m-1)，比如q(6,6)就是1+q(6,5)
- 5、n > m時：這種情況下又包含兩種情況：
??5(1)、劃分中包含m時：即{m, {x1,x2,...xi}}(它們之和為n), 其中{x1,x2,... xi} 的和為n-m，所以就是n-m的m劃分，即q(n-m,m)
??5(2)、劃分中不包含m時:劃分中所有的值都比m小，即q(n,m-1) - 因此第5中情況的劃分為q(n-m,m)+1(n,m-1)
- 對第2中舉例子詳述：q(5,3):
??(1)包含3: 1+1+3; 2+3; 既然每種情況都包含了3，那去掉3對其余各數相加為(5-3=)2的劃分的個數和其相等，那就是對2(m=3)的劃分了
??(2)不包含3： 1+1+1+1+1; 1+1+1+2; 1+2+2;
第一步，明確函式輸入和回傳
public static int equationCount(int n, int m){
}
第二步，明確遞回終止條件
public static int equationCount(int n, int m){
if (n < 1 || m < 1)
return 0;
if(n == 1 || m == 1)
return 1;
}
第三步，尋找遞回關系
public static int equationCount(int n, int m){
if (n < 1 || m < 1)
return 0;
if(n == 1 || m == 1)
return 1;
if(n < m)
return equationCount(n,n);
if(n == m)
return equationCount(n,m-1)+1;
return equationCount(n-m,m)+equationCount(n,m-1); //n > m的情況
}
分治策略
分治策略的基本思想就是將一個規模為n的問題分解成k個規模較小的子問題，這些子問題互相獨立且與原問題相同，遞回的解這些子問題，然后將子問題的解合并得到原問題的解，和這種說法最貼切的就是我們之前一篇文章介紹的歸并排序法了，這篇文章里我們還會再引出一遍，
我們將分治策略解決問題的步驟歸納為：將大問題分解成子問題，分別解決子問題，再將子問題的解合并成大問題的解.
先看第一個典型的例子——歸并排序
歸并排序
這里我們對歸并排序主要注重體現它分治策略的演算法邏輯，而不過多深究這個排序演算法是如何執行的，具體的圖解歸并排序請移步我的另一篇博文——資料結構之——八大排序演算法，
歸并排序的思想是，先將陣列分割成為一個個小陣列，直到每個小陣列中只含有一個元素，那么在這一個小陣列里面，這一個元素自然就是有序的，然后將其合并起來(由merge函式實作)，按從小到大的順序，逐層向上，就是將小問題的解合并為大問題的解，
下面是將大問題分解成小問題的程序
/**
* 只要陣列的大小不為1，就一直分割，直到不能分割為止（即陣列長度為1），
* 不能分割后按照出入堆疊順序，會將分割的小陣列分別排序后歸并起來
* @param data 待排序陣列
* @param start 起始位置
* @param end 終止位置
*/
public static void merge_sort(int data[], int start, int end){
int mid = (start+end)/2;
if(start < end){
merge_sort(data,start,mid);
merge_sort(data,mid+1,end);
merge(data,start,mid,end);
}
}
下面是合并小問題的解，歸并程序
/**
* 這個函式是將陣列合并在一起的，其實并沒有將陣列真的分開，只是用start和end指示不同的元素，來達到分割的目的
* @param p 指示子陣列1的元素
* @param q 指示子陣列2的元素
* @param r 指示合并后陣列的元素
* @param start start到mid是需要合并的子陣列1
* @param mid
* @param end mid+1到end是需要合并的子陣列2
*/
private static void merge(int data[], int start, int mid, int end){
int p = start, q = mid+1, r = 0;
int newdata[] = new int[end-start+1];
while(p <= mid && q <= end){
if(data[p] >= data[q]){ //從大到小排序
newdata[r++] = data[p++];
}else{
newdata[r++] = data[q++];
}
}
//此時，兩個子陣列中會有一個中元素還未被全部歸并到新陣列中，作如下處理
while(p <= mid){
newdata[r++] = data[p++];
}
while(q <= end){
newdata[r++] = data[q++];
}
//再將有序的陣列中的值賦給原陣列，其實也可以直接回傳這個新陣列
for (int i = start; i <= end; i++) {
data[i] = newdata[i-start];
}
}
二分查找
然后是分治策略的另一個經典例子———二分查找，顧名思義，就是在一個有序（從小到大）的陣列中查找一個元素的位置，先從最中間將陣列變為兩個小陣列，然后與中間值進行對比，如果相等直接回傳，不相等又分兩種情況，如果中間元素比待查找值小，就從后半個陣列中繼續二分查找，反之，從前半個陣列中二分查找，
public static int Binary_Search(int []data, int x, int n){ //data為待搜索陣列(有序)，x為待搜索元素，n為陣列大小
int left = 0, right = n - 1; //指示左右的兩個指示器
while(left <= right){ //left可以等于right，因為有可能剛好兩個指示器同時指示到了待查找元素上
int mid = (left+right)/2;
if(data[mid] > x)
right = mid-1;
else if(data[mid] < x)
left = mid+1;
else return mid;
}
return -1; //表示查找失敗
}
棋盤覆寫
下面我們逐漸加大難度，接下來這個問題叫做棋盤覆寫，我們先簡單介紹一下這個問題，
在一個2^k × 2^k （k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格，顯然，特殊方格在棋盤中可能出現的位置有4k種，因而有4k種不同的棋盤，圖4.10(a)所示是k=3時64種棋盤中的一個，棋盤覆寫問題（chess cover problem）要求用圖4.10(b)所示的4種不同形狀的L型骨牌覆寫給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆寫，
圖4.10(a)
圖4.10(b)
在這里為了方便講解，我們采用k=2時候的情況來說明這個問題，設初始情況為
第一次將其分割成四個小塊，分成了四個子棋盤，以黃線為分割線
然后分別對其進行填充
填充完后，又可以將其分割
重復上述填充操作，即可對所有方格填充
當k更大的時候的程序可以參考這位大佬的博客棋盤覆寫問題，接下來我們用代碼實作，
static int board[][] = new int[4][4]; //棋盤
static int tag = 1; //骨牌編號
/**
* 分治演算法典例2———棋盤覆寫問題
* @date 2019/11/3 afternoon
* @param tr 棋盤左上角方格的行號
* @param tc 棋盤左上角方格的列號
* @param dr 特殊方格所在的行號
* @param dc 特殊方格所在的列號
* @param size 棋盤寬度
* @param s 當前棋盤寬度的一半
* @param tr+s 當前棋盤中間行的行號
* @param tc+s 當前棋盤中間列的列號
*/
public static void chess(int tr, int tc, int dr, int dc, int size){
if(size == 1)
return;
int newtag = tag++;
int s = size / 2; //分割棋盤
//覆寫左上角子棋盤
if(dr < tr+s && dc < tc+s){ //特殊方格在此棋盤中
chess(tr,tc,dr,dc,s);
}else{ //此棋盤中無特殊方格
board[tr+s-1][tc+s-1] = newtag;
chess(tr,tc,tr+s-1,tc+s-1,s);
}
//覆寫右上角子棋盤
if(dr < tr+s && dc >= tc+s){
chess(tr,tc+s,dr,dc,s);
}else{
board[tr+s-1][tc+s] = newtag;
chess(tr,tc+s,tr+s-1,tc+s,s);
}
//覆寫左下角子棋盤
if(dr >= tr+s && dc < tc+s){
chess(tr+s,tc,dr,dc,s);
}else{
board[tr+s][tc+s-1] = newtag;
chess(tr+s,tc,tr+s,tc+s-1,s);
}
//覆寫右下角子棋盤
if(dr >= tr+s && dc >= tc+s){
chess(tr+s,tc+s,dr,dc,s);
}else{
board[tr+s][tc+s] = newtag;
chess(tr+s,tc+s,tr+s,tc+s,s);
}
}
接下來的問題依然有一些難度，叫做列印日程表問題，
日程表問題
問題：設有n=2^k個選手參加回圈賽，要求設計一個滿足以下要求比賽日程表：
1）每個選手必須與其它n-1個選手各賽一次；
2）每個選手一天只能賽一次，
分析，按照上面的要求，可以將比賽表設計成一個n行n-1列的二維表，其中第i行第j列的元素表示和第i個選手在第j天比賽的選手號，
采用分治策略，可將所有參加比賽的選手分成兩部分，n=2^k 個選手的比賽日程表就可以通過n=2^（k-1） 個選手的的比賽日程表來決定，遞回的執行這樣的分割，直到只剩下兩個選手，比賽日程表的就可以通過這樣的分治策略逐步構建，
說個大白話就是：先默認構造日程表第一行，即0，1，2，3，...然后先分割日程表，將左上角復制到右下角，右上角復制到左下角
初始化第一行不做贅述，讓chess[0][i] = i+1即可
下面在Excel中用圖示做一演示
代碼實作
/**
* 將比賽日程表設計成n行n列，表中除了第一列，其他n-1列才是我們要的，陣列下標行列都從0開始，第i行j列代表第（i+1）位選手在第j天的對手：
* 表格初始化會將第一行按1到n一次填充，然后遞回填充下面的，用左上角和右上角分別去填充右下角和左下角，因為要是對稱矩陣（具體原因好好想想）
* @param p 表示行序號
* @param q 表示列序號
* @param t 表示當前傳進函式方格的規模也就是大小
* @param arr 表格
*/
public static void arrange(int p, int q, int t, int arr[][]){
if(t>=4){ //如果規模大于4，就繼續遞回
arrange(p,q,t/2,arr);
arrange(p,q+t/2,t/2,arr);
}
//填左下角
for(int i=p+t/2;i<p+t;i++){
for(int j=q;j<q+t/2;j++){
arr[i][j]=arr[i-t/2][j+t/2];
}
}
//填右下角
for(int i=p+t/2;i<p+t;i++){
for(int j=q+t/2;j<q+t;j++){
arr[i][j]=arr[i-t/2][j-t/2];
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/110909.html
標籤：其他
上一篇：《演算法筆記》之入門模擬
下一篇：紅黑樹——自平衡程序