## 一、实验名称

递归与分治

## 二、实验目的及要求

利用C/C++/Java等程序设计语言，实现本章节中分治算法、递归，汉诺塔问题/二分搜索算法/合并排序/快速排序等经典算法。通过本实验章节掌握递归、分治算法的设计思想及实现技巧，加深对课程知识的理解。

## 三、实验环境

ubuntu-24.04 x86_64 5.14.0-503.11.1.el9_5.x86_64

gcc version 11.4.0 (Ubuntu 11.4.0-9ubuntu1) 

## 四、实验设计

### 1. 整数划分

#### 1.1 实验步骤

##### 程序设计框图

```mermaid
graph TD
    A[开始] --> B{n == 0?};
    B -- 是 --> C[返回 1];
    B -- 否 --> D{n < 0 或 m <= 0?};
    D -- 是 --> E[返回 0];
    D -- 否 --> F["integerPartition(n, m - 1)"];
    D -- 否 --> G["integerPartition(n - m, m)"];
    F --> H[+] --> I[返回 结果];
    G --> H;
    C --> I;
    E --> I;
```



##### 设计思想：

**递归分解**问题：将整数 `n` 的划分视为使用若干个**不大于 `m`** 的整数相加得到 `n` 的过程。通过**选择是否使用当前最大允许数 `m`**，将问题分解为规模更小的子问题，并累积方案数。



##### 实现步骤：

1. **递归函数 `partition(n, m)`:** 计算 `n` 的使用不超过 `m` 的整数划分数。
2. 递归出口：
   * `n == 0`: 找到一种划分，返回 1。
   * `n < 0` 或 `m <= 0`: 无法有效划分，返回 0。
3. 递归调用：
   * **不使用 `m`:** `partition(n, m - 1)`
   * **使用 `m`:** `partition(n - m, m)`
4. **合并结果：** 返回 `partition(n, m - 1) + partition(n - m, m)`。
5. **主函数：** 调用 `partition(n, n)` 获取结果。



#### 1.2 调试过程及实验结果

```zsh
❯ g++ integerPartition.cpp
❯ ./a.out
请输入一个正整数 n: 3
整数划分方式数为: 3
❯ ./a.out
请输入一个正整数 n: 6
整数划分方式数为: 11
❯ ./a.out
请输入一个正整数 n: 81
整数划分方式数为: 18004327
❯ ./a.out
请输入一个正整数 n: 1
整数划分方式数为: 1
```



### 2. 汉诺塔

#### 2.1 实验步骤

##### 程序设计框图

```mermaid
graph TD
    A[开始] --> B{n == 1?};
    B -- 是 --> C["输出: 移动盘子 n 从 from 到 to"];
    C --> D[返回];
    B -- 否 --> E["hanoi(n - 1, from, mid, to)"];
    E --> F["输出: 移动盘子 n 从 from 到 to"];
    F --> G["hanoi(n - 1, mid, to, from)"];
    G --> D;
```

##### 设计思想：

将 `n` 个盘子从 `A` 移动到 `C` 的问题分解为三个步骤：

1. 将 `n-1` 个盘子从 `A` 移动到**辅助柱 `B`**。
2. 将**最大的第 `n` 个盘子**从 `A` 移动到目标柱 `C`。
3. 将 `n-1` 个盘子从辅助柱 `B` 移动到目标柱 `C`。

通过**递归**地解决步骤 1 和 3，逐步缩小问题规模，直到只剩一个盘子可以直接移动。

##### 实现步骤：

1. **递归函数 `hanoi(n, from, to, mid)`:**
   * `n`: 盘子数量。
   * `from`: 起始柱。
   * `to`: 目标柱。
   * `mid`: 辅助柱。
2. **递归出口：**
   * `n == 1`: 直接将盘子从 `from` 移动到 `to` 并输出。
3. **递归调用：**
   * `hanoi(n - 1, from, mid, to)`: 将 `n-1` 个盘子从 `from` 移动到 `mid`（此时 `to` 是辅助）。
   * 输出移动第 `n` 个盘子的操作：`cout << "移动盘子 " << n << " 从 " << from << " 到 " << to << endl;`
   * `hanoi(n - 1, mid, to, from)`: 将 `n-1` 个盘子从 `mid` 移动到 `to`（此时 `from` 是辅助）。
4. **主函数：** 调用 `hanoi(num, 'A', 'C', 'B')` 启动汉诺塔移动。



#### 2.2 调试过程及实验结果

