ucenter使用自己做的网站,夫妻网站开发,山东大标网络,html网页设计基础文章目录 1. 概述2. 适用场景3. 设计步骤4. 优缺点5. 典型应用6. 题目和代码示例6.1 简单题目#xff1a;归并排序6.2 中等题目#xff1a;最近点对问题6.3 困难题目#xff1a;分数背包问题 7. 题目和思路表格8. 总结References 1000.01.CS.AL.1.4-核心-DivedeToConquerAlg… 文章目录 1. 概述2. 适用场景3. 设计步骤4. 优缺点5. 典型应用6. 题目和代码示例6.1 简单题目归并排序6.2 中等题目最近点对问题6.3 困难题目分数背包问题 7. 题目和思路表格8. 总结References 1000.01.CS.AL.1.4-核心-DivedeToConquerAlgorithm-Created: 2024-06-15.Saturday09:35 1. 概述
分治算法Divide and Conquer是一种重要的算法设计思想其核心思想是将一个复杂的问题分解为多个相对简单的小问题通过解决这些小问题再合并其结果从而得到原问题的解。分治算法的典型特征是递归常用于求解具有重复子问题性质的问题。
2. 适用场景
分治算法适用于以下场景
问题可以分解为若干个规模较小且相互独立的子问题。这些子问题的解可以合并得到原问题的解。具有最优子结构性质即子问题的最优解可以合成原问题的最优解。
3. 设计步骤
分解Divide将原问题分解为若干个子问题这些子问题的结构与原问题相同但规模较小。解决Conquer递归地解决这些子问题。当子问题的规模足够小时直接解决。合并Combine将子问题的解合并得到原问题的解。
4. 优缺点
优点分治算法的递归思想使其在解决许多复杂问题时表现出色。具有良好的可扩展性和并行计算的潜力。缺点对于某些问题分治算法可能会引入额外的开销如递归调用栈和合并步骤的时间复杂度。
5. 典型应用
归并排序Merge Sort一种高效的排序算法利用分治思想将数组分为两半递归地排序并合并。快速排序Quick Sort另一种高效的排序算法选择一个基准元素将数组分为两部分递归排序。最近点对问题Closest Pair Problem在平面上找到距离最近的两点分治法可以将时间复杂度降至 O(nlogn)O(n \log n)O(nlogn)。矩阵乘法Strassen’s Algorithm一种用于矩阵乘法的分治算法降低了时间复杂度。
6. 题目和代码示例
6.1 简单题目归并排序
题目描述实现归并排序算法对给定的数组进行排序。
代码示例
#include iostream
#include vector// 函数声明
void mergeSort(std::vectorint arr, int left, int right);
void merge(std::vectorint arr, int left, int mid, int right);int main() {std::vectorint arr {38, 27, 43, 3, 9, 82, 10};mergeSort(arr, 0, arr.size() - 1);for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}// 归并排序递归地将数组分成两半进行排序
void mergeSort(std::vectorint arr, int left, int right) {if (left right) {int mid left (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);merge(arr, left, mid, right);}
}// 合并两个已排序的子数组
void merge(std::vectorint arr, int left, int mid, int right) {int n1 mid - left 1;int n2 right - mid;std::vectorint L(n1), R(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];} else {arr[k] R[j];}k;}while (i n1) {arr[k] L[i];}while (j n2) {arr[k] R[j];}
}
Others.
def merge_sort(arr):if len(arr) 1:mid len(arr) // 2left_half arr[:mid]right_half arr[mid:]merge_sort(left_half)merge_sort(right_half)i j k 0while i len(left_half) and j len(right_half):if left_half[i] right_half[j]:arr[k] left_half[i]i 1else:arr[k] right_half[j]j 1k 1while i len(left_half):arr[k] left_half[i]i 1k 1while j len(right_half):arr[k] right_half[j]j 1k 1# 示例
arr [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr) # 输出: [3, 9, 10, 27, 38, 43, 82]6.2 中等题目最近点对问题
题目描述在平面上找到距离最近的两点时间复杂度为 O(nlogn)。
代码示例
#include iostream
#include vector
#include cmath
#include algorithmstruct Point {int x, y;
};double dist(const Point p1, const Point p2) {return std::sqrt((p1.x - p2.x) * (p1.x - p2.x) (p1.y - p2.y) * (p1.y - p2.y));
}double closestPair(std::vectorPoint points, int left, int right) {if (right - left 3) {double minDist std::numeric_limitsdouble::infinity();for (int i left; i right; i) {for (int j i 1; j right; j) {minDist std::min(minDist, dist(points[i], points[j]));}}return minDist;}int mid left (right - left) / 2;double d1 closestPair(points, left, mid);double d2 closestPair(points, mid 1, right);double d std::min(d1, d2);std::vectorPoint strip;for (int i left; i right; i) {if (std::abs(points[i].x - points[mid].x) d) {strip.push_back(points[i]);}}std::sort(strip.begin(), strip.end(), [](const Point p1, const Point p2) {return p1.y p2.y;});double minDist d;for (size_t i 0; i strip.size(); i) {for (size_t j i 1; j strip.size() (strip[j].y - strip[i].y) minDist; j) {minDist std::min(minDist, dist(strip[i], strip[j]));}}return minDist;
}int main() {std::vectorPoint points {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};std::sort(points.begin(), points.end(), [](const Point p1, const Point p2) {return p1.x p2.x;});std::cout 最近点对距离: closestPair(points, 0, points.size() - 1) std::endl;return 0;
}Others.
import mathdef dist(p1, p2):return math.sqrt((p1[0] - p2[0]) ** 2 (p1[1] - p2[1]) ** 2)def closest_pair(points):def closest_pair_recursive(points):if len(points) 3:return min((dist(p1, p2), (p1, p2)) for i, p1 in enumerate(points) for p2 in points[i1:])[1]mid len(points) // 2left_half points[:mid]right_half points[mid:](d1, pair1) closest_pair_recursive(left_half)(d2, pair2) closest_pair_recursive(right_half)d min(d1, d2)pair pair1 if d1 d2 else pair2strip [p for p in points if abs(p[0] - points[mid][0]) d]strip.sort(keylambda p: p[1])for i in range(len(strip)):for j in range(i1, len(strip)):if strip[j][1] - strip[i][1] d:breakd_new dist(strip[i], strip[j])if d_new d:d d_newpair (strip[i], strip[j])return d, pairpoints.sort(keylambda p: p[0])return closest_pair_recursive(points)[1]# 示例
points [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(points)) # 输出: ((2, 3), (3, 4))6.3 困难题目分数背包问题
题目描述给定物品的重量和价值求在背包容量限制下的最大价值物品可以分割。
代码示例
#include iostream
#include vector
#include algorithmstruct Item {double value;double weight;
};double fractionalKnapsack(std::vectorItem items, double capacity) {std::sort(items.begin(), items.end(), [](const Item a, const Item b) {return (a.value / a.weight) (b.value / b.weight);});double totalValue 0;for (const auto item : items) {if (capacity item.weight) {capacity - item.weight;totalValue item.value;} else {totalValue item.value * (capacity / item.weight);break;}}return totalValue;
}int main() {std::vectorItem items {{60, 10}, {100, 20}, {120, 30}};double capacity 50;std::cout 背包的最大价值: fractionalKnapsack(items, capacity) std::endl;return 0;
}Others.
def fractional_knapsack(values, weights, capacity):items list(zip(values, weights))items.sort(keylambda x: x[0] / x[1], reverseTrue)total_value 0for value, weight in items:if capacity weight:capacity - weighttotal_value valueelse:total_value value * (capacity / weight)breakreturn total_value# 示例
values [60, 100, 120]
weights [10, 20, 30]
capacity 50
print(fractional_knapsack(values, weights, capacity)) # 输出: 240.07. 题目和思路表格
序号题目题目描述分治策略代码实现1归并排序对给定的数组进行排序递归地将数组分成两半进行排序代码2最近点对问题找到距离最近的两点将点集合递归地分成两半代码3分数背包问题求在背包容量限制下的最大价值每次选择单位重量价值最高的物品代码4快速排序高效排序算法选择一个基准元素将数组分为两部分递归排序代码5矩阵乘法用于矩阵乘法将矩阵分成更小的子矩阵递归计算-6求逆序对数量统计数组中的逆序对个数使用分治法将数组分成两半递归统计逆序对-7最大子序和找出最大和的连续子序列将序列递归地分成两半合并子序列的结果-8大整数乘法实现高效的大整数乘法使用Karatsuba算法将大整数分成两部分进行递归计算-9二维平面上的最近点对在平面上找到距离最近的两点将点集合递归地分成两半合并结果-10棋盘覆盖问题用L型骨牌覆盖2^n * 2^n的棋盘将棋盘递归地分成四部分覆盖部分棋盘-
8. 总结
分治算法是一种强大的算法设计思想能够高效地解决许多复杂的问题。通过将问题分解为更小的子问题分治算法不仅能够降低时间复杂度还具有良好的可扩展性。在实际应用中理解和掌握分治算法的思想和典型应用对于解决各种问题具有重要意义。通过本文的例子和思路相信读者能够深入理解分治算法的关键概念并灵活应用于实际问题中。
References
