【算法】王晓东期末考题总结（一）

---

分治

实现思路可参考：【算法】分治算法
之前写的Java版有思路。

1. 二分搜索

#include <iostream>
#include <vector>

using namespace std;

// 二分搜索函数
int binarySearch(const vector<int>& array, int target) {
    int left = 0;
    int right = array.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果找到目标元素，返回其索引
        if (array[mid] == target) {
            return mid;
        }

        // 如果目标元素在数组的左半部分，缩小搜索范围到左半部分
        if (array[mid] > target) {
            right = mid - 1;
        }
        // 如果目标元素在数组的右半部分，缩小搜索范围到右半部分
        else {
            left = mid + 1;
        }
    }

    // 如果数组中没有找到目标元素，返回-1表示未找到
    return -1;
}

int main() {
    vector<int> array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 6;

    // 调用二分搜索函数
    int result = binarySearch(array, target);

    // 输出结果
    if (result != -1) {
        cout << "元素 " << target << " 在数组中的索引为 " << result << endl;
    } else {
        cout << "未找到元素 " << target << endl;
    }

    return 0;
}

2. 合并排序

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& array, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组存储左右两个子数组
    vector<int> leftArray(n1);
    vector<int> rightArray(n2);

    // 复制数据到临时数组 leftArray 和 rightArray
    for (int i = 0; i < n1; i++) {
        leftArray[i] = array[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArray[j] = array[mid + 1 + j];
    }

    // 合并左右子数组
    int i = 0; // 初始化左子数组的索引
    int j = 0; // 初始化右子数组的索引
    int k = left; // 初始化合并后的数组的索引

    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            array[k] = leftArray[i];
            i++;
        } else {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }

    // 将左子数组的剩余部分复制到合并后的数组
    while (i < n1) {
        array[k] = leftArray[i];
        i++;
        k++;
    }

    // 将右子数组的剩余部分复制到合并后的数组
    while (j < n2) {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(vector<int>& array, int left, int right) {
    if (left < right) {
        // 找到数组的中间位置
        int mid = left + (right - left) / 2;

        // 递归地对左右两部分进行排序
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);

        // 合并已排序的两部分
        merge(array, left, mid, right);
    }
}

int main() {
    vector<int> array = {12, 11, 13, 5, 6, 7};

    cout << "原始数组: ";
    for (int num : array) {
        cout << num << " ";
    }
    cout << endl;

    // 调用归并排序函数
    mergeSort(array, 0, array.size() - 1);

    cout << "排序后的数组: ";
    for (int num : array) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

3. 快速排序

#include <iostream>
#include <vector>

using namespace std;

// 交换数组中两个元素的位置
void swap(vector<int>& array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

// 根据选定的基准元素将数组划分为两部分，并返回基准元素的索引
int partition(vector<int>& array, int low, int high) {
    // 选择最右侧元素作为基准
    int pivot = array[high];
    int i = low - 1;  // i是小于等于基准元素的子数组的最后一个元素的索引

    // 遍历数组，将小于等于基准元素的元素放在左侧，大于基准元素的元素放在右侧
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(array, i, j);
        }
    }

    // 将基准元素放在正确的位置
    swap(array, i + 1, high);

    return i + 1;
}

// 快速排序的递归函数
void quickSort(vector<int>& array, int low, int high) {
    if (low < high) {
        // 划分数组，获取基准元素的索引
        int pivotIndex = partition(array, low, high);

        // 递归排序左侧子数组
        quickSort(array, low, pivotIndex - 1);
        // 递归排序右侧子数组
        quickSort(array, pivotIndex + 1, high);
    }
}


int main() {
    vector<int> array = {12, 4, 5, 6, 7, 3, 1, 15};

    cout << "Original array: ";
    for (int num : array) {
        cout << num << " ";
    }

    // 调用快速排序算法
    quickSort(array, 0, array.size() -1);

    cout << "\nSorted array: ";
    for (int num : array) {
        cout << num << " ";
    }

    return 0;
}