```zsh
❯ g++ hanoi.cpp
❯ ./a.out
请输入盘子数量：3
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
❯ ./a.out
请输入盘子数量：5
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
移动盘子 4 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 2 从 C 到 A
移动盘子 1 从 B 到 A
移动盘子 3 从 C 到 B
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 5 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
移动盘子 3 从 B 到 A
移动盘子 1 从 C 到 B
移动盘子 2 从 C 到 A
移动盘子 1 从 B 到 A
移动盘子 4 从 B 到 C
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C
```



### 3. 快速排序

#### 3.1 实验步骤

##### 程序设计框图

```mermaid
graph TD
    D{low < high?};
    D -- 否 --> E[返回];
    D -- 是 --> F["选择基准元素"];
    F --> G["分区操作: 将小于基准的放左边, 大于基准的放右边"];
    G --> H["获取基准元素最终索引 idx"];
    H --> I["quickSort(数组, low, idx - 1)"];
    H --> J["quickSort(数组, idx + 1, high)"];
    I --> E;
    J --> E;
```



##### 设计思想：

**分而治之**。选取一个**基准元素 (pivot)**，通过**分区 (partition)** 操作将数组划分为两个子数组：左边子数组的所有元素都小于或等于基准，右边子数组的所有元素都大于或等于基准。然后**递归地**对左右两个子数组进行快速排序。

##### 实现步骤：

1. **递归函数 `quickSort(arr, low, high)`:** 对数组 `arr` 的 `[low, high]` 范围进行排序。
2. **递归出口：** `low >= high` 时，子数组只有一个或没有元素，无需排序，返回。
3. 分区操作 `partition(arr, low, high)`：
   * 选取一个基准元素（通常是第一个元素）。
   * 重新排列数组，使得基准元素左边的元素都小于等于它，右边的元素都大于等于它。
   * 返回基准元素最终所在的索引。
4. 递归调用：
   * 对基准元素左边的子数组进行快速排序：`quickSort(arr, low, pivot_index - 1)`。
   * 对基准元素右边的子数组进行快速排序：`quickSort(arr, pivot_index + 1, high)`。
5. **主函数：** 调用 `quickSort(arr, 0, arr.size() - 1)` 启动排序。

#### 3.2 调试过程及实验结果

```zsh
❯ g++ quickSort.cpp
❯ ./a.out
请输入一组整数, 以空格分隔, 输入回车结束: 
9 2 4 8 1
原数组为: 
9 2 4 8 1 
使用快速排序后的数组为: 
1 2 4 8 9 
❯ ./a.out
请输入一组整数, 以空格分隔, 输入回车结束: 
0 23452 23 12 8 0 114514 1919810
原数组为: 
0 23452 23 12 8 0 114514 1919810 
使用快速排序后的数组为: 
0 0 8 12 23 23452 114514 1919810
```

### 4. 归并排序

#### 4.1 实验步骤

##### 程序设计框图

```mermaid
graph TD 
    D{数组长度 <= 1?};
    D -- 是 --> E[返回 数组];
    D -- 否 --> F["分割数组为 左半部分 和 右半部分"];
    F --> G["左半部分 = mergeSort(左半部分)"];
    F --> H["右半部分 = mergeSort(右半部分)"];
    G --> I["合并 有序的 左半部分 和 右半部分"];
    H --> I;
    I --> E;
```



##### 设计思想：

**分而治之**。将待排序数组**递归地分割**成两个子数组，直到每个子数组只包含一个元素（此时认为是有序的）。然后将两个**有序的子数组**逐步**合并**成一个更大的有序数组，直到整个数组有序。

##### 实现步骤：

1. **递归函数 `mergeSort(arr, left, right)`:** 对数组 `arr` 的 `[left, right]` 范围进行排序。
2. **递归出口：** `left >= right` 时，子数组只有一个或没有元素，无需排序，返回。
3. **分割：** 计算中间索引 `mid = (left + right) / 2`，将数组划分为 `[left, mid]` 和 `[mid + 1, right]` 两个子数组。
4. **递归排序：** 分别对左右两个子数组进行归并排序：`mergeSort(arr, left, mid)` 和 `mergeSort(arr, mid + 1, right)`。
5. **合并 `merge(arr, left, mid, right)`：** 将两个已排序的子数组 `arr[left...mid]` 和 `arr[mid+1...right]` 合并成一个有序的子数组。这通常需要额外的临时空间来存放合并后的元素。
6. **主函数：** 调用 `mergeSort(arr, 0, arr.size() - 1)` 启动排序。



#### 4.2 调试过程及实验结果

