天天看點
傳回

算法設計與分析第2章 遞歸與分治政策第2章 遞歸與分治政策

第2章 遞歸與分治政策

2.1 遞歸算法

遞歸算法：直接或間接地調用自身的算法。

遞歸函數：用函數自身給出定義的函數。兩個要素：邊界條件、遞歸方程

優點：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正确性。

缺點：運作效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。

解決方法：在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。

1、采用一個使用者定義的棧來模拟系統的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，隻不過人工做了本來由編譯器做的事情，優化效果不明顯。

2、用遞推來實作遞歸函數。

3、通過變換能将一些遞歸轉化為尾遞歸，進而疊代求出結果。

後兩種方法在時空複雜度上均有較大改善，但其适用範圍有限。

例1.階乘函數

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long factorial(long long n)
{
    if(n==0) return 1;
    else return n*factorial(n-1);
}
int main()
{
    long long  n;
    long long result;
    cout<<"this app compute the factorial of n,please input n:"<<endl;
    while(cin>>n)
    {
        result=factorial(n);
        cout<<"The factorial of "<<n<<" is: "<<result<<endl;
    }
    return 0;
}

例2. Fibonacci數列

無窮數列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數列。它可以遞歸地定義為：

算法設計與分析第2章 遞歸與分治政策第2章 遞歸與分治政策

代碼：

#include<iostream>
#include<stdlib.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int Fibonacci(int n)
{
    if(n==0||n==1) return 1;
    else return Fibonacci(n-1)+Fibonacci(n-2);
}
int main()
{
    int n,result;
    cout<<"this app compute Fibonacci of n, please input n:"<<endl;
    while(cin>>n)
    {
        result=Fibonacci(n);
        cout<<"the Fibonacci of "<<n<<" is :"<<result<<endl;
    }
    return 0;
}

例3 .Ackerman函數

當一個函數及它的一個變量是由函數自身定義時，稱這個函數是雙遞歸函數。

Ackerman函數A(n，m)定義如下：

算法設計與分析第2章 遞歸與分治政策第2章 遞歸與分治政策

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int Ackerman(int n,int m)
{
    if(n==1&&m==0) return 2;
    else if(n==0&&m>=0) return 1;
    else if(n>=2&&m==0) return n+2;
    else if(n>=1&&m>=1) return Ackerman(Ackerman(n-1,m),m-1);
}
int main()
{
    int n,m,result;
    cout<<"this app compute the problem of Ackerman,please input n and m:"<<endl;
    while(cin>>n>>m)
    {
        result=Ackerman(n,m);
        cout<<"the result is :"<<result<<endl;
    }
    return 0;
}
例4.全排列問題：123 -> 123 132 213 231 312 321

分析：可以采取以下步驟：

（1）數組的第一個元素為1(排列的第一個元素為1),生成後面的n-1個排列;

數組的第一進制素與第二進制素互換,使得排列的第一個元素為2,生成後面的n-1個排列;

依次類推,最後數組第一進制素與數組第n元素互換,使排列第一進制素為n,生成後面的n-1個排列;

（2）上述第一步驟中,為生成後面的n-1個元素的排列,繼續采取以下步驟：

數組的第二個元素為2(排列的第二個元素為2),生成後面的n-2個排列;

數組的第二進制素與第三元素互換,使得排列的第一個元素為3,生成後面的n-2個排列;

依次類推,最後數組第二進制素與數組第n元素互換,使排列第二進制素為n,生成後面的n-2個排列;

（3）上述步驟持續進行,即當排列的前n-2個元素确定後,為生成後面的2個元素的排列,可按照前面類似方式進行：

數組的第n-1個元素為n-1(排列的第n-1個元素為n-1),生成後面的1個排列,此時數組中的n個元素已經構成了一個排列;

數組的第n-1元素與第n元素互換,使得排列的第n-1個元素為n,生成後面的1個元素的排列,此時數組中的n個元素已經構成了一個排列;

