return 1.0-2*s(x/2)*s(x/2);? }Р第八页，编辑于星期五：十六点 四十九分。РР5.2.1 分治与递归Р分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。?采用分治法解决的问题一般具有的特征如下： ? 1. 问题的规模缩小到一定的规模就可以较容易地解决。 ? 2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。 ? 3. 合并问题分解出的子问题的解可以得到问题的解。 ? 4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。?设计步骤?1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。 ? 2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。 ? 3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。Р第九页，编辑于星期五：十六点 四十九分。РР5.2.1 分治法应用举例Р二分搜索技术? 二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x,算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x。如果x>a[n/2],则只要在数组a的右半部继续搜索x。?合并排序：将待排序元素分成大小大致相同的2个子集合，分别对2个子集进行排序，最终将排好序的子集合合并成为所要求的集合。?快速排序:?线性时间选择：给定线性序集中n个元素和一个整数k,1<=k<=n,要求找出这n个元素中第k小的元素，即当k=1时找的是最小元素，k=n时找的是最大元素，当k=(n+1)/2时，成为找中位数。Р第十页，编辑于星期五：十六点 四十九分。
全文预览
