算法案例名师获奖

算法案例（第3课时）重点难点重点：理解区间二分法的意义；学会分析类似的问题；通过案例分析，体会算法思想，难点：理解二分法的算法思想和算法表示学习要求1．理解区间二分法的意义,二分法主要是采用了循环结构处理问题要会分析类似的问题．2．能由流程图分析出期所含有的结构并用为代码表示出相应的算法．语句的认识及其他语句的进一步熟悉．【课堂互动】问题：用区间二分法写出方程在区间[1，]内的一个近似解（误差不超过）的一个算法．算法设计思想：令函数.如图，如果估计出方程在某区间内有一个根，就能用二分法搜索求得符合误差限制的近似解．取[a，b]的中点，如果f()=0，则就是方程的根；否则判断根在的左侧还是右侧，如果在左侧，就用[a，]代替区间[a，b]．如果在右侧，就用[，b]代替区间[a，b]，如此循环下去，直到|a-b|<(c是约定的误差范围，本例中为时终止，此时≈．算法步骤：S1取[a，b]的中点，将区间一分为二；S2若，则就是方程的根；否则判断根在的左侧还是右侧：若＞0，则，以代替a；若＜0，则，以代替b；S3若<c，计算终止，此时≈，否则转S1．【流程图】＜0＜0开始Y结束输入a，b，c←←输出a←b←<cNYNYN【伪代码】代码1:Reada,b,cWhileAndIf<0ElseEndIfEndWhilePrint代码2:Read20304050IfThenGoTo12060IfThen7080Else90100EndIf110IfThenGoTo20120Print【追踪训练】开始Y结束输入a，b，c←←输出a←b开始Y结束输入a，b，c←←输出a←b←<cNYNYN＜0【解】由图像可知方程有一个根在[1，2]内．a←1b←2c←While≥c←(a+b)/2←←If=0ThenExitWhileIf＜0Thenb←Elsea←EndIfEndWhilePrint流程图如下:分层训练1.阅读下列代码，写出该代码的运行结果p←20m←2dop←p-mm←m+3Untilm>pPrintm思考运用2.设计求解不定方程（）的一个算法，（提示：可用循环语句或条件语句）3.判断某年是否为闰年，要看此年份数能否被4整除，但又不能被100整除；或者看此年份数能否被400整除．画出上述算法的流程图，并写出伪代码．4.函数与有三个交点（x1，y1），（2，4），（4，16），其中-1＜x1＜0．试用二分法求出x1近似值（误差不超过）．5、求满足不等式：1×2×3×┅×I<10000的最大正整数I，写出代码．[来源:..]6、求出平方数小于1000的所有正整数的和，并写出代码．探究拓展：7.要判断一个数x是否为质数，我们可以把它分别除以从2到x-1的每一个整数，如果都除不尽，则x为质数．要判断a是否能被b整除，只要看a/b是否等于Int(a/b),若相等则能整除．下面是寻找3~100之内质数的一个算法的伪代码：10ForxFrom3To10020.orIFrom2Tox-130IfInt(x/i)=x/iThenGoTo1040EndFor50Printx60EndFor实际上，上述算法的运算次数较多，可以加以改进，首先，偶数不可能是质数，因此第1行的步长可改为2，其次，第2行中的x-1可以改为(为什么?)．写出改进后的伪代码，你有寻找质数更好的方法吗？[来源:.]8.满足方程的一组正整数称为勾股数或商高数，试设计一个满足a≤