C++遞歸與分治算法原理示例詳解

更新時(shí)間：2021年11月02日 08:54:13 作者：Gaoithe

這篇文章主要為大家介紹了C++遞歸與分治算法的策略原理示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

1. 漢諾塔問題

遞歸算法，分為 3 步：將 n 個(gè) a 上的盤子借助 c 移動(dòng)到 b

① 將 n-1 個(gè) a 上的盤子借助 b 移動(dòng)到 c

② 將 a 上的盤子移動(dòng)到 b

③ 將 c 上的 n-1 個(gè)盤子借助 a 移動(dòng)到 b

所有盤子都移動(dòng)到 b 上了

void hanoi(int n,char a,char b,char c)//將n個(gè)碟子從a借助c 移到b
 { 
    if(n==0) 
    return; 
    else 
     { 
        hanoi(n-1,a,c,b); 
        move(a,b); 
        hanoi(n-1,c,b,a);
     ｝
｝

2. 全排列問題

問題描述：設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，求R的全排列Perm(R)。

算法思路：

① 從 n 個(gè)數(shù)中取出數(shù)列的第一個(gè)數(shù)，然后不斷將數(shù)列中剩余的數(shù)與第一個(gè)數(shù)進(jìn)行交換，計(jì)算剩余 n-1 個(gè)數(shù)的全排列。

② 對(duì) n - 1 個(gè)數(shù)進(jìn)行同樣的遞歸操作，當(dāng)交換的第一個(gè)數(shù)的下標(biāo) k 和序列末尾的 m 相同時(shí)，說(shuō)明前置所有數(shù)都已經(jīng)交換完成，進(jìn)行輸出。

③ 遞歸結(jié)束后進(jìn)行狀態(tài)回調(diào)，保證不影響下一次遞歸的進(jìn)行。

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. 快速排序

圖解快速排序：//m.fzitv.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;
    } 
}

以上就是C++遞歸與分治算法原理示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C++遞歸與分治算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: