遞推法和遞歸法誰效率更高?排列組合問題在暴力枚舉的情況一般有3種情況，我來為大家講解一下關于遞推法和遞歸法誰效率更高?跟着小編一起來看一看吧!

遞推法和遞歸法誰效率更高

排列組合問題在暴力枚舉的情況一般有3種情況

我們在此記個數為N

• 情況一：打印n個數的全排列:

N=n!N=n!

• 情況二：打印n個數中任意m個數的全排列

N=Amn=n!(n−m)!N=Anm=n!(n−m)!

• 情況三：打印n個數中任意m個數的組合

N=Cmn=n!m!(n−m)!N=Cnm=n!m!(n−m)!

遞推是按照一定的規律來計算序列中的每個項，通常是通過計算前面的一些項來得出序列中的指定項的值。其思想是把一個複雜的龐大的計算過程轉化為簡單過程的多次重複，該算法利用了計算機速度快和不知疲倦的機器特點。

所謂遞歸，實際上是一種把大問題逐步縮小成最小同類問題的過程，其中最小問題的解是已知的，往往是所給條件。

比較兩者，可清楚地發現遞歸是逆向的遞推。遞推是從最小問題出發一步步向前求解，遞歸則是從最大問題開始不斷去調用自己達到最小問題的解然後再逐層歸來。

所以一般來講遞推的效率大于遞歸，并且在遞歸中問題的n是在計算前就已經知道的，而遞推可以在求解中确定。

我們以斐波那契數列距離，其數學遞推公式如下(無論遞推還是遞歸，一般都從遞推公式開始分析)

