往期文章
1 緒論-資料結構的基本概念
2 緒論-演算法
3 線性表-順序表和鏈式表概念及其代碼實作
4 查找-順序+折半+索引+哈希
5 插入排序-希爾排序-選擇排序-冒泡排序-快速排序-基數排序-外部排序-歸并排序
文章目錄
- 1 遞回的定義
- 2 Fibonacci數列遞回求解和非遞回求解
- 3 回文串檢測的遞回求解和非遞回求解
- 4 分治遞回
- 4.1 分治遞回思想
- 4.2 分治法的適用條件
- 4.3 分治法的基本步驟
- 4.4 遞回復雜度計算的三種方式求解
- 4.4.1 代換法
- 4.4.2 迭代法-直接展開
- 4.4.3 主方法
- 5 實體應用
1 遞回的定義
- 子程式（或函式）直接呼叫自己或通過一系列呼叫陳述句 間接呼叫自己，稱為遞回，
- 遞回是一種描述問題和解決問題的基本方法，
直接遞回呼叫
void A()
{
...
A();
...
}
間接呼叫遞回
void B()
{
...
C();
...
}
void C()
{
...
B();
...
}
2 Fibonacci數列遞回求解和非遞回求解
尾遞回都能轉換成非遞回的寫法
尾遞回是指遞回只是出現在return的時候
遞回求解
int f(int n)
{
if(n<=1)
return n;//結束條件
else
return(f(n-1)+f(n-2));//遞回方程
}
非遞回求解
int f(int n)
{
int pre,now,next,j;
if(n<=1)return(n);
else
{
pre=0;now=1;
for(j=2;j<=n;j++)
{
next=pre+now;
pre=now;
now=next
}
return(next);
}
}
3 回文串檢測的遞回求解和非遞回求解
如果一個字串從左向右讀和從右向左讀完全相同（不區分大小寫），則這個字串稱為回文串（palindrome)，例如“noon”、“madam”等都是回文串，
遞回求解
bool palindrome(string &s,unsigned h,unsigned t)
{
if (h>=t) return 1;
if(tolower(s[h])==tolower(s[t]))
return palindrome(s,h+1,t-1);
else
return 0;
}
非遞回求解
bool palindrome(string &s)
{
int h=0,t=strlen(s)-1;
while(h<=t)
{
if(s[h]!=s[t])return 0;
h++;t--;
}
return 1;
}
4 分治遞回
4.1 分治遞回思想
- 對這k個子問題分別求解，如果子問題的規模仍然不夠 小，則再劃分為k個子問題，如此遞回的進行下去，直 到問題規模足夠小，很容易求出其解為止，
- 將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解，
4.2 分治法的適用條件
- 該問題的規模縮小到一定的程度就可以容易地解決；
- 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質（前提）
- 利用該問題分解出的子問題的解可以合并為該問題的解；（如果具備前兩條不具備第三條可以考慮使用貪婪演算法和動態規劃）
- 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題，（這條特征設計分治法的效率）
4.3 分治法的基本步驟
注意看注釋
{
if ( | P | <= n0) adhoc(P); //解決小規模的問題
divide P into smaller subinstances P1,P2,...,Pk；//分解問題
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //遞回的解各子問題
return merge(y1,...,yk); //將各子問題的解合并為原問題的解
}
4.4 遞回復雜度計算的三種方式求解
4.4.1 代換法
前提說明（忽略細節 如果后期發現細節很重要再加入進來）
T(n) 由兩部分組成 一個是 每個小部分的計算時間之和 + 分解時間和解和并的時間f（n）
主要思想
- 猜測解的形式.
- 通過數學歸納法找出使解真正有 效的常數
4.4.2 迭代法-直接展開
4.4.3 主方法
5 實體應用
假設有n個資料a[n],要把這n個資料的全排列都列印出來，考慮遞回方法PrintPermutation，
-
第一個位置的元素可能是這n個元素的任意一個，可以采用swap，將第一個位置與其他位置的交換，就可以得到第一個位置元素不同的情況，而余下的遞回呼叫列印全排列函式PrintPermutation完成，但要注意還應該交換回去，便于后面的正確處理，
-
遞回函式內部，又會當前的第一個位置（第2個位置）的元素與余下n-2個位置元素交換；里面又會當前的第一個位置（第3個位置）的元素與余下n-3個位置元素交換；……；最后第n個位置的元素，就表示前面的n-1個位置已經處理了，就可以列印了，所以遞回列印條件是位置k=n，這個也是遞回出口
a[] 存放資料 k表示第一個交換的位置，一般為1，n便是資料的個數，
void PrintPermutation(int a[], int k, int n){
if (k == n){
for (int i = 1; i < n + 1; ++i){
cout << a[i] << " ";
}
cout << endl;
return;
}
else{
for (int i = k; i < n+1; ++i){
Swap(a[k], a[i]);
PrintPermutation(a, k + 1, n);
Swap(a[k], a[i]);
}
}
}
int main()
{
int *a, len;
cout << "len:" << endl;
cin >> len;
a = new int[len+1];
if (!a)return -1;
for (int i = 1; i < len + 1; ++i)
a[i] = i;
PrintPermutation(a, 1, len);
}
如果有遺漏和錯誤的地方，歡迎指出，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/267162.html
標籤：其他
上一篇：SSL協議原理