算法设计与分析：递归算法

发表于 更新于 分类于

算法思路

  1. 根据主问题找到子问题，子问题必须能够减小主问题的规模：
    1. 子问题通过假设主问题的一部分答案，以此减少主问题的规模（确定主问题的一部分结果）;
    2. 子问题需要考虑自身假定的答案的其它可能性，采用其他可能性（可能体现为新的参数）继续递归或借助循环进行遍历并递归：
      • 什么时候需要一个循环？当前子问题没有解决完的时候。如全排列问题，子问题假设的是第 i 个元素已经确定，但这第 i 个元素具体确定为什么是有多种情况的，在没有考虑到所有情况前该子问题不能算作解决，所以需要一个循环。
      • 什么时候不需一个循环？当前子问题假定的结果需要考虑的情况比较少的时候。如整数划分问题，子问题假设的是最大的项是 k，按照这个假设 k 解决了子问题后，考虑到了另外的情况是最大的项可能小于 k，所以我按照小于 k 的方法再调用一次递归，便解决了子问题，此时由于其他情况比较少所有无需循环。
    3. 拥有明确的终止情况及其结果（有不可再划分为子问题的情况）；
  2. 确定终止条件，明确子问题思路，明确子问题继续划分的条件和方法；
  3. 编写子问题解决函数。

明显特征
往往结果需要到最后才能确定，即确定了结果的一部分后，仍有很多情况需要讨论。

打比方
组织一队人去旅游，这队人是怎么样的，得等到队伍的最后一个人确定下来了才知道，而前面不管确定了多少人，都无法知道最后这个队伍是怎么样的。

例题

1. 排列问题

求 n 个元素的全排列。

解题思路

  1. 子问题：子问题假设了一种排列的队首元素是 a1a_1
  2. 子问题假定结果的其他情况：队首元素可以是除了 aia_i 以外的其他元素。解决方法：让 aia_i 全部当一次队首元素。
  3. 子问题终止条件：当未确定的结果只剩下一个元素时，整个序列便已经确定，可以输出。
  4. 子问题划分方法：
    Arr(list,R)Arr(list, R) 中 listlist 为已经确定的排序，RR 为当前要进行排列的集合。
    每个子问题将自己需要排列的集合中的元素逐一调整到队首，每调整一次，调用一次 Arr(list, R - {队首元素})。当 RR 中只有一个元素的时候，就可以输出了。
    也就是每个子问题都确定了一个队首元素，也就是减少后续子问题需要排列的元素数量，以此减小问题的规模。

存在的问题及优化

值传递 list 导致的内存占用大问题
list 统一使用指针传送，多加一个参数 k 用于确定已经排列的元素的位置（前 k 个元素已排列）。
在排列之前直接将需要调至队头的元素和当前队头元素直接进行交换。排列后调换回去（保持集合的顺序方便按下标遍历所有元素）

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Arr(vector<int> &arrange_list, int arranging_divide_index) {
    if (arranging_divide_index == arrange_list.size()) {
        for (size_t i = 0; i < arrange_list.size(); i ++) {
            cout << arrange_list[i] << " ";
        }
        cout << endl;
        return;
    }
    else {
        for (size_t i = arranging_divide_index; i < arrange_list.size(); i ++) {
            swap(arrange_list[arranging_divide_index], arrange_list[i]);
            Arr(arrange_list, arranging_divide_index + 1);
            // 不能打乱待排序集合的顺序
            swap(arrange_list[arranging_divide_index], arrange_list[i]);
        }
    }
}

2. 整数划分问题

求一个整数 n 的所有划分情况（不包含 0 ），如 2 的划分有：

1
2
2
1 1

解题思路

  1. 子问题：子问题假设划分的最大的整数为 n 且已经存在于队列中（即确定了其中一个划分数，减少了需要划分的整数的大小，减小了问题的规模），随后继续划分子问题；
  2. 子问题假设的其他情况：最大整数为 n 并不存在于队列中，划分子问题，让子问题假设 n-1 存在于队列中，同样需要考虑不存在情况，即再让子问题假设 n-2 存在于队列中…递归即可，无论存不存在都属于一种划分，所以最终都要加起来。
  3. 递归函数：
    q(n,m)q (n, m) 表示在划分中最大的项不超过 mm 的情况下，对 nn 进行划分所有可能的结果。

q(n,m)={1m=1,n=1q(n,n)n<m1+q(n,n−1)m=nq(n−m,m)+q(n,m−1)1<m<nq(n,m)=\left\{ \begin{array}{rcl} 1 & & {m = 1 , n = 1}\\ q(n, n) & & {n < m}\\ 1 + q(n, n-1) & & {m = n} \\ q(n-m, m) + q(n, m-1) & & {1 < m < n}\\ \end{array} \right.

公式解读：

  1. 第一条：
    1. 最大项为 1，即划分的所有项都是 1, 只有一种情况；
    2. 需要划分的整数为 1，只有划分为 1 一种情况；
  2. 最大整数不会超过 n
  3. m = n 的时候，可以确定一定存在一种划分为 n，所以只需要确定最大整数不超过 n - 1 的时候的划分结果的数量再 + 1 即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int NumberOfDivide(int total_num, int max_term)
{
    if (total_num == 1 || max_term == 1) {
        return 1;
    }
    if (total_num < max_term) {
        return NumberOfDivide(total_num, total_num);
    }
    if (total_num == max_term) {
        return 1 + NumberOfDivide(total_num, total_num - 1);
    }
    return NumberOfDivide(total_num - max_term, max_term) + NumberOfDivide(total_num, max_term - 1);
}

附：Latex 表示分段函数

1
2
3
4
5
6
7
8
9
函数名=\left\{
\begin{array}{rcl}
表达式1 & & {范围 < 变量}\\
表达式2 & & {范围 < 变量}\\
表达式3 & & {范围 < 变量}\\
表达式4 & & {范围 < 变量}
\end{array} \right.

\leq 小于等于

函数名={表达式1范围<变量表达式2范围<变量表达式3范围<变量表达式4范围≤变量函数名=\left\{ \begin{array}{rcl} 表达式1 & & {范围 < 变量}\\ 表达式2 & & {范围 < 变量}\\ 表达式3 & & {范围 < 变量}\\ 表达式4 & & {范围 \leq 变量} \end{array} \right.