4. 最接近点对问题

最接近点对问题是一个经典的计算几何问题，目标是找到平面上一组点中距离最近的两个点。分治算法是解决这个问题的一种有效方法。下面是最接近点对问题的分治算法实现思路：

• 按照 x 坐标将点集排序：
  将点集按照 x 坐标的顺序进行排序。这可以通过常见的排序算法（如快速排序）实现。
• 分治：
  将排序后的点集平均分成两部分，分别递归求解左右两部分的最接近点对。
• 查找跨越中间的最接近点对：
  在左右两部分的边界附近，找到距离中间线最近的两个点。这一步的时间复杂度是线性的。
• 合并：
  比较左右两部分的最接近点对，选择其中的最小值作为候选。
• 找到最终的最接近点对：
  在之前的步骤中，我们找到了两个候选点对，分别来自左右两部分。最终的最接近点对要么在其中一个部分，要么跨越两个部分。
• 计算最终的最接近点对：
  在考虑跨越边界的情况时，需要检查距离边界线距离小于当前最小距离的点。如果找到更小的距离，更新最小距离。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

struct Point {
    double x, y;
};

// 按照 x 坐标升序排序
bool compareX(const Point& a, const Point& b) {
    return a.x < b.x;
}

// 按照 y 坐标升序排序
bool compareY(const Point& a, const Point& b) {
    return a.y < b.y;
}

// 计算两点之间的距离
double distance(const Point& a, const Point& b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

// 暴力解法，计算所有点对之间的距离，找到最小值
pair<Point, Point> bruteForceClosestPair(const vector<Point>& points, int left, int right) {
    double minDist = numeric_limits<double>::max();
    pair<Point, Point> closestPair;

    for (int i = left; i <= right; ++i) {
        for (int j = i + 1; j <= right; ++j) {
            double dist = distance(points[i], points[j]);
            if (dist < minDist) {
                minDist = dist;
                closestPair = {points[i], points[j]};
            }
        }
    }

    return closestPair;
}

// 在给定的点集中找到最接近的点对
pair<Point, Point> closestPairUtil(const vector<Point>& points, int left, int right) {
    if (right - left <= 3) {
        // 对于小规模问题，使用暴力解法
        return bruteForceClosestPair(points, left, right);
    }

    int mid = (left + right) / 2;

    // 分别递归求解左右两边的最近点对
    pair<Point, Point> leftClosest = closestPairUtil(points, left, mid);
    pair<Point, Point> rightClosest = closestPairUtil(points, mid + 1, right);

    // 取左右两边的最近点对中的最小距离
    double minDist = min(distance(leftClosest.first, leftClosest.second),
                         distance(rightClosest.first, rightClosest.second));

    // 在距离中间线小于minDist的点集中查找可能更小的距离
    vector<Point> strip;
    for (int i = left; i <= right; ++i) {
        if (abs(points[i].x - points[mid].x) < minDist) {
            strip.push_back(points[i]);
        }
    }

    // 按照 y 坐标升序排序 strip
    sort(strip.begin(), strip.end(), compareY);

    // 在 strip 中查找可能更小的距离
    for (int i = 0; i < strip.size(); ++i) {
        for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist; ++j) {
            double dist = distance(strip[i], strip[j]);
            if (dist < minDist) {
                minDist = dist;
                leftClosest = {strip[i], strip[j]};
            }
        }
    }

    // 返回最终的最近点对
    return leftClosest;
}

// 最接近点对算法的入口函数
pair<Point, Point> closestPair(const vector<Point>& points) {
    // 按照 x 坐标升序排序点集
    vector<Point> sortedPoints = points;
    sort(sortedPoints.begin(), sortedPoints.end(), compareX);

    return closestPairUtil(sortedPoints, 0, sortedPoints.size() - 1);
}