```zsh
❯ g++ mergeSort.cpp
❯ ./a.out
请输入一组整数, 以空格分隔, 输入回车结束: 
2 9 1 0 7
原数组为: 2 9 1 0 7 
使用归并排序后的数组为: 0 1 2 7 9 
❯ ./a.out
请输入一组整数, 以空格分隔, 输入回车结束: 
1919818 4 0 1 0 114514
原数组为: 1919818 4 0 1 0 114514 
使用归并排序后的数组为: 0 0 1 4 114514 1919818 
```

### 5. 总结

**上机实践结果分析：**

* **整数划分：**
  * **结果：** 能够正确计算出给定正整数 `n` 的划分方案数。对于较小的 `n`，结果能够通过手动枚举验证。
  * **分析：** 递归调用的次数随着 `n` 的增大而迅速增加，可能导致栈溢出或效率问题。对于相同的 `n` 和不同的最大划分数 `m`，结果会相应变化。实验结果直观地展示了划分数随 `n` 增长的复杂性。
* **汉诺塔：**
  * **结果：** 能够按照汉诺塔的规则输出正确的盘子移动步骤，将所有盘子从起始柱移动到目标柱。
  * **分析：** 移动步数随着盘子数量 `n` 的增加呈指数级增长 $(2^n−1)$。当 `n` 较大时，输出的步骤会非常多。实验结果清晰地展示了递归算法在解决此类问题时的简洁性和步数的指数级增长。
* **快速排序：**
  * **结果：** 能够对输入的包含重复或无序整数的数组进行有效排序，得到一个升序（或降序，取决于实现）排列的数组。
  * **分析：** 实际运行时间受到基准元素选择的影响。在平均情况下，快速排序表现出良好的性能（$O(n log n)$）。但在最坏情况下（例如，已排序或逆序数组且总是选择第一个元素作为基准），时间复杂度会退化到 $O(n^2)$。实验结果可能展示了不同输入情况下排序所需时间的差异。
* **归并排序：**
  * **结果：** 能够稳定地对输入的包含重复或无序整数的数组进行排序，得到一个升序（或降序）排列的数组。
  * **分析：** 归并排序的时间复杂度始终为 $O(n log n)$，且排序过程稳定。实验结果可能显示出其在各种输入情况下相对一致的性能表现，但由于需要额外的合并空间，空间复杂度为 $O(n)$。

**上机的心得体会：**

1. **递归思想的重要性：** 这四个实验中，整数划分和汉诺塔都直接采用了递归思想。通过将复杂问题分解为更小的、相似的子问题，递归能够以简洁的代码实现复杂的逻辑。然而，需要注意递归深度可能带来的性能和栈溢出风险。
2. **分而治之的威力：** 快速排序和归并排序都体现了“分而治之”的思想。将大问题分解成小问题，解决小问题后再合并结果，能够有效地降低问题的复杂度，提高算法的效率（尤其体现在排序算法上）。
3. **算法选择与性能：** 通过快速排序和归并排序的实践，体会到不同的排序算法在不同场景下可能具有不同的性能表现。快速排序在平均情况下很快，但最坏情况性能较差；归并排序性能稳定，但需要额外的空间。在实际应用中，需要根据数据特性和资源限制选择合适的算法。
4. **理解算法原理是关键：** 仅仅编写出能够运行的代码是不够的，更重要的是理解算法背后的设计思想、时间复杂度和空间复杂度。这有助于我们更好地分析算法的优劣，并在遇到问题时进行调试和优化。

总而言之，这四个实验涵盖了重要的算法设计思想，如递归和分而治之。通过实践，不仅掌握了这些算法的实现，更重要的是理解了它们背后的原理、优缺点以及适用场景，为后续更深入地学习和应用算法打下了坚实的基础。

### 6. 附录

#### 整数划分

```cpp
#include <iostream>
using namespace std;

// 对于整数 n , 使用若干个不超过 m 的整数进行划分, 得到划分数
int integerPartition(int n, int m) {
    if (n == 0) return 1; // 递归出口, 完整地把原来的数字划分成了 0, 得到了一种划分方式, 所以返回1;
    if (n < 0 || m <= 0) return 0; // 如果 n < 0, 也就是无法用正整数完美划分, 就代表无法划分, 返回方案数0; 
                                   // 如果 m <= 0, 一个正整数无法被一个 <= 0 的数划分, 也返回方案数0;
    // 递归调用, 分为两种情况:
    // 1. 不使用 m 来划分, 那就接着往下, 尝试使用 m - 1 来划分 n;
    // 2. 使用 m 来划分, 划出去一个 m, 剩下 n - m, 继续尝试使用 m 来划分 n - m;
    return integerPartition(n, m - 1) + integerPartition(n - m, m);
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;
    cout << "整数划分方式数为: " << integerPartition(n, n) << endl;
    return 0;
}
```

