C语言-二分法及其应用举例.pptx

二分法及其应用举例《C语言程序设计》 夏 银2018.11.141情境导课 概念生成情境导课 概念生成一位商人有8枚金币，其中有1枚假金币(质量略轻)，你能用天平(不用砝码)将假金币找出来吗？情境导课 概念生成需要称几次，能找出假金币？情境导课 概念生成八枚金币中 有一枚略轻情境导课 概念生成情境导课 概念生成我在这里情境导课 概念生成情境导课 概念生成情境导课 概念生成我在这里情境导课 概念生成情境导课 概念生成哦，找到了啊！情境导课 概念生成二分法的定义对处理对象（数据或者具体的物）不断取中间点，将范围一分为二，再经比较，按需要留下其中一个小范围，如此往复，逐步逼近目标的方法叫二分法，也叫对分法。2应用举例 算法探究应用举例 算法探究1.采用二分法在给定的有序数组{0,2,3,5,6,8,9,10,11,15}中查找用户输入的值，并显示查找结果。请填写适当的符号或语句，使程序实现其功能。如输入11输出为：找到位置为8如输入2输出为：找到位置为1如输入4输出为：4未找到应用举例 算法探究算法探究 数组a[10]K=1101234567890235689101511lowhighmid应用举例 算法探究算法探究 数组a[10]K=201234567890356891011152lowhighmid应用举例 算法探究算法探究 数组a[10]K=401234567890235689101115lowhighmid应用举例 算法探究C语句流程图语言描述low=0;high=9;mid=(low+high)/2;while(low=high){if(a[mid]==k) {…;find=1;break;} if(a[mid]k) high=mid-1; else low=mid+1; mid=(low+high)/2;} low=0;high=9;mid=(low+high)/2先假设最小的数组下标low的值是0最大的数组下标high值为9取中点，得中间的数组下标mid值为（0+9）/2当low=high时比较a[mid]和要找的值k是否相等，如果相等，即输出下标、做标记、程序结束如果a[mid]k 将最大数组下标high的值改为mid-1 重新计算mid的值否则 将最小数组下标low的值改为mid+1 重新计算mid的值low=highif(a[mid]==k){…;find=1;break;} if(a[mid]k) high=mid-1; else low=mid+1; mid=(low+high)/2;应用举例 算法探究main(){ int a[10]={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,k); while (low=high) { if(a[mid]==k) {printf(找到位置为：%d\n,mid+1); find=1;break; } if(a[mid]k) high=mid-1; else low=mid+1; mid=(low+high)/2; } if(find==0) printf(%d未找到\n,k);}程序实现 3程序练习 知识内化程序练习 知识内化2.用二分法在1到2的范围内求方程2^x+3*x-7=0的根。（精确度为1e-5）算法探究函数f(x)=2^x+3x-7对应的函数值表:x0123456f(x)-6-2310214075两个问题：(1)你能找到这个函数的零点所在的某个区间吗？(2)能否找到什么方法一步一步缩小这个区间，使区间端点越来越逼近函数的零点，进而求得方程的根（函数f(x)零点)的近似值？-1-2-3-4-5-6-7程序练习 知识内化y10.50x11.21.41.61.82-1-2-3-4-5-6-7程序练习 知识内化1.5y程序练习 知识内化11.250.50x11.52-1-2-3-4-5-6-7程序练习 知识内化y10.51.3750x1.2511.52-1-2-3-4-5-6-7程序练习 知识内化y10.51.43750x11.521.375-1-2-3所以方程2^x+3*x-7=0 的根近似解可以取1.433189-4-5-6-7#includestdio.h#includemath.hmain(){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