int main() {
    vector<Point> points = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {5, 5}, {7, 7}, {8, 8}};

    // 调用最接近点对算法
    pair<Point, Point> closestPairPoints = closestPair(points);

    // 输出结果
    cout << "最接近点对: (" << closestPairPoints.first.x << ", " << closestPairPoints.first.y << ") and ("
         << closestPairPoints.second.x << ", " << closestPairPoints.second.y << ")" << endl;

    return 0;
}

---

动态规划

实现思路可参考：【算法】动态规划（Dynamic Programming）

1. 矩阵连乘

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// 定义矩阵结构体
struct Matrix {
    int rows, cols;
};

// 动态规划解决矩阵连乘问题
int matrixChainOrder(const vector<Matrix>& matrices) {
    int n = matrices.size();

    // 创建二维数组存储最小计算代价
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 计算最小计算代价
    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = numeric_limits<int>::max();
            for (int k = i; k <= j - 1; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + matrices[i - 1].rows * matrices[k].cols * matrices[j].cols;
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                }
            }
        }
    }

    // 返回最终的最小计算代价
    return dp[1][n - 1];
}

int main() {
    // 定义一系列矩阵
    vector<Matrix> matrices = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20}, {20, 25}};

    // 调用矩阵连乘问题算法
    int minCost = matrixChainOrder(matrices);

    // 输出结果 12250
    cout << "最小计算代价为: " << minCost << endl;

    return 0;
}

2. 流水作业调度

流水作业调度问题（Flow Shop Scheduling Problem）是一个经典的调度问题，通常涉及到多个作业（jobs）需要在多台机器上执行。每个作业都有一系列的任务（tasks），并且每个任务需要在不同的机器上执行。流水作业调度的目标是找到一个调度方案，使得完成所有作业的时间最短。

以下是流水作业调度问题的动态规划实现思路：

• 问题建模：
  将流水作业调度问题建模成一个二维数组，其中数组的行表示机器，数组的列表示任务。每个元素表示相应机器上执行相应任务所需的时间。
• 状态定义：
  定义动态规划状态。在这里，状态可以表示为 dp[i][j]，其中 i 表示机器的编号，j 表示任务的编号。dp[i][j] 表示前 j 个任务在前 i 台机器上的最短完成时间。
• 状态转移方程：
  根据问题的性质，确定状态转移方程。通常，状态转移方程可以定义为：

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + processingTime[i][j]

其中 processingTime[i][j] 表示第i台机器上执行第j个任务所需的时间。

• 初始化：
  初始化第一行和第一列。第一行表示第一台机器上的任务完成时间，第一列表示每个任务在第一台机器上的完成时间。
• 动态规划求解：
  通过填表的方式，逐步计算出所有的状态值，直至完成所有任务。
• 最优解提取：
  根据最终的状态表，提取出最短完成时间，并可以根据需要追踪得到具体的调度方案。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 动态规划求解流水作业调度问题
int flowShopScheduling(const vector<vector<int>>& processingTime) {
    int machines = processingTime.size();
    int jobs = processingTime[0].size();

    // dp[i][j] 表示前 i 台机器和前 j 个作业的最短完成时间
    vector<vector<int>> dp(machines + 1, vector<int>(jobs + 1, 0));

    // 初始化第一行和第一列
    for (int i = 1; i <= machines; ++i) {
        dp[i][1] = dp[i - 1][1] + processingTime[i - 1][0];
    }

    for (int j = 1; j <= jobs; ++j) {
        dp[1][j] = dp[1][j - 1] + processingTime[0][j - 1];
    }

    // 动态规划递推
    for (int i = 2; i <= machines; ++i) {
        for (int j = 2; j <= jobs; ++j) {
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + processingTime[i - 1][j - 1];
        }
    }

    // 返回最短完成时间
    return dp[machines][jobs];
}

int main() {
    // 示例：3台机器，4个作业的处理时间
    vector<vector<int>> processingTime = {
        {2, 5, 8, 7},
        {3, 2, 4, 6},
        {8, 3, 6, 1}
    };

    // 求解最短完成时间
    int shortestTime = flowShopScheduling(processingTime);

    // 输出结果
    cout << "最短完成时间为: " << shortestTime << endl;

    return 0;
}

