首页/新闻资讯/正文详情

分治法的递归实现

发布时间:2026/9/24 7:49:33 来源:云帆数科 栏目:资讯中心
分治法的递归实现
分治法的递归实现一. 分治思想分治法核心分、治、合分将大问题拆分为多个结构相同的子问题治递归求解子问题子问题足够小时直接返回递归出口合合并子问题的解得到原问题结果二. C通用模板cpp// l、r代表区间左右边界int divide(int l, int r){// 递归出口if (l r)return 基础解;// 分int mid (l r) / 2;int leftRes divide(l, mid);int rightRes divide(mid 1, r);// 合return merge(leftRes, rightRes);}三. 示例归并排序经典分治C代码cpp#include#includeusing namespace std// 合并两个有序区间void merge(vector arr, int l, int mid, int r){vector tmp(r - l 1);int i l, j mid 1, k 0;while (i mid j r){if (arr[i] arr[j])tmp[k] arr[i];elsetmp[k] arr[j];}while (i mid) tmp[k] arr[i];while (j r) tmp[k] arr[j];// 写回原数组for (int p 0; p tmp.size(); p)arr[l p] tmp[p];}// 分治递归void mergeSort(vector arr, int l, int r){if (l r) return; // 递归终止int mid (l r) / 2;mergeSort(arr, l, mid); // 处理左半区间mergeSort(arr, mid1, r); // 处理右半区间merge(arr, l, mid, r); // 合并结果}int main(){vector arr {5,2,9,1,6};mergeSort(arr, 0, arr.size()-1);for (int num : arr)cout num ;return 0;}复杂度\boldsymbol{O(n\log n)}四. 适用场景 易错点适用归并排序、快速排序、数组求最值、统计逆序对等。易错缺少递归出口栈溢出区间划分错误元素重复或漏掉忘记合并子问题结果小结分治递归自顶向下拆分自底向上合并。把复杂大问题拆解成简单小问题求解是分治最巧妙的地方。

相关推荐

汇川IS620伺服调试实战:InoServoShop连接、参数监控与备份全攻略
汇川IS620伺服调试实战:InoServoShop连接、参数监控与备份全攻略

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 7:49:21

Win11升级TPM 2.0检测失败?Intel PTT与AMD fTPM开启指南
Win11升级TPM 2.0检测失败?Intel PTT与AMD fTPM开启指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 7:49:15

新能源车企数字化建设方案:从业务蓝图到数据资产落地
新能源车企数字化建设方案:从业务蓝图到数据资产落地

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 7:49:15

EMQX 插件 API 网关修复:HTTP 请求头与查询参数透传机制深度解析
EMQX 插件 API 网关修复:HTTP 请求头与查询参数透传机制深度解析

后端物联网消息队列通信 【免费下载链接】emqx The most scalable and reliable MQTT broker for AI, IoT, IIoT and connected vehicles 项目地址: https://gitcode.com/gh_mirrors/em/emqx 点击查看 免费下载 导读 本文围绕 EMQX 开源仓库中的一条缺陷修复记录&… · 2026/9/24 8:26:18

SWIR051AU短波红外相机:从InGaAs原理到工业检测实战
SWIR051AU短波红外相机:从InGaAs原理到工业检测实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 8:25:15

LTspice第三方SPICE模型集成全流程指南
LTspice第三方SPICE模型集成全流程指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 8:25:02

芯片IP选型避坑指南:架构适配、工艺兼容与验证完备性实战
芯片IP选型避坑指南:架构适配、工艺兼容与验证完备性实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 8:24:56

Vega 平行坐标图实战:多维汽车数据的 axes-offset 折线布局规范全解析
Vega 平行坐标图实战:多维汽车数据的 axes-offset 折线布局规范全解析

数据可视化 【免费下载链接】vega A visualization grammar. 项目地址: https://gitcode.com/gh_mirrors/ve/vega 点击查看 免费下载 平行坐标(Parallel Coordinates)是一种用于多维数据可视化的经典图表:每个维度占据一条平行的… · 2026/9/24 8:24:31

RLHF、InstructGPT 与 DPO:大模型对齐训练全面解析
RLHF、InstructGPT 与 DPO:大模型对齐训练全面解析

本文系统讲解大模型对齐训练的核心方法:RLHF(基于人类反馈的强化学习)、InstructGPT 的三步对齐流程,以及 DPO(直接偏好优化)。从原理、步骤、优缺点到实践细节,一篇讲透。一、什么是 RLHF&… · 2026/9/24 8:24:25

基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程
基于YOLOv8的渔船作业监控系统:从环境搭建到边缘部署全流程

简介:这是一套面向计算机、人工智能、自动化等专业学生与教师的毕业设计级项目资源,围绕YOLOv8实现渔船作业监控系统,可用于毕设、课程设计、大作业或项目立项演示。压缩包共97个文件,约24.21MB,以70个Python源码文件为… · 2026/9/24 0:00:13

1D-CNN时间序列建模实战:从Conv1d原理到工业落地
1D-CNN时间序列建模实战:从Conv1d原理到工业落地

简介:面向时间序列数据建模的一维卷积神经网络完整实现,适合深度学习入门者及需要快速验证时序模型的研究者,能够从音频、文本、传感器或股价等序列中挖掘局部特征与时间依赖。压缩包体积很小,只有3KB,内含3个Python脚… · 2026/9/24 0:00:26

柔软的L:汉语语流中被忽视的舌肌张力控制
柔软的L:汉语语流中被忽视的舌肌张力控制

1. 这个“L”不是字母表里的L,而是舌尖上的L最近在几个方言群和语音教学社群里,反复看到有人发一句:“也说字母L:柔软的长舌”。初看以为是英语发音课笔记,点开才发现全是方言爱好者、播音系学生、语言康复师甚至戏曲演… · 2026/9/24 0:00:44

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码