蓝桥杯第十五届抱佛脚（四）递归与分治

蓝桥杯第十五届抱佛脚（四）递归与分治

递归和分治是两种常见的问题解决方法，它们是不同的概念，但它们经常在一起使用，有时甚至是互相支持的。

递归

递归是一种解决问题的方法，其中一个函数通过不断调用自身来解决更小规模的子问题，直到达到基本情况为止。递归函数通常包含两个部分：

1. 基本情况：在递归调用中不再进行递归的情况，这是递归终止的条件。
2. 递归情况：递归函数调用自身来解决更小规模的子问题。

递归通常用于解决具有自相似性质的问题，例如树结构、图结构等。经典的递归算法包括斐波那契数列的计算、二叉树的遍历等。

分治

分治是一种算法设计策略，它将问题分解成若干个规模较小且相互独立的子问题，然后解决这些子问题，最后将子问题的解合并起来得到原问题的解。分治算法一般包括三个步骤：

1. 分解：将原问题分解成若干个规模较小的子问题。
2. 解决：递归地解决这些子问题。当子问题足够小，可以直接求解。
3. 合并：将子问题的解合并成原问题的解。

分治算法通常用于解决可以被分割成互相独立的子问题的问题。经典的分治算法包括归并排序、快速排序等。

递归与分治的联系

尽管递归和分治是不同的概念，但它们经常在一起使用。在分治策略中，递归用于解决子问题。分治算法将原问题分解成更小的规模，然后通过递归地解决这些子问题来实现。因此，可以说分治算法通常会使用递归来实现子问题的解决。

递归是一种解决问题的方法，而分治是一种算法设计策略。它们经常一起使用，尤其是在解决可以分解成子问题的问题时。

递归算法的实现思路

• 先「自顶向下」拆分问题，直到不能拆分为止；
  • 「自顶向下」是直接面对我们要解决的问题，逐层拆分，直到不能拆分为止，再按照拆分的顺序的逆序逐层解决，直至原问题得到了解决，这是「递归」。
• 再「自底向上」逐层把底层的结果向上汇报，直至得到原问题的解。
  • 如果我们非常清楚一个问题最开始的样子，并且也清楚一个问题是如何从它最开始的样子逐步演变成为我们想要求解的问题的样子，我们就可以通过「递推」的方式，从小规模的问题开始逐步「递推」得到最终要解决的大问题的解。

例题：递归乘法

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10
1
2

示例2:

 输入：A = 3, B = 4
 输出：12
1
2

基础解题版本：

1. 基本情况：
   • 如果 B 为 0，则直接返回 0。
   • 如果 B 为 1，则直接返回 A。
2. 递归调用：
   • 如果 B 大于 1，则递归调用 multiply(A, B-1)，这相当于将 B 逐步减一，继续进行相乘操作。
3. 合并子问题的解：
   • 在递归调用的过程中，每次将 A 与 B-1 相乘，然后将结果累加到 A 上，直到 B 减为 1 时结束递归。

时间复杂度为 O(n)。

class Solution {
    public int multiply(int A, int B) {
        if(B == 0) return 0;
        if(B == 1) return A;
        return A + multiply(A, B-1);
    }
}
1
2
3
4
5
6
7

优化题解：

1. 基本情况处理：
   • 如果其中一个数为0，则返回0。
   • 如果其中一个数为1，则返回另一个数。
2. 将问题分解为更小的子问题：
   • 将其中一个数逐步拆分为更小的部分。我们可以取其中一个数 A，并将其右移一位（相当于除以2），同时将另一个数 B 左移一位（相当于乘以2），这样可以将问题规模减小。
3. 递归求解：
   • 对拆分后的每个部分递归调用相同的函数，得到子问题的解。
4. 合并子问题的解：
   • 对子问题的解进行合并，得到最终结果。

时间复杂度为 O(log(n))