processingTime 表示每台机器上每个作业的处理时间。flowShopScheduling 函数使用动态规划来计算最短完成时间。在动态规划的递推过程中，通过比较上一步的状态，选择最优的方式来更新状态。最终，dp[machines][tasks] 即为问题的最优解，即最短完成时间。

3. 背包问题

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 物品结构体
struct Item {
    int weight; // 物品重量
    int value;  // 物品价值
};

// 动态规划解决0/1背包问题
int knapsack(const vector<Item>& items, int capacity) {
    int numItems = items.size();

    // 创建二维数组存储最大价值
    vector<vector<int>> dp(numItems + 1, vector<int>(capacity + 1, 0));

    // 填充动态规划表
    for (int i = 1; i <= numItems; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (items[i - 1].weight <= w) {
                // 当前物品可以放入背包
                dp[i][w] = max(dp[i - 1][w], items[i - 1].value + dp[i - 1][w - items[i - 1].weight]);
            } else {
                // 当前物品不能放入背包
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 返回最终的最大价值
    return dp[numItems][capacity];
}

int main() {
    // 定义一组物品
    vector<Item> items = {{2, 3}, {3, 4}, {4, 5}, {5, 6}};

    // 背包容量
    int capacity = 8;

    // 调用0/1背包问题算法
    int maxValue = knapsack(items, capacity);

    // 输出结果
    cout << "背包中物品的最大总价值为: " << maxValue << endl;

    return 0;
}

---

贪心算法

实现思路可参考：【算法】贪心算法

1. 最优装载问题（首次适用）

#include <iostream>
#include <vector>

using namespace std;

// 最优装载问题的首次适应算法
int firstFit(const vector<int>& items, int binCapacity) {
    int numBins = 0;
    vector<int> binSpace; // 每个容器的剩余空间

    for (int item : items) {
        bool binFound = false;

        // 在现有的容器中找到第一个可以装下当前物品的容器
        for (int i = 0; i < numBins; i++) {
            if (binSpace[i] >= item) {
                binSpace[i] -= item;
                binFound = true;
                break;
            }
        }

        // 如果没有找到合适的容器，则开启一个新的容器
        if (!binFound) {
            binSpace.push_back(binCapacity - item);
            numBins++;
        }
    }

    return numBins;
}

int main() {
    // 定义一组物品
    vector<int> items = {4, 8, 1, 4, 2, 1, 8, 5};

    // 容器的容量
    int binCapacity = 10;

    // 调用首次适应算法解决最优装载问题
    int numBins = firstFit(items, binCapacity);

    // 输出结果 4
    cout << "最优装载问题的最小容器数量（首次适应算法）为: " << numBins << endl;

    return 0;
}

2. 单源最短路径

贪心算法解决单源最短路径问题的经典算法是Dijkstra算法。Dijkstra算法通过贪心策略逐步确定从源节点到各个其他节点的最短路径，具体实现思路如下：

• 初始化：
  将源节点到自身的距离设为0，将源节点到其他所有节点的距离设为无穷大（或一个较大的数）。
• 选择最短路径节点：
  从未确定最短路径的节点中选择一个节点，该节点到源节点的距离最短。一开始选择源节点。
• 更新距离：
  对于选定的节点，更新它的邻居节点到源节点的距离。如果通过选定节点到某个邻居节点的路径比当前已知的最短路径更短，则更新邻居节点的距离。
• 标记节点：
  将选定的节点标记为已确定最短路径。
• 重复步骤2~4：
  重复步骤2~4，直到所有节点都被标记为已确定最短路径或者没有可选的节点。

#include <iostream>
#include <vector>
#include <set>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// 图的邻接矩阵表示
using Graph = vector<vector<int>>;

// Dijkstra算法实现
void dijkstra(const Graph& graph, int source, vector<int>& distances) {
    int n = graph.size();
    set<pair<int, int>> pq;  // 优先队列，用于选择当前距离最短的节点

    distances.resize(n, INF);
    distances[source] = 0;

    pq.insert({0, source});

    while (!pq.empty()) {
        int u = pq.begin()->second;
        pq.erase(pq.begin());

        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != INF && distances[u] + graph[u][v] < distances[v]) {
                // 更新距离
                pq.erase({distances[v], v});
                distances[v] = distances[u] + graph[u][v];
                pq.insert({distances[v], v});
            }
        }
    }
}

