赞
踩
目录
分治算法(Divide and Conquer)是一种解决问题的算法设计策略,它将一个大问题分解成若干个规模较小且相互独立的子问题,然后将这些子问题的解合并起来,从而得到原问题的解。
分治算法通常包括以下三个步骤:
分治算法的典型应用包括排序算法(如快速排序、归并排序)、搜索算法(如二分查找)、数学问题(如大整数乘法)等。
输入:⼀个已排序数组 a[1...n](元素各不相同),⼀个元素 x输出:如果 x = a[j],返回 j,否则返回 -1
分治测略:
- #include <iostream>
- #include <vector>
- using namespace std;
-
- //分治递归函数,复杂度为O(logn)
- int binary_search(const vector<int>& a, int x, int low, int high)
- {
- if (low > high) return -1;
- int mid = (low + high) / 2;
- if (a[mid] == x) return mid;
- if (a[mid] > x)
- return binary_search(a, x, low, mid - 1);
- else
- return binary_search(a, x, mid + 1, high);
- }
-
- int main() {
- vector<int> arr = {3, 8, 1, 6, 2, 5, 9, 4, 7};
- int x = 8;
- int j = binary_search(arr, x, 0, arr.size() - 1);
- cout << j << endl; // 输出:1 即8所在的数组下标
- return 0;
- }
正确性分析:
命题: 如果x∈a[low ... high],算法返回 j,其中 x=a[j], low j< high,否则返回-1
对数组 a 的长度 n = high - low +1 进行归纳:
- 基本情况: n = 0
- low = high +1,此时算法返回-1,显然正确 (空数组不包舍x)
- 归纳假设: 假设对所有长度小于 k > 1 的a的子数组,命题正确
- 归纳步骤: 证明对长度为k的数组,命题正确
- a[mid]=x: 算法返回mid,显然正确
- a[mid]<x: 因为a有序,所以x ∈ a[mid + l..high],子问题能够正确求解,所以命题正确
- a[mid]>x: 因为a有序,所以x ∈ a[low..mid-1],子问题能够正确求解,所以命题正确
输入:一个已排序数组a[1..n],一个元素x
输出: 元素x的出现次数
方法一:直接使用二分搜索
- int direct_count(const vector<int>& a, int x, int j=-1)
- {
- count = 0;
- j = binary_search(a,x,0,a.size())
- if (j) //若x存在,开始左右遍历
- i = j-1; k = j+1; count++;
- while(a[i]==x && i>=0){ // <-左遍历
- count++;
- i--;
- }
- while(a[k]==x && k<a.size()){ // ->右遍历
- count++;
- k++;
- }
- return count;
- }
方法二:改进二分搜索
- //二分找左边界
- int first(const vector<int>& a, int x, int left, int right)
- {
- int leftIndex = -1; //左边界下标
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (a[mid] == x) {
- leftIndex = mid;
- right = mid - 1; //右侧向左靠拢,不断逼近左边界
- }
- else if (a[mid] > x) {right = mid - 1;}
- else {left = mid + 1;}
- }
- }
-
- //二分找右边界
- int last(const vector<int>& a, int x, int left, int right)
- {
- int rightIndex = -1; //右边界下标
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (a[mid] == x) {
- rightIndex = mid;
- left = mid + 1; //左侧向右靠拢,不断逼近右边界
- }
- else if (a[mid] > x) {right = mid - 1;}
- else {left = mid + 1;}
- }
- }
-
- int count(const vector<int>& a, int x)
- {
- int i = first(a, x, 0, a.size() - 1);
- if (i == -1) return 0;
- int j = last(a, x, i, a.size() - 1);
- return j - i + 1;
- }
给你k个任务和n台机器,其中机器i处理一个任务所需的时间为;
求处理所有任务所需的最短时间。
比如k=8,n=3,t[1..3] ={2,3,1}时,最短时间为9
这道题同样可以采用二分法进行递归求解。解题思路:
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
-
- int calculateTasks(vector<int>& times, int T) {
- int tasks = 0;
- for(int time : times) {
- tasks += T / time;
- }
- return tasks;
- }
-
- int findShortestTime(vector<int>& times, int machines, int totalTasks) {
- int left = 1;
- int right = *min_element(times.begin(), times.end()) * totalTasks;
- int shortestTime = right;
-
- while (left <= right) {
- int mid = left + (right - left) / 2;
- int completedTasks = calculateTasks(times, mid);
-
- if (completedTasks >= totalTasks) {
- shortestTime = mid;
- right = mid - 1;
- } else {
- left = mid + 1;
- }
- }
-
- return shortestTime;
- }
-
- int main() {
- vector<int> times = {2, 3, 1};
- int machines = 3;
- int totalTasks = 8;
-
- int shortestTime = findShortestTime(times, machines, totalTasks);
-
- cout << "处理所有任务所需的最短时间为:" << shortestTime << endl;
-
- return 0;
- }
1.寻找中位数
输入: 数组a[1..n]
输出:a[1],..,a[n]的中位数
2. 逆序对
在一个数组A[1...n]中,逆序对 (inversion) 是一对索引(i,j),满足i<j 且A[i]>A[j]。一个包含n个元素的数组中的逆序对数量介于0(如果数组已排序)和2n(如果数组完全逆序)之间。设计一个高效的算法计算数组A[1...n]中逆序对的数量。
3.支配点
给定二维平面上两个不同的点p和q,如果p.x < q.x且p.y < q.y,称q支配p。给定一个点集P,设计一个高效的算法,计算每一个点p∈P支配的点的数量。给出算法的基本思路和伪代码描述,分析算法的时间复杂度。
习题答案:分治算法课后习题
习题答案:分治算法课后习题2
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。