算法案例3二分法.pptx

算法案例(3)二分法求近似解 现有一商品，价格在08000元之间，采取怎样的策略才能在较短的时间内猜出正确的答案？第一步：报“4000”；第二步：若主持人说“高了”（说明答案在14000之间），就报“2000”，否则（答数在40008000之间）报“6000”；第三步：重复第二步的报数方法，直至得到正确结果。如何赋值 从第二步算法分析：答案x*肯定在两个端点a,b之间，只是这两个端点a,b不断变化，我们可以用赋值的手法使两个端点a,b相对固定,则x*=（a+b）/2 第一步：可以给指定的区间端点为a,b（a0，则x*(x0,b),以x0代替a；若f(a)*f(x0)0，则x*(a,x0),以x0代替b；S3 若|a-b|c,计算终止,此时x*x0，否则转S1流程图与伪代码 10 Rend a,b,c20 x0(a+b)/230 f(a)a3-a-140 f(x0)x03-x0-150 If f(x0)=0 Then Go To 12060 If f(a)f(x0)0 Then70 b x080 Else90 a x0100 End If110 If|a-b|c Then Go To 20120 Print x0输入输入a,b,c输出输出x0bx0ax0f(a)a3-a-1f(x0)x03-x0-1X0(a+b)/2|a-b|cf(a)f(x0)0f(x0)=0YNYNY数学理论 用二分法设计求方程f(x)0的近似根算法的基本步骤：1确定近似根所在的基础区间a,b和近似根的精确度c；2.求有根区间的中点,判断是否满足精度要求；3求区间端点的函数值，f(a),f(b)4.判断f(a)f(b)的符号，改变有根区间的下限或上限5循环求近似根6输出根的近似值巩固运用 例2 将以二分法求方程x2-20的近似根（精确度为0.005）的一个算法补充完整 解：Sl 令f(m)x2-2，因为f(1)0，所以设x1l，x22 S2 令m ，判断f(m)是否为0。若是，则m为所求；若否，则继续判断 S3 若 ，则x1m；否则令x2m S4 判定 0.005是否成立。若是，则x1,x2之间的任意取值均为满足条什的近似根，若否，则 例3仟意给定一个大于的正整数，设计一个算法求的所有因数 依次以（）为除数去除，检查余数是否为，若是，则是n的因数；若不是，则不是的因数；在的因数中加入1和n；输出的所有因数回顾反思