若排列算法pl_alm(A,k,n)表示生成數組後面的k個元素的排列,則通過上述分析,有：

基礎步：k=1，隻有一個元素，已經形成一個排列;

歸納步：對于任意一個k(k=2,3,…,n)，若可根據算法pl_alm(A,k-1,n)完成數組後面k-1個元素的排列，則為了完成數組後面k個元素的排列pl_alm(A,k,n)，應該逐一對數組中的第n-k元素與數組中的n-k~n元素進行互換，每互換一次，就執行一次pl_alm(A,k-1,n)操作，并進而産生一個排列。

算法的時間複雜度為： O(n*n!)

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
void pl_alm(int A[],int k,int n)
{
    int i;
    if(k==1)
    {
        for(i=0; i<n; i++)
        {
            cout<<A[i];
        }
        cout<<endl;
    }
    else
    {
        for(i=n-k; i<n; i++)  //循環将目前位置元素依次與其後元素互換
        {
            swap(A[n-k],A[i]);
            pl_alm(A,k-1,n);  //遞歸生成後面的k-1個元素的全排列
            swap(A[n-k],A[i]);
        }
    }
}
int main()
{
    int A[52];
    int i,n;
    cout<<"please input the elements sum of A(must less than 50): "<<endl;
    cin>>n;
    if(n>50)
    {
        cout<<"out of range! finished!"<<endl;
        return 0;
    }
    cout<<"please input all of elements of A:"<<endl;
    for(i=0; i<n; i++)
    {
        cin>>A[i];
    }
    pl_alm(A,n,n);
    return 0;
}

例5.整數劃分問題

将正整數n表示成一系列正整數之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數n的這種表示稱為正整數n的劃分。求正整數n的不同劃分個數。

分析：

如果設p(n)為正整數n的劃分數,則難以找到遞歸關系,是以考慮增加一個自變量:将最大加數n1不大于m的劃分個數記作q(n,m),可以建立q(n,m)的如下遞歸關系:

(1) q(n,1)=1,n>=1;

當最大加數n1不大于1時，任何正整數n隻有一種劃分形式，即n=1+1+1+…+1

(2) q(n,m)=q(n,n),m>=n;

最大加數n1實際上不能大于n,是以，q(1,m)=1。

(3) q(n,n)=1+q(n,n-1);

正整數n的劃分由n1=n的劃分和n1≤n-1的劃分組成。

