當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

算法设计与分析第2章递归与分治策略

發布時間：2023/11/27 生活经验 32 豆豆

生活随笔收集整理的這篇文章主要介紹了算法设计与分析第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數列。它可以遞歸地定義為：

代碼：

#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)定義如下：

代碼：

#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次加法。
一次多項式：

改寫如下形式：

時間復雜度：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;elsecout<<"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;
}

總結

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

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