求方程的根.ppt

分治算法 将较大规模的问题分解成几个较小规模的子问题，这些子问题互相独立且与原问题相似，通过对较小规模问题的求解，然后组合各部分的解，从而得到对整个问题的求解。例如：二分查找、快速排序、归并排序、循环比赛、残缺棋盘、一元三次方程求解都可以通过分治算法实现。 算法基本思想： 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。 算法基本思想： 对于这类问题，我们往往先把它分解成几个子问题，这些子问题互相独立且与原问题相似，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。 算法基本思想： 如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。 分治法的一般步骤 　　 1）分解，将要解决的问题划分成若干规模较小的同类问题； 　　 2）求解，当子问题划分得足够小时，用较简单的方法解决； 　　 3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 算法的过程（通过二分法为例、利用递归实现）： Begin If ①问题不可分then ②返回问题解 Else begin ③从原问题中划出含一半运算对象的子问题1 ④递归调用分治法过程，求出解1 ⑤从原问题中划出含另一半运算对象的子问2 ⑥递归调用分治法过程，求出解2 ⑦将解1、解2组合成整个问题的解。 End； End; 快速排序法 procedure qsort( l,r:longint); Var i,j,m,p,k:longint; begin m:=a[random(r-l)+l]; i:=l;j:=r; repeat while a[i]m do inc(i); while a[j]m do dec(j); if i=j then begin p:=a[i]; a[i]:=a[j]; a[j]:=p; inc(i); dec(j); end; until ij; if lj then qsort(l,j); if ir then qsort(i,r); end; 例题7.2 用分治算法实现二分查找：有10000个已经从小到大排序好的数据，输入一个数x，判断它是否在这10000个数中。 练习 求余运算9701 小车问题9703 * 方法1 任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。 方法2 将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。 方法3 分析 上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里? 方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。 分治的应用（求方程的根） 例题1： 一元三次方程求解 有形如：ax3+bx2+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 分析 如果精确到小数点后两位，可用简单的枚举法：将x从-100.00 到100.00（步长0.01） 逐一枚举，得到20000个 f(x)，取其值与0最接近的三个f(x)，对应的x即为答案。而题目已改成精度为小数点后4位，枚举算法时间复杂度将达不到要求。 直接使用求根公式，极为复杂。加上本题的提示给我们以启迪：采用二分法逐渐缩小根的范围，从而得到根的某精度的数值。 具体方法如下： 分析 A、当已知区间(a,b)内有一个根时，用二分法求根，若区间(a,b)内有根，则必有f(a)·f(b)0。重复执行如下的过程： (1)若a+0.0001b或f((a+b)/2)=0，则可