C语言 二分法及其应用举例ppt课件.pptx

,C语言程序设计,二分法及其应用举例,夏 银,2018.11.14,情境导课 概念生成,1,一位商人有8枚金币，其中有1枚假金币(质量略轻)，你能用天平(不用砝码)将假金币找出来吗？,需要称几次，能找出假金币？,八枚金币中 有一枚略轻,我在这里,我在这里,哦，找到了啊！,二分法的定义对处理对象（数据或者具体的物）不断取中间点，将范围一分为二，再经比较，按需要留下其中一个小范围，如此往复，逐步逼近目标的方法叫二分法，也叫对分法。,应用举例 算法探究,2,1.采用二分法在给定的有序数组0,2,3,5,6,8,9,10,11,15中查找用户输入的值，并显示查找结果。请填写适当的符号或语句，使程序实现其功能。如输入11输出为：找到位置为8如输入2输出为：找到位置为1如输入4输出为：4未找到,11,low,high,mid,K=11,算法探究,数组a10,算法探究,数组a10,2,low,high,mid,K=2,算法探究,数组a10,low,high,mid,K=4,先假设最小的数组下标low的值是0最大的数组下标high值为9取中点，得中间的数组下标mid值为（0+9）/2当lowk 将最大数组下标high的值改为mid-1 重新计算mid的值否则 将最小数组下标low的值改为mid+1 重新计算mid的值,语言描述,程序实现,main() int a10=0,1,2,3,4,5,6,7,8,9; int low=0,high=9,mid,k,find=0; mid=(low+high)/2; printf(请输入欲查找的值：n); scanf(%d,程序练习 知识内化,3,2.用二分法在1到2的范围内求方程2x+3*x-7=0的根。（精确度为1e-5）,算法探究,函数f(x)=2x+3x-7对应的函数值表:,两个问题：(1)你能找到这个函数的零点所在的某个区间吗？(2)能否找到什么方法一步一步缩小这个区间，使区间端点越来越逼近函数的零点，进而求得方程的根（函数f(x)零点)的近似值？,1.5,1,-1,-2,0.5,1,y,x,0,-3,-4,-5,-6,-7,2,1.5,1.25,1,1.375,-1,-2,0.5,1,y,x,0,-3,-4,-5,-6,-7,2,1.5,1.25,1,1.375,-1,-2,0.5,1,y,x,0,-3,-4,-5,-6,-7,2,1.5,1.4375,所以方程2x+3*x-7=0 的根近似解可以取1.433189,程序实现,#include#includemain()float x0,x1,x2,fx0,fx1,fx2; x1=1.0;x2=2.0; fx1=pow(2,x1)+3*x1-7; fx2=pow(2,x2)+3*x2-7; x0=(x1+x2)/2; fx0=pow(2,x0)+3*x0-7; while(fabs(fx0)=1e-5) if(fx0*fx10) x1=x0; else x2=x0; x0=(x1+x2)/2; fx0=pow(2,x0)+3*x0-7; printf(the root is %6.2fn,x0 );,归纳小结 课堂延伸,4,1. 二分法的实质：,3. 二分法的应用：,通过缩小范围来靠近目标。,2. 二分法的方法：,不断取中点，达到缩小范围的目的。,辨真伪、找数据、解方程、猜价格、修电路等，做到了在较的时间内用最小的精力去解决问题。,修电路、水管、气管 某个雷电交加的夜晚，医院的医生正在抢救一个危重病人，忽然电停了。据了解原因是供电站到医院的某处线路出现了故障，维修工，如何迅速查出故障所在? (线路长10km，每50m一根电线杆）,作业：观看视频，编写一个猜数字的小游戏，同学之间分小组猜数字，看谁能用最少的次数猜对？,