下载文档原格式
第四章分治算法§1. 算法基本思想考虑下面折半搜索算法程序4-1-1 折半搜索template<class T>int BinarySearch(T a[], const T& x, int n){//在数组a[0:n-1]中搜索x，数组中的元素满足a[0]<=a[1] //<= ···<=a[n-1]。
如果找到x，则返回所在位置（数组元素的下标），//否则返回–1int left=0; int right=n-1;while(left<=right){int middle=(left+right)/2;if(x==a[middle]) return middle;if(x>a[middle]) left=middle+1;else right=middle – 1;}return –1; //未找到x}while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行)Θ次。
由于每次循环需耗时)1((log nΘ，因此在最坏情况下，总的时间复杂性为)Θ。
(log n折半搜索算法贯彻一个思想，即分治法。
当人们要解决一个输入规模，比如n，很大的问题时，往往会想到将该问题分解。
比如将这n个输入分成k个不同的子集。
如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的难以解决的问题就可以得到解决。
这种将整个问题分解成若干个小问题来处理的方法称为分治法。
一般来说，被分解出来的子问题应与原问题具有相同的类型，这样便于采用递归算法。
如果得到的子问题相对来说还较大，则再用分治法，直到产生出不用再分解就可求解的子问题为止。
人们考虑和使用较多的是k=2的情形，即将整个问题二分。
以下用A[1:n]来表示n个输入，用DanC(p,q)表示处理输入为A[p:q]情况的问题。
实验一递归与分治策略一、实验目的：熟练掌握递归与分治策略的思想并应用其解决实际问题。
二、递归与分治策略思想基本思想:将要求解的较大规模的问题分割成k个更小规模的子问题。
对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
实验题目(1-2):找出从自然数1,2,…，n中任取r个数的所有组合。
算法思想：当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。
这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。
设函数引入工作数组a[ ]存放求出的组合，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。
第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或已确定了组合的全部元素，输出这个组合。
问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。
例如n=5，r=3的所有组合为：（1）5、4、3 （2）5、4、2 （3）5、4、1（4）5、3、2 （5）5、3、1 （6）5、2、1（7）4、3、2 （8）4、3、1 （9）4、2、1（10）3、2、1分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。
设函数为void find(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。
当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。
这就将求m个数中取k 个数的组合问题转化成求m-1个数中取k-1个数的组合问题。
设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中，当一个组合求出后，才将a[ ]中的一个组合输出。
第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。
计算机算法设计与分析第4版(王晓东著)课后答
案下载
计算机算法设计与分析第4版内容简介
第1章算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。
全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。
主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。
书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。
为突出教材的`可读性和可用性，章首增加了学习要点提示，章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。
算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。
频率计数是指计算机执行程序中的某一条语句的执行次数。
多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。
指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。
2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。
3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。
4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。
5. 解：①n=11； ②n=12； ③n=982； ④n=39。
第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。
2． 解：通过分治算法的一般设计步骤进行说明。
3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。
分治算法及其典型应用分治算法是一种非常重要的算法设计思想，它将一个大问题分解成多个小问题，然后分别解决这些小问题，最后将它们的解合并起来得到原问题的解。
分治算法的典型应用包括快速排序、归并排序、二分搜索等。
快速排序是一种高效的排序算法，它采用分治思想将原始数组分解成较小的子数组，然后分别对这些子数组进行排序。
最后将这些子数组合并起来得到有序的数组。
快速排序的时间复杂度为O(nlogn)，在实际应用中被广泛使用。
归并排序也是一种常见的排序算法，它同样采用分治思想将原始数组分解成较小的子数组，然后分别对这些子数组进行排序。
不同的是，归并排序是通过将有序的子数组合并起来得到有序的数组。
归并排序同样具有O(nlogn)的时间复杂度。
二分搜索是一种查找算法，它也是基于分治思想。
在一个有序数组中查找特定元素时，二分搜索将数组分为两部分，然后分别在两部分中查找目标元素。
如果找到了目标元素，算法返回其索引；否则继续在相应的子数组中查找。
二分搜索的时间复杂度为O(logn)。
除了排序和查找，分治算法还被广泛应用于解决许多其他问题，如最大子数组问题、矩阵乘法、棋盘覆盖等。
通过将原始问题分解成较小的子问题，分治算法能够显著降低问题的复杂度，提高算法的效率。
总之，分治算法是一种非常重要的算法设计思想，它在计算机科学和工程领域有着广泛的应用。
通过将原始问题分解成多个小问题，然后分别解决这些小问题，最后将它们的解合并起来，分治算法能够解决许多复杂的问题，并且在实际应用中取得了巨大的成功。
33第四讲 分治法一、引入问题1：找出伪币给你一个装有1 6枚硬币的袋子。
1 6枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。
你的任务是找出这枚伪造的硬币。
为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。
利用这台仪器，可以知道两组硬币的重量是否相同。
方法1任意取1枚硬币，与其他硬币进行比较，若发现轻者为伪币。
最多可能有15次比较。
方法2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。
最多可能有8次比较。
方法3分析上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。
问题2：金块问题有一个老板有一袋金块。
每个月将有两名雇员会因其优异的表现分别被奖励一个金块。
按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。
根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。
如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。
假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。
方法1假设袋中有n 个金块。
可以用函数M a x通过n-1次比较找到最重的金块。
找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。
这样，比较的总次数为2n-3。
算法如下：max:=a[1];min:=a[1];for i:=2 to n do {2n-2次比较}beginif a[i]>max then max:=a[i];if a[i]<min then min:=a[i];end ;可对上述改进少1次max:=a[1];for i:=2 to n do {n-1次比较，从n个元素中找到最大的}if a[i]>max then begin max:=a[i]; j:=i; end;for i:=j+1 to n do a[i-1]:=a[i]; {去掉最大的数a[j]}min:=a[1];for i:=2 to n-1 do {n-2次比较，从剩下的元素中找最小的}if a[i]>max then min:=a[i];找金块的示例图3435方法2：n ≤2，识别出最重和最轻的金块，一次比较就足够了。
分治算法问题分解与解决及代码示例在计算机科学领域中，分治算法是一种将问题分解成若干个相互独立且具有相同结构的子问题，然后通过解决子问题并将结果合并得到原问题的解决方法。
它常常被用于处理复杂问题，特别是在算法设计和分析中起到了重要的作用。
本文将介绍分治算法的问题分解与解决的基本思想，并提供相应的代码示例。
一、问题分解与解决的基本思想分治算法的关键思想是将大问题划分为若干个规模较小且结构相似的子问题，然后递归地解决这些子问题，并将结果进行合并以得到原问题的解决方案。
该算法可以分为三个基本步骤：分解、解决和合并。
1. 分解：将原问题划分为若干个规模较小的子问题。
这一步骤需要根据具体问题的特点来确定如何进行子问题的划分，确保子问题的规模逐步减小。
2. 解决：通过递归地调用分治算法来解决子问题。
当子问题的规模足够小可以直接求解时，就不需要再进行递归调用。
3. 合并：将子问题的解进行合并，得到原问题的解。
这一步骤通常需要根据具体问题的特点进行具体的合并操作。
二、代码示例以下是一个经典的分治算法的代码示例，用于计算一个整数数组的最大值。
```pythondef find_max(nums, left, right):if left == right:return nums[left]mid = (left + right) // 2left_max = find_max(nums, left, mid)right_max = find_max(nums, mid+1, right)return max(left_max, right_max)nums = [5, 2, 9, 3, 1, 6]max_value = find_max(nums, 0, len(nums)-1)print("The maximum value is:", max_value)```上述代码中，`find_max`函数用于递归地寻找给定数组 `nums` 中的最大值。
《算法设计与分析》课程实验报告实验序号：04实验项目名称：实验4 分治法（三）一、实验题目1.邮局选址问题问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。
用x 坐标表示东西向，用y坐标表示南北向。
各居民点的位置可以由坐标(x,y)表示。
街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。
居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
编程任务：给定n 个居民点的位置,编程计算邮局的最佳位置。
2.最大子数组问题问题描述：对给定数组A，寻找A的和最大的非空连续子数组。
3.寻找近似中值问题描述：设A是n个数的序列，如果A中的元素x满足以下条件：小于x的数的个数≥n/4,且大于x的数的个数≥n/4 ，则称x为A的近似中值。
设计算法求出A的一个近似中值。
如果A中不存在近似中值，输出false，否则输出找到的一个近似中值4.循环赛日程表问题描述：设有n=2^k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1个选手各赛一次，每个选手一天只能赛一次，循环赛一共进行n-1天。
二、实验目的（1）进一步理解分治法解决问题的思想及步骤（2）体会分治法解决问题时递归及迭代两种不同程序实现的应用情况之差异（3）熟练掌握分治法的自底向上填表实现（4）将分治法灵活于具体实际问题的解决过程中，重点体会大问题如何分解为子问题及每一个大问题涉及哪些子问题及子问题的表示。
三、实验要求（1）写清算法的设计思想。
（2）用递归或者迭代方法实现你的算法，并分析两种实现的优缺点。
（3）根据你的数据结构设计测试数据，并记录实验结果。
（4）请给出你所设计算法的时间复杂度的分析，如果是递归算法，请写清楚算法执行时间的递推式。
四、实验过程（算法设计思想、源码）1.邮局选址问题(1)算法设计思想根据题目要求，街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。
