亿企搜网站建设,python 做网站合适吗,app推广多少钱一个,优化神马排名软件什么是分治算法
分治算法是一种常见的问题解决方法#xff0c;它将一个复杂的问题划分为多个相同或相似的子问题#xff0c;然后递归地解决这些子问题#xff0c;最后将子问题的解合并得到原问题的解。
分治算法通常包含三个步骤#xff1a; 分解#xff08;Divide…什么是分治算法
分治算法是一种常见的问题解决方法它将一个复杂的问题划分为多个相同或相似的子问题然后递归地解决这些子问题最后将子问题的解合并得到原问题的解。
分治算法通常包含三个步骤 分解Divide将原问题划分成多个相同或相似的子问题。这里的划分策略取决于具体问题的特性。 解决Conquer递归地解决子问题。对于规模较小的子问题可以直接求解。 合并Combine将子问题的解合并成原问题的解。这一步骤通常在递归的回溯过程中完成。
分治算法的核心思想是将复杂的问题划分为规模更小的子问题并通过递归地解决这些子问题来解决原问题。通过合并子问题的解最终得到原问题的解。
分治算法常用于解决一些具有重叠子问题性质的问题例如归并排序、快速排序和求解最大子数组等。它可以提高问题的求解效率降低问题的复杂度。
然而分治算法并非适用于所有类型的问题。在应用分治算法时需要满足以下条件
原问题可以划分为多个规模较小的子问题。子问题的解可以合并成原问题的解。子问题之间相互独立即子问题之间没有重叠部分。
通过合理地划分问题、解决子问题和合并子问题的解分治算法可以帮助我们有效地解决各种复杂的问题。
常见的用分治算法解决的问题
1、归并排序
归并排序是一种常见的排序算法其基本思想是将待排序的数组分成两个子数组分别对这两个子数组进行递归排序然后将两个有序的子数组合并成一个有序的数组。下面是归并排序的算法思路 分解将待排序的数组分解为两个子数组。选择一个中间位置(mid)将数组一分为二分别得到左子数组和右子数组。 递归排序对左子数组和右子数组分别进行递归排序。将这一步骤递归地应用于左子数组和右子数组直到子数组的长度为1或0即无法再分解。 合并将两个有序的子数组合并成一个有序的数组。创建一个临时数组(tmp)来存储合并后的结果。从两个子数组的起始位置开始比较两个子数组的元素将较小的元素放入临时数组中并将对应子数组的指针向后移动一位。重复这个过程直到其中一个子数组的所有元素都被放入临时数组中。将剩余的子数组中的元素依次放入临时数组的末尾。最后将临时数组中的元素复制回原始数组的对应位置。 递归结束当子数组的长度为1或0时递归结束。此时数组已经有序。
代码实现
/*算法思路首先我们需要将一个待排序的序列分成若干个子序列我们采用2分法在中间mid处划分成了两个序列1、我们采用递归思想将一个序列在mid处划分直到不能划分为止
2、将划分的子序列进行排序然后将排序好的子序列合并*/void merge(int a[],int start,int mid,int end){int *tmp (int *)malloc((end-start1)*sizeof(int)); // 动态分配一个临时存放数组int i start;int j mid1;int k 0;// 排序while(imid jend){if(a[i]a[j]){tmp[k] a[i];}else{tmp[k] a[j];}}// 如果还剩下序列直接加到数组最后面while(imid){tmp[k] a[i];}while(jend){tmp[k] a[j];}// 最后合并子序列for(int i0;ik;i){a[starti] tmp[i]; }free(tmp);}void merge_sort(int a[],int start,int end){if(aNULL || startend){return ;}// 递归划分子序列int mid (startend)/2;merge_sort(a,start,mid);merge_sort(a,mid1,end);// 合并排序好的子序列merge(a,start,mid,end);
}
2、最大子数组问题
最大子数组问题是一个经典的问题其目标是在给定数组中找到一个子数组使得该子数组的元素和最大 基本情况如果数组的长度为1直接返回该元素作为最大子数组。 分解将原数组划分为两个子数组。找到数组的中间位置将数组一分为二分别得到左子数组和右子数组。 递归求解对左子数组和右子数组分别进行递归求解最大子数组。即对左子数组和右子数组分别调用最大子数组算法。 跨越中点的最大子数组考虑包含中点的子数组即左子数组的最右边元素和右子数组的最左边元素之间的连续子数组。从中点开始向左扩展记录最大和然后从中点开始向右扩展记录最大和。将这两个和相加得到跨越中点的最大子数组和。 合并比较左子数组、右子数组和跨越中点的最大子数组的和取最大的作为最终的最大子数组和。 返回结果返回最大子数组的起始位置、结束位置和和值。
代码实现
#include stdio.h
#include limits.h// 求解跨越中点的最大子数组和
int maxCrossingSum(int arr[], int low, int mid, int high) {int leftSum INT_MIN; // 表示无穷小因为负数也要进行求和运算 int sum 0;// 求出左边子序列的最大值 for (int i mid; i low; i--) {sum arr[i];if (sum leftSum) {leftSum sum;}}int rightSum INT_MIN;sum 0;// 求右边子序列的最大值 for (int i mid 1; i high; i) {sum arr[i];if (sum rightSum) {rightSum sum;}}return leftSum rightSum;
}// 分治法求解最大子数组和
int maxSubArrayUtil(int arr[], int low, int high) {// 当子序列只有一个元素时if (low high) {return arr[low];}int mid (low high) / 2;// 最大子数组和可能在左边、右边或跨越中点int leftMax maxSubArrayUtil(arr, low, mid);int rightMax maxSubArrayUtil(arr, mid 1, high);// 合并之后的值int crossMax maxCrossingSum(arr, low, mid, high);// 返回三者中的最大值// condition ? expression_if_true : expression_if_false;// condition 条件为真则返回 expression_if_true否则返回expression_if_falsereturn (leftMax rightMax leftMax crossMax) ? leftMax : ((rightMax leftMax rightMax crossMax) ? rightMax : crossMax);
}// 对外接口调用分治法求解最大子数组和
int maxSubArray(int arr[], int numsSize) {return maxSubArrayUtil(arr, 0, numsSize - 1);
}int main() {int nums[] {1,-2,4,5,-2,8,3,-2,6,7,3,-1};int numsSize sizeof(nums) / sizeof(nums[0]);int result maxSubArray(nums, numsSize);printf(子数组最大和为: %d\n, result);return 0;
}在这里会有一个问题就是如果你输入的数组 num [-1,-1,-2,-2]时你返回的结果是-2但其实真正的最大值是-1所以分治算法并不是解决最大子数组问题的最优解在这个给大家分享另一种算法思路那就是利用动态规划的算法思想来解决问题。
思路
1、定义一个动态规划数组 D其中 D[i] 表示以第 i 个元素结尾的最大子数组和。
2、递推关系是关键它告诉我们如何通过已知信息计算新的信息D[i] max(D[i-1] num[i], num[i])
代码如下
# include stdio.hint max(int a,int b){if(ab){return a;}else{return b;}
}int maxSubArray(int* num,int size){if(size 0){return 0;}int D[size];D[0] num[0]; // 动态规划数组D[i]表示以第i个元素结尾的最大子数组和int maxSum D[0]; // 初始化第一个元素// 从第二个元素开始遍历数组根据递推关系更新动态规划数组for(int i 1;isize;i){D[i] max((D[i-1]num[i]),num[i]);if(maxSum D[i]){maxSum D[i];}}return maxSum;
}int main(){int nums[] {-2, 1, -3, 4, -1, 2, 1, -5, 4};int size sizeof(nums) / sizeof(nums[0]);int result maxSubArray(nums, size);printf(Maximum Subarray Sum: %d\n, result);return 0;
}
3、逆序对问题
逆序对问题是一个经典的问题其目标是计算一个数组中逆序对的数量。逆序对指的是数组中的两个元素若其在数组中的相对顺序与排序后的顺序相反则它们构成一个逆序对。
例如num [5,2,3,6,8] 其中num[0] 5,num[1] 2, 这就是一个逆序对。
下面是逆序对问题的一种常见算法思路基于归并排序的思想 分解将原数组划分为两个相等的子数组直到子数组的长度为 1。这可以通过递归实现。 递归求解对左子数组和右子数组分别进行递归求解逆序对的数量。 合并与计数在合并左右子数组的过程中统计逆序对的数量。合并时使用两个指针分别指向左子数组和右子数组的起始位置并进行比较。若右子数组当前元素小于左子数组当前元素则构成逆序对并将逆序对的数量累加。同时将较小的元素放入合并后的数组中移动对应的指针。若左子数组或右子数组遍历完毕则将剩余的元素直接放入合并后的数组中。 返回结果返回逆序对的数量。
代码实现
# include stdio.h
# includestdlib.h// 归并排序辅助函数将两个有序数组合并为一个有序数组并计算逆序对个数
int merge(int* num,int low,int mid,int high){int count 0;int* tmp (int *)malloc((high-low1)*sizeof(int));int i low;int j mid1;int k 0;while(imid jhigh){if(num[i]num[j]){tmp[k] num[i];}else{tmp[k] num[j];count (mid-i1); // 左数组剩余元素都大于arr[j]构成逆序对}}while(imid){tmp[k] num[i];}while(jhigh){tmp[k] num[j];}// 将合并后的结果拷贝回原数组for(int m 0;mk;m){num[lowm] tmp[m];}free(tmp);return count;
}// 归并排序
int merge_sort(int* num,int low,int high){int count 0;if(num NULL || low high){return 0;} int mid (lowhigh)/2;// 分别对左右两个子数组进行归并排序并累加逆序对个数count merge_sort(num,low,mid);count merge_sort(num,mid1,high);// 合并两个有序数组并累加逆序对个数count merge(num,low,mid,high);return count;} // 求解逆序对
int countInversePairs(int* num ,int length) {int count merge_sort(num,0,length-1);return count;}int main(){
// int arr[] {13,8,10,6,15,18,12,20,9,14,17,19};int arr[] {4,6,8,3,5};
// int arr[] {9, 5, 7, 2, 4, 1, 6, 8, 3};int length sizeof(arr) / sizeof(arr[0]);int count countInversePairs(arr,length);printf(%d,count);return 0;
}
4、快速排序
快速排序是一种常用的排序算法其基于分治思想进行排序。下面是快速排序的算法思路 选择基准从数组中选择一个元素作为基准pivot。一般可以选择第一个元素、最后一个元素或者随机选择一个元素作为基准。 分区操作将数组中的元素按照与基准的大小关系划分为两个子数组一个子数组中的元素小于等于基准另一个子数组中的元素大于基准。可以通过使用两个指针一个指向数组的起始位置一个指向数组的结束位置通过交换元素来实现分区操作。 初始化两个指针 i 和 j分别指向数组的起始位置和结束位置。从指针 i 开始向右移动直到找到一个元素大于基准。从指针 j 开始向左移动直到找到一个元素小于基准。如果 i 小于等于 j交换指针 i 和 j 所指向的元素。继续移动指针直到 i 大于 j。 递归排序对基准左边的子数组和右边的子数组分别进行递归排序。即对左子数组和右子数组重复上述步骤直到子数组的长度为 1 或 0。 合并结果递归排序完成后数组已经有序。
代码实现
# includestdio.h// 交换数组中两个元素的值
void swap(int* a,int* b){int tmp *a;*a *b;*b tmp;
}// 划分函数返回基准元素的最终位置
int partition(int* num,int low,int high){int pivot num[high]; // 选择最后一个元素作为基准元素int i low - 1; // i表示小于基准的元素的右边界for(int j low;jhigh-1;j){if(num[j]pivot){i;swap(num[i],num[j]); // 将小于等于基准的元素交换到左侧}} swap(num[i1],num[high]); // 将基准元素放到正确的位置return i1; // 返回基准元素的最终位置} // 快速排序函数
void Quick_sort(int* num,int low,int high){if(lowhigh){int pivotIndex partition(num,low,high); // 划分数组获取基准元素的位置递归对基准元素左侧和右侧的子数组进行排序Quick_sort(num,low,pivotIndex-1);Quick_sort(num,pivotIndex1,high);}
} int main(){int num[] {9, 5, 7, 2, 4, 1, 6, 8, 3};int length sizeof(num) / sizeof(num[0]); Quick_sort(num, 0, length - 1);printf(排序结果);for (int i 0; i length; i) {printf(%d , num[i]);}printf(\n);return 0;
}
5、次序选择问题
次序选择问题Order Statistics Problem是指从一个未排序的数组中找到第 k 小或第 k 大的元素。下面是一种常见的算法思想基于快速排序的分治思想来解决次序选择问题这个可以看作快速排序的应用。 选择基准从数组中选择一个元素作为基准pivot。一般可以选择第一个元素、最后一个元素或者随机选择一个元素作为基准。 分区操作将数组中的元素按照与基准的大小关系划分为两个子数组一个子数组中的元素小于等于基准另一个子数组中的元素大于基准。可以通过使用两个指针一个指向数组的起始位置一个指向数组的结束位置通过交换元素来实现分区操作。 初始化两个指针 i 和 j分别指向数组的起始位置和结束位置。从指针 i 开始向右移动直到找到一个元素大于基准。从指针 j 开始向左移动直到找到一个元素小于基准。如果 i 小于等于 j交换指针 i 和 j 所指向的元素。继续移动指针直到 i 大于 j。 递归选择根据分区操作后基准的位置将问题转化为在基准的左边或右边子数组中寻找第 k 小或第 k 大的元素。若基准的位置为 k-1则找到了第 k 小或第 k 大的元素若基准的位置大于 k-1则在左边子数组中递归选择第 k 小或第 k 大的元素若基准的位置小于 k-1则在右边子数组中递归选择第 k-j 小或第 k-j 大的元素。 返回结果最终返回第 k 小或第 k 大的元素。
代码实现
#include stdio.h// 交换数组中两个元素的值
void swap(int* a, int* b) {int temp *a;*a *b;*b temp;
}// 划分函数返回基准元素的最终位置
int partition(int arr[], int low, int high) {int pivot arr[low]; // 选择第一个元素作为基准元素int i low; // i表示小于基准的元素的右边界for (int j low 1; j high; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]); // 将小于基准的元素交换到左侧}}swap(arr[low], arr[i]); // 将基准元素放到正确的位置return i; // 返回基准元素的最终位置
}// 快速选择函数
int quickSelect(int arr[], int low, int high, int k) {if (low high) {return arr[low]; // 当数组只有一个元素时直接返回该元素}int pivotIndex partition(arr, low, high); // 划分数组获取基准元素的位置if (k pivotIndex) {return arr[k]; // 基准元素即为第k小或第k大的元素} else if (k pivotIndex) {return quickSelect(arr, low, pivotIndex - 1, k); // 在基准元素的左侧递归查找} else {return quickSelect(arr, pivotIndex 1, high, k); // 在基准元素的右侧递归查找}
}int main() {下·int arr[] {9, 5, 7, 2, 4, 1, 6, 8, 3};int length sizeof(arr) / sizeof(arr[0]);int k 4; // 查找第4小的元素int result quickSelect(arr, 0, length - 1, k - 1);printf(第%d小的元素是%d\n, k, result);return 0;
}
总结一下其实分治思想就是一个将原问题化成多个子问题的算法思想其中有三个重要的步骤
分解原问题将原问题分解成多个子问题
解决子问题递归求解各个子问题
合并问题解将结果合并为原问题解
