遞回

引入

　　什么是遞回？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說……，象這樣，一個物件部分地由它自己組成，或者是按它自己定義，我們稱之為遞回，　　一個函式、程序、概念或數學結構，如果在其定義或說明內部又直接或間接地出現有其本身的參考，則稱它們是遞回的或者是遞回定義的，在程式設計中，程序或函式直接或者間接呼叫自己，就被稱為遞回呼叫，

遞回的概念

遞回程序是借助于一個遞回作業堆疊來實作的
問題向一極推進，這一程序叫做遞推；
問題逐一解決，最后回到原問題，這一程序叫做回歸，
遞回的程序正是由遞推和回歸兩個程序組成，

　　用遞回方法撰寫的問題解決程式具有結構清晰，可讀性強等優點，且遞回演算法的設計比非遞回演算法的設計往往要容易一些，所以當問題本身是遞回定義的，或者問題所涉及到的資料結構是遞回定義的，或者是問題的解決方法是遞回形式的時候，往往采用遞回演算法來解決，

遞回的應用及實作

　　遞回演算法在可計算性理論中占有重要地位，它是演算法設計的有力工具，對于拓展編程思路非常有用，就遞回演算法而言并不涉及高深數學知識，只不過初學者要建立起遞回概念不十分容易，

　　我們先從一個最簡單的例子匯入，

　　求斐波那契數列的第n位（C++代碼）：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int fibonacci(int n) {
 5     if (n <= 1) {
 6         return n;
 7     } else {
 8         return fibonacci(n-1) + fibonacci(n-2);
 9     }
10 }
11 
12 int main() {
13     int n ;
14     cin >> n ;
15     printf("斐波那契數列前 %d 項為：\n", n);
16     for (int i = 1; i <= n; i++) {
17         printf("%d ", fibonacci(i));
18     }
19     printf("\n");
20     return 0;
21 }

回溯法

回溯法的概念與模板

　　回溯法是一種常用的演算法，它主要用于解決一些組合優化問題，例如八皇后問題、0/1背包問題等，回溯法的基本思想是：從問題的某一種狀態開始，搜索所有可能的情況，直到找到符合要求的解為止，

　　回溯法的實作程序通常采用遞回的方式，每次遞回都會嘗試一種可能的情況，如果這種情況不符合要求，就回溯到上一層遞回，嘗試其它的情況，在回溯的程序中，需要記錄已經嘗試過的情況，以避免重復計算，

　　回溯法的時間復雜度通常比較高，因為它需要搜索所有可能的情況，但是，在一些特殊的情況下，回溯法可以通過剪枝等優化技巧來提高效率，

　　回溯法是一種常用的演算法思想，可以用于解決很多問題，比如八皇后問題、0/1背包問題等，下面是一個用C語言實作回溯法的模板：

 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_N 100 // 最大的問題規模
 4 
 5 int n; // 問題規模
 6 int a[MAX_N]; // 存盤解的陣列
 7 
 8 // 檢查當前解是否合法
 9 int check(int cur) {
10     // TODO: 根據具體問題實作
11 }
12 
13 // 回溯函式
14 void backtrack(int cur) {
15     if (cur == n) { // 找到一個解
16         // TODO: 處理解的代碼
17         return;
18     }
19     for (int i = 0; i < n; i++) { // 列舉當前位置的所有可能取值
20         a[cur] = i; // 嘗試將當前位置設為i
21         if (check(cur)) { // 如果當前解合法
22             backtrack(cur + 1); // 繼續搜索下一個位置
23         }
24     }
25 }
26 
27 int main() {
28     // TODO: 讀入問題規模n和其它必要的輸入
29     backtrack(0); // 從第0個位置開始搜索
30     return 0;
31 }

在實際使用中，需要根據具體問題實作check函式和處理解的代碼，

八皇后問題

　　下面是一個八皇后問題的回溯法實作：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 8;
 5 int queen[N]; // 存放每一行皇后所在的列號
 6 
 7 bool check(int row, int col) // 判斷當前位置是否可以放置皇后
 8 {
 9     for (int i = 0; i < row; i++)
10     {
11         if (queen[i] == col || abs(row - i) == abs(col - queen[i]))
12             return false;
13     }
14     return true;
15 }
16 
17 void backtrack(int row) // 回溯函式
18 {
19     if (row == N) // 找到一組解
20     {
21         for (int i = 0; i < N; i++)
22             cout << queen[i] << " ";
23         cout << endl;
24         return;
25     }
26 
27     for (int col = 0; col < N; col++) // 列舉當前行所有可能的列
28     {
29         if (check(row, col)) // 如果當前位置可以放置皇后
30         {
31             queen[row] = col; // 記錄當前皇后所在的列號
32             backtrack(row + 1); // 繼續搜索下一行
33         }
34     }
35 }
36 
37 int main()
38 {
39     backtrack(0);
40     return 0;
41 }

　　在上面的代碼中，check函式用于判斷當前位置是否可以放置皇后，backtrack函式用于搜索所有可能的情況，在搜索程序中，queen陣列用于記錄每一行皇后所在的列號，

　　回溯法是一種非常實用的演算法，它可以解決很多組合優化問題，但是，由于回溯法的時間復雜度較高，因此在實際應用中需要注意優化，

碼字不易，點個贊唄§(*￣▽￣*)§

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547279.html

標籤：其他

上一篇：Maven安裝詳解

下一篇：day06-靜態資源訪問&Rest風格

遞回與回溯法

遞回

引入

遞回的概念

遞回的應用及實作

回溯法

回溯法的概念與模板

八皇后問題