分治算法yu.ppt

分 治 算 法 例：找出伪币 给你一个装有n枚硬币的袋子。n枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。 为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。 对n=2,3,4,5,6,7,8,9? N=80 ? 分治思想 分治思想 分治策略的解题思路 if(问题不可分) { 直接求解； 返回问题的解； } else { 对原问题进行分治； 递归对每一个分治的部分求解; 归并整个问题，得出全问题的解； } 分 析 如果精确到小数点后两位，可用简单的枚举法：将x从-100.00 到100.00（步长0.01） 逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值 分 析 * 【分治思想】：分治就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。 分治步骤： 1.分解(Divide)：将原问题分成一系列子问题。 2.解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。 3.合并(combine)；将子问题的结果合并成原问题的解。 问题S 问题S 问题S S的解 问题S1 …… 问题S2 问题Si 问题Sn …… S1的解 …… S2的解 Si的解 Sn的解 …… 问题的分解 子集解的合并 子问题求解 应用举例:一元三次方程求解 【问题描述】：有形如：ax^3+bx^2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后4位。 提示：记方程f(x)=ax3+bx2+cx+d，若存在2个数x1和x2，且x1x2，f(x1)*f(x2)0，则在(x1，x2)之间一定有一个根。 【样例输入】：1 -5 -4 20 【样例输出】：-2.00 2.00 5.00 当已知区间(a,b)内有一个根时，用二分法求根，若区间(a,b)内有根，则必有f(a)*f(b)0。重复执行如下的过程： (1).若a+0.0001b或f((a+b)/2)=0，则可确定根为(a+b)/2并退出过程； (2).若f(a)* f((a+b)/2)0,则由题目给出的定理可知根在区间(a,(a+b)/2)中,故对区间重复该过程； (3).若f(a)* f((a+b)/2)0,则必然有f((a+b)/2)* f(b)0,根在((a+b)/2,b)中,对此区间重复该过程。 执行完毕,就可以得到精确到0.0001的根。 应用举例---二分查找 ? 在一个从小到大排序好的表里有哪些信誉好的足球投注网站关键码x ? 顺序查找：最坏情况下要比较所有元素 ? 二分查找：只需要比较log2n个元素 ? Divide: 检查中间元素 ? Conquer: 递归在其中一个区间内有哪些信誉好的足球投注网站 ? Combine: 平凡的 2.折半查找：是在一列升序（或降序）的数中查找目的数。将这一列数存储在数组a中,目的是寻找x,用top指向低端,bot指向高端,mid指向中间,然后进行以下三种比较： （1）若x=a[mid],则表示找到； （2）若xa[mid],则进行下一步查找,top不变,bot:=mid-1; （3）若xa[mid],则进行下一步查找, top:=mid-1;bot不变, 假如有已按由小到大排好序的9个数,a[1]--a[9] 其值分别为：1 3 5 7 9 11 13 15 17 int erfind(int low, int high, int x) //在a[low]与a[high]之间查找是否有值为x的元素 { int mid; while (low = high) { mid = (low + high) / 2; if (a[mid] ==x) return mid; //查找成功 if (x a[mid]) high=mid–1; else low=mid+1; }