(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;

正整數n的最大加數n1不大于m的劃分由n1=m的劃分和

n1≤m-1 的劃分組成。

例如正整數6有如下11種不同的劃分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。

分析如下：

q(6,6)=1+q(6,5)

q(6,5)=q(6,4)+q(1,5)=q(6,4)+1

q(6,4)=q(6,3)+q(2,4)=q(6,3)+q(2,2)=q(6,3)+q(2,1)+1=q(6,3)+1+1

q(6,3)=q(6,2)+q(3,3)=q(6,2)+q(3,2)+1=q(6,2)+q(3,1)+q(1,2)+1=q(6,2)+1+1+1

q(6,2)=q(6,1)+q(4,2)=q(6,1)+q(4,1)+q(2,2)=q(6,1)+1+q(2,1)+1=q(6,1)+1+1+1

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int division(int n,int m)
{
    if(n==1||m==1) return 1;
    else if(n<m) return division(n,n);
    else if(n==m) return division(n,n-1)+1;
    else if(n>m)  return division(n,m-1)+division(n-m,m);
}
int main()
{
    int n,num;
    cout<<"this app divide n,please input n:"<<endl;
    cin>>n;
    num=division(n,n);
    cout<<"the number of the division of n is: "<<num<<endl;
    return 0;
}

例6. Hanoi塔問題

設a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編号為1,2,…,n,現要求将塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：

規則1：每次隻能移動1個圓盤；

規則2：任何時刻都不允許将較大的圓盤壓在較小的圓盤之上；

規則3：在滿足移動規則1和2的前提下，可将圓盤移至a,b,c中任一塔座上。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<string>
#include<algorithm>
using namespace std;
int k;
void dispmove(int n,char x,char y)
{
    cout<<"NO."<<++k<<":  ";
    cout<<"floor."<<n<<":"<<x<<"->"<<y<<endl;
}
void hanoi(int n,char A,char B,char C)
{
    if(n>0)
    {
        hanoi(n-1,A,C,B);
        dispmove(n,A,C);
        hanoi(n-1,B,A,C);
    }
}
int main()
{
    int n;
    cout<<"請輸入漢諾塔層數："<<endl;
    while(cin>>n)
    {
        k=0;
        hanoi(n,'A','B','C');
        cout<<"The process is finished!"<<endl;
    }
    return 0;
}

例7.秦九韶算法

一般地，一進制n次多項式的求值需要經過2n-1次乘法和n次加法，而秦九韶算法隻需要n次乘法和n次加法。

一次多項式：

算法設計與分析第2章 遞歸與分治政策第2章 遞歸與分治政策
改寫如下形式：
算法設計與分析第2章 遞歸與分治政策第2章 遞歸與分治政策
時間複雜度：O(N),空間複雜度：O(N)

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
float qinjiushao_alm(float x,float A[],int n)  //A[0...n],由于計算時倒序，即A[0]*pow(x,n)+A[1]*pow(x,n-1)+...+A[n-1]*x+A[n],是以請輸入時按A[n...0]順序輸入
{
    float p;
    if(n==0) p=A[0];
    else p=qinjiushao_alm(x,A,n-1)*x+A[n];
    return p;
}
int main()
{
    int i,n;
    float x=0,result=0;
    float A[100];
    cout<<"please input order number of polynomial A:"<<endl;
    cin>>n;
    cout<<"please input coefficient of polynomial A:"<<endl;
    for(i=0; i<=n; i++)
    {
        cin>>A[i];
    }
    cout<<"please input value of x:"<<endl;
    cin>>x;
    result = qinjiushao_alm(x,A,n);
    cout<<"the result of polynomial is:"<<result<<endl;
    return 0;
}

2.2 分治法

基本條件：

1.原問題可分割成k個子問題，1＜k≤n

2.這些子問題都可解

3.可利用這些子問題的解求出原問題的解

特征：

1.該問題的規模縮小到一定的程度就可以容易地解決；

2.該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質

（如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質）

3.利用該問題分解出的子問題的解可以合并為該問題的解；

4.該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子問題。

例1.二分搜尋

給定已按升序排好序的n個元素a[0:n-1]，現要在這n個元素中找出一特定元素x。

時間複雜度：O(logn)

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int Binary_Search(int a[],int x,int n)
{
    int l=1,r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(x==a[mid]) return mid;
        else if (x>a[mid]) l=mid+1;
        else r=mid-1;
    }
    return -1;
}
int main()
{
    int a[100];
    int i,n,x,pos;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    while(cin>>x)
    {
        pos=Binary_Search(a,x,n);
        if(pos==-1) cout<<"not found!"<<endl;
        else cout<<"the position of "<<x<<" is: "<<pos<<endl;

        //利用C++自帶二分搜尋函數可判斷x是否存在
        /*if(binary_search(a+1,a+n+1,x))
            cout<<"the C++ function can find x!"<<endl;
        else
            cout<<"the C++ function cannot find x!"<<endl;
        */
    }
    return 0;
}

例2.合并排序

基本思想：将待排序元素分成大小大緻相同的2個子集合，分别對2個子集合進行排序，最終将排好序的子集合合并成為所要求的排好序的集合。

時間複雜度：

T(n)=O(1),n<=1

T(n)=2T(n/2)+O(n),n>1

T(n)=O(nlogn)是漸進意義上的最優算法，輔助空間O(n)

