分治算法(用C++、lua实现)
目录
本文为 分治算法 的代码实现。
作者水平比较差,有错误的地方请见谅。
1、算法
分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
可使用分治法求解的一些经典问题
(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔
此例子为使用分治法,来求一个数组中的最大连续子段。
连续子段为:-23,18,20,-7,12
最大值为:-23+18+20-7+12 = 43
2、C++实现
暴力求解
#include <iostream> using namespace std; int main() { //求最大的连续子段和 int sumArray[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; int length = sizeof(sumArray)/sizeof(sumArray[0]); int startIndex = 0; int endIndex = 0; int maxArray = sumArray[0]; for(int i=0;i<length;i++){ int tempPrice = 0; for(int j=i;j<length;j++){ tempPrice += sumArray[j]; if(tempPrice>maxArray) { maxArray = tempPrice; startIndex = i; endIndex = j; } } } cout<<"最大数组首index:"<<startIndex<<endl; cout<<"最大数组尾index:"<<endIndex<<endl; cout<<"最大值"<<maxArray<<endl; return 0; }
分治算法
#include <iostream> using namespace std; int startIndex; int endIndex; int maxArray; int GetMaxArray(int arr[],int low,int high); int main() { int sumArray[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; int length = sizeof(sumArray)/sizeof(sumArray[0]); startIndex = 0; endIndex = 0; maxArray = sumArray[0]; GetMaxArray(sumArray,0, length-1); cout<<"首index:"<<startIndex<<endl; cout<<"尾index:"<<endIndex<<endl; cout<<"最大值"<<maxArray<<endl; return 0; } int GetMaxArray(int arr[],int low,int high) { if (low == high) { startIndex = low; endIndex = high; return maxArray; } int mid = (low + high) / 2; //左区间的最大子段 int leftMax = GetMaxArray(arr,low, mid); //右区间的最大子段 int rightMax = GetMaxArray(arr,mid + 1, high); //左下标在左区间右下标在右区间的最大字段 int allMax = 0; //计算allMax的左半最大部分 int allMaxLeft = arr[mid] ; int leftIndex = mid; int tempNum = 0; for (int i = mid; i >= low; i--) { tempNum += arr[i]; if (tempNum > allMaxLeft) { allMaxLeft = tempNum; leftIndex = i; } } //计算allMax的右半最大部分 int allMaxRight = arr[mid + 1]; int rightIndex = mid + 1; tempNum = 0; for (int j = mid + 1; j <= high; j++) { tempNum += arr[j]; if (tempNum > allMaxRight) { allMaxRight = tempNum; rightIndex = j; } } //三者比较,谁的值最大 allMax = allMaxLeft + allMaxRight; startIndex = leftIndex; endIndex = rightIndex; return max(max(leftMax, rightMax), allMax); }
3、lua实现
sumArray = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7} length = #sumArray startIndex = 1 endIndex = 1 maxArray = sumArray[1] function GetMaxArray(arr,low,high) if(low == high) then startIndex = low; endIndex = high; return maxArray; end --mid不能为浮点数,向下取整 local mid = math.floor((low+high)/2) --左区间最大值 local leftMax = GetMaxArray(arr,low,mid) --右区间最大值 local rightMax = GetMaxArray(arr,mid+1,high) --左下标在左区间右下标在右区间的最大字段 local allMax = 0 --计算allMax的左半最大部分 local allMaxLeft = arr[mid] local leftIndex = mid local tempNum = 0 for i=mid,low,-1 do tempNum = tempNum + arr[i] if(tempNum > allMaxLeft) then allMaxLeft = tempNum leftIndex = i end end --计算allMax的右半最大部分 local allMaxRight = arr[mid+1] local rightIndex = mid+1 tempNum = 0 for i=mid+1,high,1 do tempNum = tempNum + arr[i] if(tempNum > allMaxRight) then allMaxRight = tempNum rightIndex = i end end allMax = allMaxLeft + allMaxRight --使用lua的多返回值 return leftIndex,rightIndex,MaxNum(MaxNum(leftMax,rightMax),allMax) end --自定义比较两个整数函数 function MaxNum(num1,num2) if(num1>num2) then return num1 end return num2 end startIndex,endIndex,maxArray = GetMaxArray(sumArray,1,length) print("首index:" .. startIndex) print("尾index:" .. endIndex) print("最大值:" .. maxArray)
相关推荐
Ghero 2020-08-09
数据与算法之美 2020-06-10
Broadview 2020-05-16
风吹夏天 2020-02-17
yishujixiaoxiao 2020-02-02
troysps 2019-12-30
Oudasheng 2019-12-19
shawsun 2019-12-23
baike 2019-12-15
蜗牛慢爬的李成广 2019-12-03
风吹夏天 2019-11-03
seekerhit 2019-10-19
微分 2014-05-25
duyifei0 2019-06-27
wonner 2017-10-05
OpenPI 2019-05-29
linergou 2016-12-26