C++递归与分治算法原理示例详解

1. 汉诺塔问题

递归算法，分为 3 步：将 n 个 a 上的盘子借助 c 移动到 b

① 将 n-1 个 a 上的盘子借助 b 移动到 c

② 将 a 上的盘子移动到 b

③ 将 c 上的 n-1 个盘子借助 a 移动到 b

所有盘子都移动到 b 上了

void hanoi(int n,char a,char b,char c)//将n个碟子从a借助c 移到b
 { 
    if(n==0) 
    return; 
    else 
     { 
        hanoi(n-1,a,c,b); 
        move(a,b); 
        hanoi(n-1,c,b,a);
     ｝
｝

2. 全排列问题

问题描述：设R={r1,r2,…,rn}是要进行排列的n个元素，求R的全排列Perm(R)。

算法思路：

① 从 n 个数中取出数列的第一个数，然后不断将数列中剩余的数与第一个数进行交换，计算剩余 n-1 个数的全排列。

② 对 n - 1 个数进行同样的递归操作，当交换的第一个数的下标 k 和序列末尾的 m 相同时，说明前置所有数都已经交换完成，进行输出。

③ 递归结束后进行状态回调，保证不影响下一次递归的进行。

void Perm(int list[], int k, int m)
{
    if(k==m)
    {
        for(int i=0;i<m;i++）
        {
            cout<<list[i];
        }
        cout<<endl;
        return;
    }
    for(int i=k;i<m;i++)
    {
        swap(list[k], list[i])
        Perm(list, k+1, m)
        swap(list[k], list[i])
    }
}

3. 利用递归与分治策略寻找最大值

#include <bits/stdc++.h>
using namespace std; 
int find_max(int a[], int from, int to){ 
    if(from>=to) return a[from]; 
    int mid = (from + to)/2;
    int v1 = find_max(a, from, mid);
    int v2 = find_max(a, mid+1, to);
    if(v1<=v2) return v2;
    else return v1;
} 
int main()
{
    int n, a[100000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<find_max(a, 0, n-1);
}

4. 归并排序

#include <bits/stdc++.h> 
using namespace std;  
void merge_array(int a[], int from, int mid, int to){
 
    int tmp[100000], idx_tmp=0;
    int i,j;
    for(i=from, j=mid+1; i<=mid && j<=to;){
 
        if(a[i]<=a[j]) tmp[idx_tmp++] = a[i++];
        else tmp[idx_tmp++] = a[j++]; 
    }
    while(i<=mid) tmp[idx_tmp++]=a[i++];
    while(j<=to) tmp[idx_tmp++]=a[j++];
    for(int i=from,j=0; i<=to;i++) a[i] = tmp[j++]; 
}
 
void merge_sort(int a[], int from, int to){ 
    if(from < to){
        int mid = (from + to)/2;
        merge_sort(a, from, mid);
        merge_sort(a, mid+1, to);
        merge_array(a, from, mid, to);
    }
} 
int main()
{
    int n, a[100000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    merge_sort(a, 0, n-1);
    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }
}

5. 快速排序

图解快速排序：//www.jb51.net/article/113769.htm

递归 + 交换法

#include <bits/stdc++.h> 
using namespace std; 
int sort_array(int a[], int from, int to)
{
    int base = a[from];
    int i,j;
    for(i=from, j=to; i<j;)
    {
        while(a[j]>=base && i<j) j--;
        while(a[i]<=base && i<j) i++;
        //function swap()
        if(i<j){
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[from]=a[i];
    a[i]=base;
    return i;
} 
void quick_sort(int a[], int from, int to)
{
    if(from>=to) return;
    int i = sort_array(a, from, to);
    quick_sort(a, from, i-1);
    quick_sort(a, i+1, to);
}
 
int main()
{
    int n, a[100000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(a, 0, n-1);
    for(int i=0;i<n;i++){
        printf("%d ", a[i]);
    }
}

6. 棋盘覆盖问题

#include <bits/stdc++.h> 
using namespace std; 
int num=0;
int a[1000][1000]; 
void make_chess(int px, int py, int tx, int ty, int sze){ 
    if(sze==1) return;
    num++;
    sze/=2;
 
    //左上
    if(px<tx+sze && py<ty+sze)
    {
        a[tx+sze-1][ty+sze]=num;
        a[tx+sze][ty+sze-1]=num;
        a[tx+sze][ty+sze]=num;
    }
 
    //右上
    if(px<tx+sze && py>=ty+sze)
    {
        a[tx+sze-1][ty+sze-1]=num;
        a[tx+sze][ty+sze-1]=num;
        a[tx+sze][ty+sze]=num;
    }
 
    //左下
    if(px>=tx+sze && py<ty+sze)
    {
        a[tx+sze-1][ty+sze-1]=num;
        a[tx+sze-1][ty+sze]=num;
        a[tx+sze][ty+sze]=num;
    }
    //右下
    if(px>=tx+sze && py>=ty+sze)
    {
        a[tx+sze-1][ty+sze-1]=num;
        a[tx+sze-1][ty+sze]=num;
        a[tx+sze][ty+sze-1]=num;
    }
 
    //左上
    if(px<tx+sze && py<ty+sze) make_chess(px, py, tx, ty, sze);
    else make_chess(tx+sze-1, ty+sze-1, tx, ty, sze);
 
    //右上
    if(px<tx+sze && py>=ty+sze) make_chess(px, py, tx, ty+sze,sze);
    else make_chess(tx+sze-1, ty+sze, tx, ty+sze,sze);
 
    //左下
    if(px>=tx+sze && py<ty+sze) make_chess(px, py, tx+sze, ty,sze);
    else make_chess(tx+sze, ty+sze-1, tx+sze, ty, sze);
 
    //右下
    if(px>=tx+sze && py>=ty+sze) make_chess(px, py, tx+sze, ty+sze, sze);
    else make_chess(tx+sze, ty+sze, tx+sze, ty+sze, sze); 
}
 
int main()
{
    int k, px, py;
    int tx=0, ty=0;
    cin>>k>>px>>py;
    make_chess(px-1, py-1, tx, ty, k);
 
    for(int i=0; i<k; i++){
        for(int j=0; j<k; j++){
            printf("%2d ", a[i][j]);
        }
        cout<<endl;
    } 
}

频道导航