算法案例3

楚水实验学校高二数学备课组算法案例广义地说：为了解决某一问题而采取的方法和步骤，就称之为算法。算法的概念:一般而言，对一类问题的机械的、统一的求解方法称为算法。知识回顾流程图：是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。流程图的概念已学过的伪代码中的几种基本算法语句:(1)赋值语句:变量←表达式或变量或常数．(2)输入语句:Reada,b(3)输出语句:(4)条件语句:Printa,bIfAThenBElseCEndIf当型语句:Whilep循环体Endwhile直到型语句:Do循环体UntilpEndDo循环语句伪代码中的:pAYNpAYN当循环的次数已经确定，可用“For”语句表示．“For”语句伪代码格式：ForIFrom“初值”To“终值”step“步长”……EndFor例1用二分法求方程x2－2x－1＝0的近似解（精确到0.1）．－1－1123xyO首先画出函数f(x)＝x2－2x－1的图象，从图象上可以发现：方程x2－2x－1＝0的一个根x1在区间(－1，0)内，另一个根x2在区间(2，3)内．据函数图象，我们发现：f(2)＝－10，f(3)＝20，即f(2)·f(3)0，由二次函数的单调性表明图象在区间(2，3)内仅穿越x轴一次，即方程在区间(2，3)内有惟一解．可以将区间一分为二，使包含根的区间长度缩小下面计算2，3的平均值(以下称之为区间的中点)2.5所对应的函数值f(2.5)，并进一步缩小根所在的区间．f(2.5)＝0.250，即f(2)·f(2.5)0，故近似解在区间(2，2.5)内．通过依次取区间中点的方法，将根所在的区间逐步缩小，并列出表格：区间区间中点的值中点对应的函数值(2，3)2.50.25(2，2.5)2.25－0.4375(2.25，2.5)2.375－0.10938(2.375，2.5)2.43750.066406(2.375，2.4375)直到区间两个端点值精确到0.1时的近似值都是2.4，所以方程的一个近似解为2.4．注：由于确定近似值的方法不太方便，因此用计算机实现二分法时，常常不是给出精度，而是给出误差范围！问题：如果方程f(x)＝0在某区间[a，b]内有一个根，如何利用二分法搜索符合误差限制c的近似解？S1取[a，b]的中点x0＝，将区间一分为二；2baS2若f(x0)＝0，则x0就是方程的根，转S4,否则当f(a)·f(x0)0，则x∈(a,x0)，用x0代替b,否则用x0代替a；S3若|a－b|不小于c，转S1；S4输出x0.问题：写出用区间二分法求方程x3－x－1＝0在区间[1,1.5]内的一个近似解（误差不超过0.001）的一个算法．a1b1.5c0.001Dox0(a＋b)/2f(a)a3－a－1f(x0)x03－x0－1Iff(x0)＝0ThenEndDoIff(a)f(x0)＜0Thenbx0Elseax0EndIfUntil|a－b|＜cEndDoPrintx0若是,则m为所求;探究:画出用二分法求方程x2-2=0的近似根(精确度为0.005)的程序框图.算法分析:第一步:令f(x)=x2-2.因为f(1)0,f(2)0,所以设a=1,b=2.第二步:令,2abm判断f(m)是否为0.若否,则继续判断f(a)(m)大于0还是小于0.第三步:若f(a)(m)0,则令a=m;否则,令b=m.第四步:判断|a-b|ε是否成立?若是,则a或b为满足条件的近似根;若否,则返回第二步.否是是否f(a)f(m)0?程序框图开始f(x)=x2-2输入精确度ε和初值a,b2abmf(m)=0?am否bm|a-b|ε?122输出a和b结束输出m313是例编写一个求的近似值的算法，要求精确度不超过0.0001，写出其伪代码.3