class Solution {
    public int multiply(int A, int B) {
        // 基本情况
        if (A == 0 || B == 0) {
            return 0;
        } else if (A == 1) {
            return B;
        } else if (B == 1) {
            return A;
        }

        // 将问题分解为更小的子问题
        int half_A = A >> 1;
        int double_B = B << 1;

        // 递归求解
        int product = multiply(half_A, double_B);

        // 合并子问题的解
        if (A % 2 == 0) {
            return product;
        } else {
            return product + B;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

利用并归排序深入理解递归

归并排序的基本思想：

归并排序采用分治策略，将待排序的数组分成两部分，分别进行排序，然后将两个已排序的子数组合并成一个有序的数组。

归并排序的递归过程：

1. 分解：将数组逐步分解为更小的子数组，直到每个子数组只有一个元素或为空。
2. 解决：对每个子数组进行排序，这里可以采用递归调用归并排序来解决子问题。
3. 合并：将已排序的子数组合并成一个有序的数组。

举例说明：

让我们来看一下归并排序对给定数组 [21, 12, 39, 14, 16, 10, 42, 6, 34, 34] 的执行过程：

1. 初始状态：原始数组为 [21, 12, 39, 14, 16, 10, 42, 6, 34, 34]。

2. 第一次分解：

   • 将数组分成两个子数组： [21, 12, 39, 14, 16] 和 [10, 42, 6, 34, 34]。

3. 对子数组进行排序：

   • 对两个子数组 [21, 12, 39, 14, 16] 和 [10, 42, 6, 34, 34] 分别进行排序。

4. 递归排序子数组：

   • 对第一个子数组 [21, 12, 39, 14, 16] 进行递归排序：

     • 分解成 [21, 12] 和 [39, 14, 16]。
     • 对子数组 [21, 12] 和 [39, 14, 16] 分别进行排序。

   • 对第二个子数组 [10, 42, 6, 34, 34] 进行递归排序：

     • 分解成 [10, 42] 和 [6, 34, 34]。
     • 对子数组 [10, 42] 和 [6, 34, 34] 分别进行排序。

5. 合并排序后的子数组：

   • 对排序后的子数组进行合并操作：
     • 对 [21, 12] 和 [39, 14, 16] 进行合并，得到 [12, 14, 16, 21, 39]。
     • 对 [10, 42] 和 [6, 34, 34] 进行合并，得到 [6, 10, 34, 34, 42]。

6. 最终合并：

   • 将合并后的两个子数组 [12, 14, 16, 21, 39] 和 [6, 10, 34, 34, 42] 进行合并，得到最终排序后的数组 [6, 10, 12, 14, 16, 21, 34, 34, 39, 42]。

这样，我们就完成了对给定数组 [21, 12, 39, 14, 16, 10, 42, 6, 34, 34] 的归并排序过程。

归并排序与二叉树后序遍历的递归顺序是一致的。

• 后序遍历：先递归左子树，再递归右子树，最后处理根节点。
• 归并排序：先递归左子数组，再递归右子数组，最后处理合并。

归并排序的代码示例：

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        // 递归终止条件
        if (left < right) {
            // 计算中间索引
            int mid = (left + right) / 2;
            // 递归排序左半部分
            mergeSort(arr, left, mid);
            // 递归排序右半部分
            mergeSort(arr, mid + 1, right);
            // 合并左右两部分
            merge(arr, left, mid, right);
        }
    }

    // 归并函数：将两个已排序的数组合并成一个有序数组
    public static void merge(int[] arr, int left, int mid, int right) {
        // 计算左右两部分的长度
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 将数据复制到临时数组
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // 合并左右两部分
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 将剩余的元素复制到数组中
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {21, 12, 39, 14, 16, 10, 42, 6, 34, 34};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("排序完成: " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

在这个示例中，我们通过 mergeSort 方法来实现归并排序，其中 merge 方法用于合并两个已排序的子数组。在 main 方法中，我们提供了一个示例数组，并调用 mergeSort 方法对其进行排序。

通过归并排序的执行过程，我们可以清晰地了解递归的应用和工作原理。

通过快速排序深入理解递归

随机快速排序是快速排序的一种变体，它在选择基准元素时采用了随机化的方法，以提高算法的平均性能。通过随机选择基准元素，我们可以减少最坏情况下的概率，并使算法更具有鲁棒性。

随机快速排序的基本思想：

1. 随机选择数组中的一个元素作为基准元素。
2. 将数组分成两部分，比基准元素小的放在左边，比基准元素大的放在右边。
3. 对左右两部分分别递归地进行随机快速排序。

随机快速排序的递归过程：

1. 分解：随机选择一个基准元素，并将数组分成两部分，比基准元素小的放在左边，比基准元素大的放在右边。
2. 递归排序：对左右两部分分别进行随机快速排序。
3. 合并：由于快速排序是原地排序，不需要显式合并步骤。

举例说明：

让我们来分析对数组 [21, 12, 39, 14, 16, 10, 42, 6, 34, 34] 进行随机快速排序的执行过程：

1. 初始状态：原始数组为 [21, 12, 39, 14, 16, 10, 42, 6, 34, 34]。

2. 选择基准元素：随机选择数组中的一个元素作为基准元素，假设选择的是 39。

3. 分解：

   • 根据基准元素 39，将数组分成两部分：
     • 左侧子数组：[21, 12, 14, 16, 10, 6, 34, 34]
     • 右侧子数组：[42]

4. 递归排序：

   • 对左侧子数组 [21, 12, 14, 16, 10, 6, 34, 34] 进行随机快速排序。
   • 对右侧子数组 [42] 进行随机快速排序。

5. 递归过程继续：

   • 左侧子数组 [21, 12, 14, 16, 10, 6, 34, 34]：

     • 随机选择基准元素，假设选择的是 14。
     • 分解数组，将小于 14 的放在左边，大于 14 的放在右边：
       • 左侧子数组：[12, 10, 6]
       • 右侧子数组：[21, 16, 34, 34]
     • 继续递归排序左右子数组。

   • 右侧子数组 [42]：

     • 因为只有一个元素，所以右侧子数组已经有序。

6. 重复递归过程：

   • 对左侧子数组 [12, 10, 6]：

     • 随机选择基准元素，假设选择的是 10。
     • 分解数组，将小于 10 的放在左边，大于 10 的放在右边：
       • 左侧子数组：[6]
       • 右侧子数组：[12]
     • 继续递归排序左右子数组。

   • 对左侧子数组 [21, 16, 34, 34]：

     • 随机选择基准元素，假设选择的是 21。
     • 分解数组，将小于 21 的放在左边，大于 21 的放在右边：
       • 左侧子数组：[16]
       • 右侧子数组：[34, 34]
     • 继续递归排序左右子数组。

7. 递归结束：

   • 所有的子数组都被分解成单个元素，递归排序结束。

8. 合并：

   • 由于快速排序是原地排序，不需要显式合并步骤。

最终，数组经过随机快速排序后的顺序为 [6, 10, 12, 14, 16, 21, 34, 34, 39, 42]。

随机快速排序的代码示例：

import java.util.Arrays;
import java.util.Random;

public class RandomQuickSort {

    public static void randomQuickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 随机选择基准元素
            int pivotIndex = randomPartition(arr, low, high);
            // 递归排序左侧子数组
            randomQuickSort(arr, low, pivotIndex - 1);
            // 递归排序右侧子数组
            randomQuickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int randomPartition(int[] arr, int low, int high) {
        // 生成 low 和 high 之间的随机索引作为基准元素索引
        Random random = new Random();
        int randomIndex = random.nextInt(high - low + 1) + low;
        // 将基准元素交换到数组末尾
        swap(arr, randomIndex, high);

        return partition(arr, low, high);
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确的位置
        swap(arr, i + 1, high);
        return i + 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {21, 12, 39, 14, 16, 10, 42, 6, 34, 34};
        randomQuickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

例题：数的划分

题目描述：

将整数 n 分成 k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5； 1，5，1； 5，1，1

问有多少种不同的分法。

示例 ：

输入

7 3
1

输出

4
1

题解：

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        System.out.println(partition(n, k));
    }

    public static int partition(int n, int k) {
        if (n == 0 || k == 0 || n < k) {
            return 0;
        }
        if (k == 1 || n == k){
            return 1;
        } else {
            return partition(n - k, k) + partition(n - 1, k-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

递归过程

当我们调用 partition(7, 3) 时，我们希望计算将整数 7 分成 3 份的不同分法数量。下面是递归过程的详细解释：

1. 第一次调用： partition(7, 3)

   进入 partition 方法，我们检查条件，n = 7 不等于 0，k = 3 不等于 0，因此继续执行。

   不满足 k == 1 或 n == k，所以我们进入 else 分支。

   我们计算 partition(7 - 3, 3) + partition(7 - 1, 3 - 1)。

2. 第一次递归调用： partition(4, 3)

   进入 partition 方法，同样检查条件，n = 4 不等于 0，k = 3 不等于 0，因此继续执行。

   不满足 k == 1 或 n == k，所以我们进入 else 分支。

   我们计算 partition(4 - 3, 3) + partition(4 - 1, 3 - 1)。

3. 第二次递归调用： partition(1, 3)

   进入 partition 方法，检查条件，n = 1 不等于 0，k = 3 不等于 0，因此继续执行。

   不满足 k == 1 或 n == k，所以我们进入 else 分支。

   我们计算 partition(1 - 3, 3) + partition(1 - 1, 3 - 1)。

   注意到 n - k 为负数，所以第一个递归调用返回 0。

   第二个递归调用变成了 partition(0, 2)。

4. 第三次递归调用： partition(0, 2)

   进入 partition 方法，检查条件，n = 0 等于 0，k = 2 不等于 0，因此继续执行。

   因为 k == 1，所以返回 1。

5. 回到第二次递归调用，partition(1 - 1, 3 - 1) 也返回 1。

6. 返回到第一次递归调用，partition(4 - 1, 3 - 1) 为 partition(3, 2)，进入下一轮递归。

7. 第四次递归调用： partition(3, 2)

   进入 partition 方法，检查条件，n = 3 不等于 0，k = 2 不等于 0，因此继续执行。

   不满足 k == 1 或 n == k，所以我们进入 else 分支。

   我们计算 partition(3 - 2, 2) + partition(3 - 1, 2 - 1)。

8. 第五次递归调用： partition(1, 2)

   进入 partition 方法，检查条件，n = 1 不等于 0，k = 2 不等于 0，因此继续执行。

   不满足 k == 1 或 n == k，所以我们进入 else 分支。

   我们计算 partition(1 - 2, 2) + partition(1 - 1, 2 - 1)。

   注意到 n - k 为负数，所以第一个递归调用返回 0。

   第二个递归调用变成了 partition(0, 1)。

9. 第六次递归调用： partition(0, 1)

   进入 partition 方法，检查条件，n = 0 等于 0，k = 1 等于 1，因此返回 1。

10. 返回到第五次递归调用，partition(1 - 1, 2 - 1) 也返回 1。

11. 返回到第四次递归调用，partition(3 - 1, 2 - 1) 为 partition(2, 1)，进入下一轮递归。

12. 第七次递归调用： partition(2, 1)

进入 partition 方法，检查条件，n = 2 不等于 0，k = 1 等于 1，因此返回 1。

13. 返回到第四次递归调用，partition(2, 1) 为 partition(2, 1) 的结果加上 partition(1, 1) 的结果，所以返回 2。

14. 返回到第一次递归调用，partition(4 - 3, 3) 为 partition(1, 3) 的结果加上 partition(3, 2) 的结果，所以返回 3。

15. 返回到初始调用，partition(7, 3) 为 partition(4, 3) 的结果加上 partition(6, 2) 的结果，所以返回 4。

最终，我们得到了将整数 7 分成 3 份的不同分法数量为 4。

分治的核心思路

划分数字的两种分法

• k份里面包含1的分法，首先就给分配 1 ，然后就剩下n-1个数分成 k -1 份

• k份里面不包含1的分法，在每一个位置上都先分配 1 ，相当于把 n-k 个数分成 k 份之后再在每个位置上加上1