[数据结构]关于分治思想+分治寻找最大(金块问题)

article/2024/3/2 12:13:58

分治思想是什么

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

直接上金块问题

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

一般来说寻找最大最小值我们直接使用预留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)操作,直到只剩一个子图为止,这个子图同时也是点生成子图,又是最小生成树


http://www.ngui.cc/article/show-747465.html

相关文章

kaggle实战:基于超市消费数据的用户个性化分析案例

大家好&#xff0c;今天给大家分享一篇 kaggle 数据集的新文章&#xff1a;基于一份超市消费数据集的用户个性化分析以及用户分群的实现。 更多详细内容参考原数据集地址&#xff1a; https://www.kaggle.com/code/sonalisingh1411/customer-personality-analysis-segmentati…

Python小炼(1):初识Python

"也许对我来说&#xff0c;太多拘束可能" 本篇的主要内容,针对的是一些常见的语法&#xff0c;在python中是怎样表示的&#xff0c;例如,python变量如何定义、选择、循环、判断结构是如何表示的&#xff1f;python函 数定义是怎么定义的…… ----前言 一、认识pyt…

【2022.12.10】备战春招Day5——每日一题 + 96. 不同的二叉搜索树

【每日一题】1691. 堆叠长方体的最大高度 题目描述 给你 n 个长方体 cuboids &#xff0c;其中第 i 个长方体的长宽高表示为 cuboids[i] [widthi, lengthi, heighti]&#xff08;下标从 0 开始&#xff09;。请你从 cuboids 选出一个 子集 &#xff0c;并将它们堆叠起来。 如…

【指纹识别】指纹识别【含GUI Matlab源码 029期】

⛄一、指纹识别简介 指纹识别技术主要分三个步骤&#xff1a;指纹预处理、特征提取、指纹分类与匹配。 无论是指纹分类还是指纹匹配,都需要提取指纹的有效特征,而特征提取的性能很大程度上要依赖于指纹图像的质量。在实际应用中,由于采集条件和采集设备的因素,采集到的指纹图像…

计算机组成原理复习题之计算机的基础概要

计算机组成原理复习题之计算机的基础概要 概述&#xff1a;下图是我们老师课堂上&#xff0c;给我们做的计算机组成原理的课后习题&#xff0c;和对应的答案&#xff0c;主要讲的是计算机的基础概要&#xff0c;希望对大家复习计算机组成原理有帮助。 一、填空题 1、冯诺依曼…

VFP上传文件前判断文件大小,超过200M不让上传

代码很简单&#xff0c;以下是判断文件不能超过200M cFileGetfile("jpg|png") If !File(lcFile)Return EndifADIR(laarray,lcFile)IF laarray[2]/1024>1024*200MESSAGEBOX("文件不能超过200M",016,thisform.Caption)RETURN ENDIF 附HTTP文件上传代码…

Go 实现插入排序算法及优化

Go 实现插入排序算法及优化插入排序算法实现算法优化小结耐心和持久胜过激烈和狂热。 哈喽大家好&#xff0c;我是陈明勇&#xff0c;今天分享的内容是使用 Go 实现插入排序算法。如果本文对你有帮助&#xff0c;不妨点个赞&#xff0c;如果你是 Go 语言初学者&#xff0c;不妨…

爆火Chatgpt注册 chatgpt使用 完全指南

1 chatgpt 简介 ChatGPT是一种语言模型&#xff0c;它被训练来对对话进行建模。它能够通过学习和理解人类语言来进行对话&#xff0c;并能够生成适当的响应。ChatGPT使用了一种叫做Transformer的神经网络架构&#xff0c;这是一种用于处理序列数据的模型&#xff0c;能够在输入…

[附源码]JAVA毕业设计-心理健康管理-(系统+LW)

[附源码]JAVA毕业设计-心理健康管理-&#xff08;系统LW&#xff09; 项目运行 环境项配置&#xff1a; Jdk1.8 Tomcat8.5 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&a…

Linux系统之安装apache服务

Linux系统之安装apache服务一、检查本地系统版本二、配置yum仓库1.配置阿里的yum源2.检查yum仓库三、安装httpd软件包1.安装httpd2.启动httpd服务四、新增IP地址1.查看原有IP2.新增IP地址五、修改httpd配置文件1.创建三个虚拟主机的根目录2.添加网页文件内容六、基于ip的虚拟主…