#### 汉诺塔

```cpp
#include <iostream>
using namespace std;

void hanoi(int n, char from, char to, char mid) {
    if (n == 1) {
        // 递归出口, 如果之哟一个盘子, 那么就可以直接从 from 移动到 to
        cout << "移动盘子 " <<  n << " 从 " << from << " 到 " << to << endl;
        return;
    }

    // 1. 先将上面的 n - 1 个盘子从 from 移动到 mid
    hanoi(n - 1, from, mid, to);

    // 2. 将第 n 个盘子从 from 移动到 to
    cout << "移动盘子 " << n << " 从 " << from << " 到 " << to << endl;

    // 3. 将 n - 1 个盘子从 mid 移动到 to
    hanoi(n - 1, mid, to, from);
}

int main () {
    int num;
    cout << "请输入盘子数量：";
    cin >> num;
    hanoi(num, 'A', 'C', 'B'); // A -> C, B 是辅助柱子
    return 0;
}
```

#### 归并排序

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

void merge(vector<int> &arr, int left, int mid, int right) {
    // 两个临时数组的长度
    int len1 = mid - left + 1;
    int len2 = right - mid;

    // 创建两个临时数组
    vector<int> arr1(len1);
    vector<int> arr2(len2);

    // 将数据复制到临时数组中
    for (int i = 0; i < len1; i++) arr1[i] = arr[left + i];
    for (int i = 0; i < len2; i++) arr2[i] = arr[mid + 1 + i];

    // 归并两个临时数组
    int i = 0, j = 0, k = left;
    while (i < len1 && j < len2) {
        if (arr1[i] <= arr2[j]) arr[k++] = arr1[i++];
        else arr[k++] = arr2[j++];
    }

    // 将较长的临时数组中剩余的元素复制到原数组中
    while (i < len1) arr[k++] = arr1[i++];
    while (j < len2) arr[k++] = arr2[j++];
}

void mergeSort(vector<int> &arr, int left, int right) {
    // 递归出口
    // 如果left >= right 说明子数组中只有一个或没有元素, 可以看作有序
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right); // 合并两个有序子数组
}

int main() {
    vector<int> arr;
    string input;
    cout << "请输入一组整数, 以空格分隔, 输入回车结束: " << endl;
    getline(cin, input);
    
    istringstream iss(input);
    int num;
    while (iss >> num) arr.push_back(num);
    int len = arr.size();

    cout << "原数组为: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    mergeSort(arr, 0, len - 1);

    cout << "使用归并排序后的数组为: ";
    for (int i : arr) cout << i << " ";
    cout << endl;

    return 0;
}
```

#### 快速排序

```cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[low];       // 选取第一个元素作为基准
    int left = low + 1;            // 基准后面的一个元素为left
    int right = high;              // 最后一个元素为right

    while (left <= right) {
        // 从左向右找第一个小于等于基准的元素
        while (arr[left] <= pivot && left <= right) left++;

        // 从右向左找第一个大于等于基准的元素
        while (arr[right] >= pivot && left <= right) right--;

        // 如果left小于right，交换这两个元素
        if (left < right) swap(arr[left], arr[right]);
    }

    // 将基准元素放到正确的位置
    swap(arr[low], arr[right]);
    return right;  // 返回基准元素的索引
}

void quickSort(vector<int> &arr, int low, int high) {
    // 如果low小于high，说明数组中还有多个元素需要排序
    // 如果low >= high，说明数组中只有一个元素或者没有元素，不需要排序
    if (low < high) {
        int idx = partition(arr, low, high);  // 获取基准元素的索引
        quickSort(arr, low, idx - 1);        // 对基准元素左边的子数组进行快速排序
        quickSort(arr, idx + 1, high);       // 对基准元素右边的子数组进行快速排序
    }
}

int main() {
    vector<int> arr;
    string input;
    cout << "请输入一组整数, 以空格分隔, 输入回车结束: " << endl;
    getline(cin, input);

    istringstream iss(input);
    int num;
    while (iss >> num) arr.push_back(num);
    int len = arr.size();

    cout << "原数组为: " << endl;
    for (int i : arr) cout << i << " " ;
    cout << endl;

    quickSort(arr, 0, len - 1); 
    
    cout << "使用快速排序后的数组为: " << endl;
    for (int i : arr) cout << i << " " ;
    cout << endl;

    return 0;
}
```