首页 > 编程学习 > [数据结构]关于分治思想+分治寻找最大(金块问题)

分治思想是什么

分治思想指的是把一个大问题转化为多个小问题,比如以前常见的归并算法和快速排序算法都是常见的应用

直接上金块问题

问题来历:假设现在有一堆金块,要从其中找出最重和最轻的一块

一般来说寻找最大最小值我们直接使用预留max min即可,但是我们可以利用分治的思想进行处理

非递归处理的分治金块问题

处理原理:先设置好max和min,然后后续一对一对地进行比较,每次遍历中获取一对元素,然后这两个元素进行比较,得到较大和较小两个。

然后利用较大的判断是否更新max,再利用较小的判断是否更新min

(1)当元素总数为奇数个的时候,设第1个元素同时为最大最小值,然后后面的n-1个元素正常进行比较即可

(2)当元素个数为偶数个的时候,先比较一下第一个第二个元素,把max和min设置出来

具体代码如下

void findMaxAndMin(int  arr[],int length){int max,min;if(length==1){max=min=0;}else{if(length%2==0){//偶数个的情况if(arr[0]>=arr[1]){max=0;min=1;}else{max=1;min=0;}for(int i=2;i<=length-2;i+=2){if(arr[i]>arr[i+1]){if(arr[i]>arr[max]){max=i;}if(arr[i+1]<arr[min]){min=i+1;}}else{if(arr[i+1]>arr[max]){max=i+1;}if(arr[i]<arr[min]){min=i;}}}}else{         //奇数个情况max=min=0;for(int i=1;i<=length-2;i+=2){if(arr[i]>arr[i+1]){if(arr[i]>arr[max]){max=i;}if(arr[i+1]<arr[min]){min=i+1;}}else{if(arr[i+1]>arr[max]){max=i+1;}if(arr[i]<arr[min]){min=i;}}}}}cout<<"最大值为"<<max<<":"<<arr[max]<<"最小数"<< min<<":"<<arr[min]<<endl;
}

总结:非递归方法实际上只是分成了两组进行比较而已,或许缩减了一半工作量,但是效果并不是太明显,不像是递归那种简单明了的分治

利用递归方法寻找最大值

原理:参数:start end(均为整数)

           如果start==end,返回值为start

           否则,把字段分成两部分 返回(start,n)和(n+1,end)的中较大值

返回值为一个区间内最大的元素

代码如下

//这次仅仅寻找最大值?其实这玩意就是无限弱化版本的归并/快速排序
int findMax(int arr[],int start,int end){if(start==end){return arr[start];}else {int n=(start+end)/2;int a= findMax(arr,start,n);int b= findMax(arr,n+1,end);return a>b?a:b;}
}
//补充:关于排序算法稳定性的定义为数值一样的元素,排序前后,相对位置没有改变

第三种最小生成树算法sollin

这种算法有点分治再合并的意思?因为使用次数太少实践太难,所以基本不怎么用

这里只阐述一下原理:

(1)先把每个点都视为一个单独的图

(2)每个图的相邻边中取权重最小的一个,与对应边相邻的点形成新的子图

(3)对新生成的子图进行重复(2)操作,直到只剩一个子图为止,这个子图同时也是点生成子图,又是最小生成树


本文链接:https://www.ngui.cc/article/show-747465.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000