第8章 分治机构

8分治8.1分治算法概述8.2二分答案8.3典型分治例题8.1分治算法概述分治算法是一种非常重要的算法设计思想。它的核心策略是将一个复杂的大问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，递归地解决这些子问题，然后将各子问题的解合并，从而得到原问题的解。这种策略在处理大规模数据或复杂计算时非常有效，能够显著降低时间复杂度。本章我们将深入探讨分治算法的基本原理、适用条件，并通过经典案例掌握其应用。定义：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。核心思想：分：分解问题，将大问题分解为多个规模较小的子问题。治：合并结果，将子问题的解合并得到原问题的解。实现方式：通常采用递归的方式实现。递归能很好地匹配分治的“分解”与“回溯”过程。适用问题特征：问题规模缩小到一定程度就容易解决。问题可以分解为若干个规模较小的相同问题。子问题的解可以合并为原问题的解。子问题相互独立（无公共子问题）。经典应用：二分搜索、归并排序、快速排序大整数乘法、棋盘覆盖最接近点对问题、循环比赛日程表二分答案是分治算法的经典应用，通过不断猜测中间值并验证，在已知答案范围且具有单调性的场景中快速求解。定义以二分搜索的方式查找答案，是分治算法的一种简单应用。基本定义适用场景1.无法直接求解，但知道答案区间。2.答案在区间内具有单调性。适用场景核心思想通过不断猜测答案并验证其正确性，快速缩小搜索范围，最终找到符合条件的解。核心思想8.2.1二分答案概述问题描述：从n条绳子中切割出m条长度相同的绳段，求绳段的最大长度。解题思路：1.确定答案范围：[最长绳长/m,总绳长/m]。2.二分搜索：猜测一个长度mid，检查能否切割出m段。3.根据检查结果调整搜索范围，直到找到最大值。1boolCheck(intlen){...}//检查能否切割出m段2voidSearch(intL,intR){...}//二分搜索最大长度8.2.2切割绳子已知条件：贷款总额、每月还款额、还款总月数。求解目标：计算贷款的月利率。问题描述1.确定范围：利率范围[0,300]。2.二分搜索：猜测利率mid，检查m个月能否还清。3.注意事项：实数二分，循环条件while(l<r-0.05)。解题思路doublel=0,r=300;while(l<r-0.05){doublemid=(l+r)/2;if(check(mid))

{

ans=mid;

l

=mid;

}else

r

=mid;}核心代码逻辑8.2.3银行贷款问题问题描述：找出序列中连续且非空的一段，使其和最大。分治策略：1.分解：将数组分成左右两半。2.求解：递归求解左右两半的最大子段和。3.合并：求解跨越中点的最大子段和，最终结果为三者中的最大值。跨越中点的处理：以中点为基准，分别向左右两侧搜索最大子段，再合并。8.3.1最大子段和最大子段和核心代码：递归实现分治策略intsubsegment(intleft,intright){if(left==right)returna[left];intmid=(left+right)/2;intleftmax=subsegment(left,mid);intrightmax=subsegment(mid+1,right);//计算跨越中点的最大子段和intsum1=MinInt,sum2=MinInt;for(inti=mid,sum=0;i>=left;i--){...}//向左搜索最大子段和for(inti=mid+1,sum=0;i<=right;i++){...}//向右搜索最大子段和returnmax(max(leftmax,rightmax),sum1+sum2);}问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多只允许完成一笔交易（即买入和卖出一支股票）。分治策略：1.分解：将价格序列分成左右两半。2.求解：递归求解左右两半的最大利润。3.合并：求解左半部分买入、右半部分卖出的最大利润，最终结果为三者中的最大值。算法关联：本题是最大子段和问题的变种。若将价格序列转化为每日的利润序列（后一天减前一天），则原问题等价于寻找该利润序列的最大子段和。算法关联8.3.2股票买卖问题问题描述为n=2^k个运动员设计满足特定要求的循环赛日程表。分治策略分解：将n个运动员分成两半。求解：递归为两半运动员设计日程表。合并：根据规律填充整个日程表(A=D,B=C,B=A+n/2)。规律总结日程表可以由左上角的子表通过复制和加法生成。n=4时的日程表规律8.3.3循环赛日程表voidsolve(intn){if(n==1)return;inthalf=n/2;solve(half);//填写左上角for(inti=0;i<half;i++){for(intj=0;j<half;j++)

{arr[i+half][j]=arr[i][j]+half;//填写左下方arr[i][j+half]=arr[i+half][j];//填写右上方arr[i+half][j+half]=arr[i][j];//填写右下方}}}1.分治算法定义：分而治之，将大问题分解为子问题，合并子问题的解。2.适用条件：问题可分解、子问题可合并、子问题独立。3.二分答案：特殊的分治应用，适用于答案有范围且单调的问题。4.典型应用：最大子段和、股票买卖、循环赛日程表。