性能分析：與其他O(NlogN)排序算法比較，歸并排序的運作時間嚴重依賴于比較元素和在數組中移動元素的相對開銷，這和語言有關。比如在Java中比較操作是昂貴的，但移動元素的開銷的較小的；而C++通常相反。

合并排序比較占記憶體，但效率高且穩定。

基本步驟：

1.申請兩個與已經排序序列相同大小的空間，并将兩個序列拷貝其中；

2.設定最初位置分别為兩個已經拷貝排序序列的起始位置，比較兩個序列元素的大小，依次選擇相對小的元素放到原始序列；

3.重複2直到某一拷貝序列全部放入原始序列，将另一個序列剩下的所有元素直接複制到原始序列尾。

設歸并排序的目前區間是R[low…high]，分治法的三個步驟是：

1.分解：将目前區間一分為二，即求分裂點

2.求解：遞歸地對兩個子區間R[low…mid]和R[mid+1…high]進行歸并排序；

3.組合：将已排序的兩個子區間R[low…mid]和R[mid+1…high]歸并為一個有序的區間R[low…high]。遞歸的終結條件：子區間長度為1（一個記錄自然有序）。

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//将兩個有序子數組a[begin...mid]和a[mid+1...end]合并,（負責在合并時排序）
void MergeArray(int a[],int begin,int mid,int end,int temp[])
{
    int i=begin,j=mid+1;
    int m=mid,n=end;
    int k=0;
    while(i<=m&&j<=n)
    {
        if(a[i]<=a[j])
        {
            temp[k++]=a[i++];
        }
        else
        {
            temp[k++]=a[j++];
        }
    }
    while(i<=m)
    {
        temp[k++]=a[i++];
    }
    while(j<=n)
    {
        temp[k++]=a[j++];
    }
    //把temp數組中的結果裝回a數組
    for(i=0; i<k; i++)
    {
        a[begin+i]=temp[i];
    }
}
void mergesort(int a[],int begin,int end,int temp[]) //區間分解
{
    if(begin<end)
    {
        int mid=(begin+end)/2;
        mergesort(a,begin,mid,temp); //左邊有序
        mergesort(a,mid+1,end,temp); //右邊有序
        MergeArray(a,begin,mid,end,temp); //将左右兩邊有序的數組合并
    }
}
int main()
{
    int i,n;
    int a[110],temp[110];
    while(cin>>n)
    {
        for(i=0; i<n; i++)
        {
            cin>>a[i];
        }
        mergesort(a,0,n-1,temp);
        for(i=0; i<n-1; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<a[n-1]<<endl;
    }
    return 0;
}

例3.快速排序

在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就能交換到後面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數較少。

最壞情況時間複雜度為O(n*n)，最好情況時間複雜度為O(nlogn)，平均時間複雜度為O(nlogn),輔助空間O(n)或O(logn)

代碼：

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int Partition(int a[],int p,int r) 
{
    int i=p,j=r+1;
    int x=a[p];
    //将<x的元素交換到左邊區域
    //将>x的元素交換到右邊區域
    while(true)
    {
        while(a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        //cout<<"i="<<i<<",j="<<j<<",a[i]="<<a[i]<<",a[j]="<<a[j]<<endl;
        swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    //cout<<"a[p]="<<a[p]<<",a[j]="<<a[j]<<endl;
    return j;
}
void QuickSort(int a[],int p,int r)
{
    if(p<r)
    {
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1); //對左半段排序
        QuickSort(a,q+1,r); //對右半段排序
    }
}
int main()
{
    int i,n;
    int a[110];
    while(cin>>n)
    {
        for(i=0; i<n; i++)
        {
            cin>>a[i];
        }
        QuickSort(a,0,n-1);
        for(i=0; i<n-1; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<a[n-1]<<endl;
    }
    return 0;
}
算法設計與分析 遞歸算法 分治法
上一篇: Redis知識梳理(28) [ 壓縮清單 ]增加元素級聯更新IntSet 小整數集合
下一篇: hbase叢集搭建及使用

繼續閱讀