计算基础教程 11

授课内容分治学时2教学目标知识目标理解分治算法的核心思想与基本步骤掌握分治算法适用问题的典型特征掌握二分答案的解题思路与实现方法了解最大子段和、循环赛日程表的分治解法能力目标提升复杂问题分解与规律归纳能力强化分治策略分析与算法设计能力培养分治与递归结合的问题求解能力重点与难点重点分治算法“分、治、合”的核心流程二分答案的思想、边界处理与适用场景最大子段和问题的分治求解方法分治算法与递归的结合使用要点难点合理划分子问题并正确合并子问题的解掌握二分答案中整数与实数区间的边界控制教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接贪心算法，学习高效的分治算法思想分治是计算机解决大规模问题的核心策略之一二分答案、快排、归并排序都是分治的典型应用掌握分治能显著提升处理大数据问题的效率本章实例丰富，可快速强化算法建模与编程能力第二部分：新课讲解一、分治算法概述1、算法思想分治算法的设计思想是将一个难以求解的大问题分割成一些规模较小且性质相同的子问题，以便各个击破，分而治之。2、算法过程整个分治过程分为“分”和“治”二步。“分”就是分解问题，将一个规模较大的问题，分解为多个规模较小的子问题。“治”就是合并，通过合并子问题的解来求出原问题的解。二、二分答案1、概述有一类题目，我们无法正面求解其答案，但我们知道答案的区间范围，并且答案在其区间范围内具有单调性，这时就可以使用二分答案的方式来快速找出答案。2、切割绳子题目有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。【输入格式】第一行是一个不超过100的正整数n第二行是一个不超过108的正整数m第三行是n个不超过106的正整数，表示每条绳子的长度【输出格式】绳段的最大长度，若无法切割，输出Failed。解析答案范围这个问题无法正面求解，但很容易找出答案的范围。答案的最小值min考虑最坏的情况，只使用一条绳子，并将其切割成m段。显然，这时应选择n条绳子中最长的那一条，将其长度除以m就是答案的最小值。答案的最大值max考虑最好的情况，就是n条绳子全部都能得到利用，没有任何切割“余料”。显然，答案的最大值是n条绳子长度之和除以m。②解题思路首先，计算出答案的中间值mid=（min+max）/2。然后，将n条绳子按每段长度为mid进行切割，看看总共能切割出多少段。如果能切割出的段数大于等于m，说明切割长度还可以再大一些，因此下一步将在[mid+1,max]之间搜索新的切割长度。如果切割出的段数小于m，说明切割长度过大，应该再调小一些，因此下一步将在[min,mid-1)之间搜索新的切割长度。按照上述步骤不停地进行搜索，每次搜索都能抛弃一半的搜索区间，很快就能找到一个切割长度t，在此尺寸下，n条绳子可以切割出m段；但若切割长度为t+1时，n条绳子就切割不出m段。这个t就是最终答案。程序详见课本。3、银行贷款题目当一个人从银行贷款后，在一段时间内他将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。【输入格式】三个用空格隔开的正整数。第一个整数表示贷款的原值w0，第二个整数表示每月支付的分期付款金额w，第三个整数表示分期付款还清贷款所需的总月数m。【输出格式】一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到0.1%。数据保证答案不超过300.0%。解析这个问题用数学方法求解非常麻烦，但使用计算机求解就非常简单了。只需要先假设利率为某一个值，然后利用这个假定的利率与月付款金额w，计算出在m个月后总共还了多少钱。如果这个钱数大于贷款的原值w0，就说明利率高了，需要再调低一点；反之，如果这个钱数小于w0，就说明利率低了，需要再调高一点。经过反复尝试，就能找出正确的利率值。三、典型分治例题1、最大子段和题目给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。【输入格式】第一行是一个整数，表示序列的长度n，1≤n≤2×105。第二行有n个整数，第i个整数表示序列的第i个数字ai，-104≤ai≤104。【输出格式】输出一行，一个整数表示答案。解析将数组从中间分成两半，然后分别求出这两半区间内的最大子段和。考虑到最大子段不一定全在数组的左半区间或者右半区间，它也可能跨越二个子区间的分界线。因此，整个数组的最大子段和为以下三种情况中的最大者：左半区间中的最大子段和右半区间中的最