⎧⎩⎨f(n)=f(n−1) f(n−2)f(1)=f(2)=1n>2,n∈N {f(n)=f(n−1) f(n−2)f(1)=f(2)=1n>2,n∈N

接下來我們利用代碼來分别示範一遍兩種方法

• 斐波那契——遞歸

#include <iostream> #include <ctime> using namespace std; //由于數列發散快，使用int類型當n較大時可能會溢出，此處僅為舉例 int func_fib(unsigned int n) { if(n==0) //盡管遞推公式給出n不會等于零，但為了以防萬一添加了n為0的情況 return 0; if(n==1 || n==2) return 1; else return func_fib(n-1) func_fib(n-2); } int main() { unsigned int n = 0; cout << "請輸入所求斐波那契數列項的項數n: " << endl; cin >> n; //輸出結果和所用時間，單位：時鐘單位 clock_t start,end; start = clock(); //開始 cout << func_fib(n) << endl; end = clock(); //結束 cout << "計算所用時間為: " << (double)(end-start) << endl; return 0; }

• 斐波那契——遞推

#include <iostream> #include <ctime> using namespace std; //同樣，n過大會溢出 int func_fib(unsigned n) { int fib = 0; int fib_n = 1; for(int i=0; i<n; i ) { int temp = fib_n; fib_n = fib fib_n; fib = temp; } return fib; } int main() { cout << "請輸入所求斐波那契數列項的項數n: " << endl; unsigned int n; cin >> n; //輸出結果和所用時間 clock_t start,end; start = clock(); //開始 cout << func_fib(n) << endl; end = clock(); //結束 cout << "計算所用時間為:" << (double)(end-start) << endl; return 0; }

我們對上述排列組合對三種情況寫代碼

輸出全排列

STL方法：

#include <iostream> #include <algorithm> #include <vector> using namespace std; //輸出序列 void printSequence(vector<int> num) { vector<int>::iterator it; //叠代器 cout << "當前序列: "; //遍曆 for(it=num.begin(); it!=num.end(); it ) cout << *it << " "; cout << endl; } int main() { /* * 注意，使用sort()與next_permutation()需要包含algorithm頭文件 */ //初始化序列 vector<int> num{2,1,5,3,4}; //排序（正序） sort(num.begin(), num.end()); //輸出全排列 do{ printSequence(num); }while(next_permutation(num.begin(), num.end())); return 0; }

遞歸方法:

#include <iostream> #include <vector> #include <algorithm> using namespace std; void printSequence(vector<int> num) { vector<int>::iterator it; //叠代器 cout << "當前序列: "; //遍曆 for(it=num.begin(); it!=num.end(); it ) cout << *it << " "; cout << endl; } /* *這裡num必須用引用。 *否則叠代器指向的num是原實例，而傳入的num是拷貝的實例，輸出結果都是原序列。 *詳細情況可以調用下方的test嘗試下(該函數已被注釋) */ void Perm(vector<int> &num, vector<int>::iterator begin, vector<int>::iterator end) { if(begin == end-1) printSequence(num); //打印，此處還可以統計個數 else{ vector<int>::iterator it; for(it=begin; it<end; it ) { swap(*begin, *it); Perm(num, begin 1, end); swap(*begin, *it); } } } //void test(vector<int> num, vector<int>::iterator it) //{ // num[0] = 10; // cout << *it << " " << num[0] << endl; //} int main() { vector<int> num{1,2,3}; Perm(num, num.begin(), num.end()); return 0; }

想要打印n個數中任意m個數的全排列其實很簡單，隻需要在上述代碼中稍作修改即可

打印序列函數printSequence

void printSequence(vector<int> num, vector<int>::iterator begin, vector<int>::iterator end) { vector<int>::iterator it; //叠代器 cout << "當前序列: "; //遍曆 for (it = begin; it != end; it ) cout << *it << " "; cout << endl; }

獲取全排列的函數Perm(增加了計數功能，需傳入變量cnt)

/* *這裡num必須用引用。 *否則叠代器指向的num是原實例，而傳入的num是拷貝的實例，輸出結果都是原序列。 *詳細情況可以調用下方的test嘗試下(該函數已被注釋) *參數：num：原序列，begin：vector的begin叠代器， end：vector的end叠代器，m:從n個數中打印m個數的全排列中的m，cnt：用于統計最後全排列個數 */ void Perm(vector<int>& num, vector<int>::iterator begin, vector<int>::iterator end, unsigned int m, int &cnt) { if (begin == num.begin() m) { printSequence(num, num.begin(), num.begin() m); //打印 cnt; //統計個數 } else { vector<int>::iterator it; for (it = begin; it < end; it ) { swap(*begin, *it); Perm(num, begin 1, end, m, cnt); swap(*begin, *it); } } }

組合不同于排列，排列有序而組合無序。所以，我們先來研究其子集的生成。

我們按如下記集合A，其中n為其元素的個數

A={x0,x1,x2,...,xn−1}A={x0,x1,x2,...,xn−1}

其子集有

ϕ,{x0},{x1},...,{x0,x1,...,xn−1}ϕ,{x0},{x1},...,{x0,x1,...,xn−1}

不妨設子集個數為N，則有

N=2nN=2n

這個式子很容易跟二進制聯系起來，我們不由得會去想子集跟二進制之間的關系

我們不妨構造一個n位的二進制數，每一位都對應集合中的一個元素，當子集中包含該元素，則對應的二進制數的該位上的值就為1否則為0，那麼每個子集都對應一個獨一無二的n位二進制數了。

以n=3時的集合為例，此時有

A={x0,x1,x2}A={x0,x1,x2}

則其子集與二進制數對應關系如下

此外我們還需要知道:

• 位運算

1<<n //該位運算等價于2的n次幂

• 與運算

10001&101=10001&00101=0000110001&101=10001&00101=00001

此處與運算僅舉例，當兩個二進制數位數不一緻則再前面補0然後對應位置做與運算

接下來我們以打印集合{0,1,2,..,n-1}的子集為例，則有如下函數

void print_subset(int n) { for (int i = 0; i < (1 << n); i ) //從000到2^n-1對應的二進制，一共2^n個子集 { //将每個子集都取出，對應數字i //在子集i的情況下，不斷嘗試取元素個數為j，其中每個元素的值跟其序号相同都為j for (int j = 0; j < n; j ) //如果子集i中含多個數，此處的for則打印多個數，若i僅1個數此處for也隻尋找并打印僅含的這一個數j if (i & (1 << j)) //将2的j次幂轉化為二進制形式，通過與運算，去測試僅包含一個十進制數j的集合是不是該子集的子集 cout << j << " "; //如果是，則說明子集i中包含十進制數j，此時打印j。 cout << endl; } }

那麼基礎知識已經介紹完了，我們回到情況三，對照子集對應二進制數的方法。我們知道一個子集對應唯一的一個二進制數，那麼一個有k個元素的子集它對應二進制數一定有k個1。所以找查子集的問題就變成了找查含k個1的二進制數。

這裡介紹個技巧(kk為一個名為kk的二進制數)

kk = kk & (kk-1)

它可以跳過0消除數中最後一個1，這樣我們執行此操作的次數就是二進制數中含1的個數

則針對情況三有如下代碼

//打印n個數中取m個數的組合 void print_set(int n, int m) { for (int i = 0; i < (1 << n); i ) { int cnt = 0, kk = i; while (kk) { kk = kk & (kk - 1); cnt ; } if (cnt == m) { for (int j = 0; j < n; j ) //此處跟上方print_subset函數同理 if (i & (1 << j)) cout << j << " "; cout << endl; } } }

• 羅永軍,郭衛斌. 算法競賽入門到進階[M]. 北京 : 清華大學出版社,2019.

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!