对分查找的具体运用.doc
文本预览下载声明
对分查找的具体运用
上海外国语大学附属大境中学 孙克恕
【教学目标】
知识与技能:掌握对分查找的方法和步骤。
过程与方法:研究对分查找算法在求解高次方程实根等具体问题中的运用,使学生将信息科技和中学的数学、物理等知识进行有效整合。
情感态度与价值观:通过本节课的学习,让学生感受到在工作、学习和生活中无不和信息素养有关,从而培养学生热爱信息科技的情感。在对算法进行完善的过程中让学生感受到做任何事没有最好,只有更好,树立起不断完善,追求卓越的思想,并通过对我国优秀科学家的介绍,增强学生的民族自豪感。
【教学重点】对分查找方法的基本思想及其具体运用。
【教学难点】对分法的深入研究。
【教 具】投影仪
【课时安排】1课时
【教学步骤】
一、引言
猜数游戏,请一同学在黑板上写一整数(在1——100内)。
师:是1吗?生:不是。师:是2吗?生:不是?师:是3吗?生:不是。师:用这种办法能找到所要找的数吗?生:能。师:这种方法显然是不好的。下面我们换一种方法。
师:是50吗?生:不是。师:是小于50吗?生:不是。师:是75吗?
……
想想看:若是在10000以内进行查找会多几次呢?
二、对分查找的概念
请同学归纳一下,上面的猜数游戏所用到的方法和所需条件。
条件:数据是有序的。
方法:先在中间位置进行查找,并由此确定新的查找范围,新的查找范围是原先的查找范围的一半,直到找到最终结果。
三、对分查找在解高次方程中的运用
1、解题思想
对于许多高次方程是不能用因式分解来求解的,由于数轴上的点是有序的,因此我们可以用对分查找来找出高次方程在某一区间的实根。即:不断地将区间对分,使得区间中点的值不断逼近方程的根。此时又出现了一个新的问题:在给定的区间内有多少个点呢?有无穷个,既然是无穷个,那么用对分法不断的对分能分穷尽吗?显然是不能。而算法的一个特点是:算法的步骤必需是有穷的。那么我们怎么从上面这个无穷的对分中转到有穷的步骤中来呢?事实上,在物理实验中,所得到的测量值,都是一个近似值,为什么我们能用这个近似值来作为物理量的真值呢?这里有一个精度的问题,即:当测量值与真值之间的误差小于精度要求时,我们就认为这个测量值就是真值。现在我们求根也有一个精度(为0.1),当区间不断被对分后,新区间的长度的一半小于精度时就停止对分,并用此时的中点值作为方程的根。
2、实例
求三次方程4x3-52x2+169x-140=0的实根(精确到0.1)。可以先用Excel画出高次方程所对应的函数的图形,并确定方程实根的区间。
1)用Excel描出Y(X)= 4x3-52x2+169x-140的图形,由此可以确定所求三次方程在区间(1,2)、(3,4)、(8,9)各有一个实根。
2)求(3,4)区间内的实根的过程如下:
(1)取(3,4)的中点x0,x0=(x1+x2)/2=(3+4)/2=3.5,计算Y0=Y(3.5)= -14,此时区间左端点函数值Y1=Y(3)= 7,Y1*Y00,由此判断在(3,4)内的根的新区间应为:(3,3.5)(提问:新区间是怎么确定的?)。(请注意:现在我们已将根的取值范围缩小的一半。)
(2)现在区间右端点x2=3.5,Y2=Y(3.5)= -14,取(3,3.5) 的中点为新的x0,x0=(x1+x2)/2=(3+3.5)/2=3.25,现在Y0= Y(3.25)= -2.6875,Y1=Y(3)= 7,因为Y1*Y00,所以根应在(3,3.25)之间。
(3)重复上面的过程:x0=(x1+x2)/2=(3+3.25)/2=3.125,Y0= Y(3.125)=2.3828,因为Y(3)* Y(3.125)0,所以根应在(3.125,3.25)之间。
现在区间(3.125,3.25)对分后的长度=0.06250.1(精度),故我们可取区间(3.125,3.25)的中点值x0=(x1+x2)/2=(3.125+3.25)/2=3.1875=3.2作为方程在区间(3,4)内的根(精确到0.1)。
提问:为什么对分后的长度0.1(精度)时就可用此时的中点值作为方程的根?(因为这样处理最大误差不会超过对分后的长度)
课堂讨论:对程序作适当的修改后,程序的功能就又得到了提高。让学生认识到做任何事“没有最好,只有更好”,而“没有最好,只有更好,不断完善,追求卓越”应成为我们的一种追求。
3、流程图
四、对分法的深入研究
并不是所有的问题都能采用对分法。蒸馒头要想蒸得好吃、不酸不黄,就要使碱适量。假如我们现在还没有掌握使碱量的规律,而要通过直接实践的方法去摸索这个规律,怎样才能用最少的实验次数就找到最理想的结果呢?当放碱太少时,馒头不好吃,随着碱的数量逐渐增加,馒头也逐渐变好;当碱量达到某个最优值时馒头最好吃。若碱量超过这个最优值继
显示全部