int main() {
    // 例子：有向图的邻接矩阵表示
    Graph graph = {
        {0, 1, 4, INF, INF},
        {INF, 0, 2, 5, INF},
        {INF, INF, 0, INF, 1},
        {INF, INF, INF, 0, 3},
        {INF, INF, INF, INF, 0}
    };

    int source = 0;  // 源节点
    vector<int> distances;  // 存储最短路径长度

    dijkstra(graph, source, distances);

    // 输出结果
    cout << "从节点 " << source << " 出发到各节点的最短路径长度：" << endl;
    for (int i = 0; i < distances.size(); ++i) {
        cout << "到节点 " << i << " 的最短路径长度为: " << distances[i] << endl;
    }

    return 0;
}

graph是一个有向图的邻接矩阵表示，source 是源节点的编号。dijkstra 函数实现了Dijkstra算法，其中使用了一个优先队列来选择当前距离最短的节点。最终，distances 向量存储了从源节点到各个节点的最短路径长度。
3. 最小生成树

贪心算法解决最小生成树问题的一个经典算法是Prim算法。Prim算法基于贪心策略，逐步构建最小生成树。以下是Prim算法的实现思路：

• 选择起始节点：
  从图中选择一个起始节点作为最小生成树的起点。
• 初始化集合：
  将起始节点加入一个集合，表示已经包含在最小生成树中的节点。
• 选择最短边：
  从已选择的节点集合中，选择一条连接到未选择节点的最短边。
• 将节点加入集合：
  将该边连接的未选择节点加入节点集合。
• 重复步骤3~4：
  重复步骤3和4，直到所有节点都包含在最小生成树中。

#include <iostream>
#include <vector>
#include <set>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// 图的邻接矩阵表示
using Graph = vector<vector<int>>;

// Prim算法实现
void prim(const Graph& graph, int start) {
    int n = graph.size();

    // 使用集合存储已选择的节点
    set<int> selectedNodes;

    // 初始化起始节点
    selectedNodes.insert(start);

    // 重复选择最短边，直到所有节点都被选择
    while (selectedNodes.size() < n) {
        int minWeight = INF;
        int minNode = -1;

        // 在已选择的节点集合中，找到一条连接到未选择节点的最短边
        for (int node : selectedNodes) {
            for (int neighbor = 0; neighbor < n; ++neighbor) {
                if (graph[node][neighbor] < minWeight && selectedNodes.find(neighbor) == selectedNodes.end()) {
                    minWeight = graph[node][neighbor];
                    minNode = neighbor;
                }
            }
        }

        // 输出最短边的信息
        cout << "Edge: (" << minNode << ", " << minWeight << ")" << endl;

        // 将连接的未选择节点加入集合
        selectedNodes.insert(minNode);
    }
}

int main() {
    // 例子：无向图的邻接矩阵表示
    Graph graph = {
        {0, 2, INF, 6, INF},
        {2, 0, 3, 8, 5},
        {INF, 3, 0, INF, 7},
        {6, 8, INF, 0, 9},
        {INF, 5, 7, 9, 0}
    };

    int startNode = 0;  // 起始节点

    cout << "最小生成树的边：" << endl;
    prim(graph, startNode);

    return 0;
}

graph 是一个无向图的邻接矩阵表示，startNode 是起始节点的编号。prim 函数实现了Prim算法，它使用一个集合 selectedNodes 来存储已选择的节点。算法通过在已选择的节点中找到一条连接到未选择节点的最短边，将未选择节点加入集合，并输出最短边的信息。最终，算法输出了构建最小生成树的边。

---