递归与回溯法

递归


 

引入

  什么是递归?先看大家都熟悉的一个民间故事:从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说,从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说……。象这样,一个对象部分地由它自己组成,或者是按它自己定义,我们称之为递归。
  一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的。在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。

递归的概念

  • 递归过程是借助于一个递归工作栈来实现的
  • 问题向一极推进,这一过程叫做递推
  • 问题逐一解决,最后回到原问题,这一过程叫做回归
  • 递归的过程正是由递推回归两个过程组成。

  用递归方法编写的问题解决程序具有结构清晰可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。

递归的应用及实现

  递归算法在可计算性理论中占有重要地位,它是算法设计的有力工具,对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识,只不过初学者要建立起递归概念不十分容易。

  我们先从一个最简单的例子导入。

  求斐波那契数列的第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数组用于记录每一行皇后所在的列号。

  回溯法是一种非常实用的算法,它可以解决很多组合优化问题。但是,由于回溯法的时间复杂度较高,因此在实际应用中需要注意优化。

 

                                                                        码字不易,点个赞呗§(* ̄▽ ̄*)§

热门相关:仙城纪   大神你人设崩了   大神你人设崩了   薄先生,情不由己   薄先生,情不由己