【教师原创整理】江苏省南通市2015届高三数学总复习优秀资源课件第16讲算法

第16讲算法江苏省南通中学主要内容一、聚焦重点流程图，基本算法语句．三、廓清疑点“输出”一定是n吗?二、破解难点当型和直到型两种循环结构与循环语句．聚焦重点：流程图基础知识四种图框类型输入、输出框处理框判断框起止框流程线问题研究数据存储与赋值基本知识数据存储每一个变量对应一个存放的单元赋值直接覆盖原来单元中的任何数据经典例题1例1设计交换两个变量x，y值的一个算法，并画出流程图．思路分析思路1：x←y，y←x思路2：使用中间量辅助．未弄清数据存储的原理，错误！例1设计交换两个变量x，y值的一个算法，并画出流程图．求解过程S1p←x（说明：寄存x到p的位置）S2x←y（说明：将x换成y）S3y←p（说明：将存在p处的值赋给y）开始p←xx←yy←p结束回顾反思（2）思维误区：直接交换．（1）基本策略：中间量过渡．经典例题2例2设计求解关于x的方程0ax+b=的一个算法（用流程图表示）．思路1：用顺序结构，直接输出bxa即可．思路分析思路2：按a,b是否为0分类讨论，用选择结构对各种情况分别输出结论．误认a≠0例2设计求解关于x的方程0ax+b=的一个算法（用流程图表示）．求解过程开始a=0b=0输出“解集为R”输出“解集为φ”输出xbxa结束YYNN确定性语句必不可少例2设计求解关于x的方程0ax+b=的一个算法（用流程图表示）．回顾反思（1）思想方法：分类讨论（3）思维误区：直接用顺序结构求解（4）思维瑕点：遗忘判断框外流程线上的“Y”和“N”（2）解题策略：用流程图表示方程的求解过程聚焦重点：基本算法语句赋值语句：x←1，x←y基础知识IfAThenBElseCEndIf同列同行输入语句：Readx,Reada，b输出语句：Printx，Printa，b条件语句：不能用“=”问题研究如何用条件语句“If-Then-Else”表示分段函数？经典例题3例3已知函数111111,x,y=x,x,,x,≤≤试用伪代码写出根据输入的x的值计算y值的一个算法．思路分析思路1：每一个条件独立使用一次If进行判断．思路2：使用条件语句“If-Then-Else”的嵌套结构．Ifx-1Theny←-1If-1≤x≤1Theny←xIfx1Theny←1判断次数多计算量大例3已知函数111111,x,y=x,x,,x,≤≤试用伪代码写出根据输入的x的值计算y值的一个算法．求解过程ReadxIfx-1Theny←-1ElseIfx≤1Theny←xElsey←1EndIfEndIfPrinty无需-1≤x≤1，运行到Else分支时已经满足x≥-1EndIf与If一一对应分行书写回顾反思（2）解题方法：求分段函数的函数值的算法应使用选择结构，如分为两段以上，应使用嵌套结构（1）解题策略：合理使用嵌套结构（3）思维瑕点：嵌套If语句中重复判断破解难点:循环结构与循环语句问题研究如何使用当型循环与直到型循环?如何选用While语句，Do语句，For语句?基础知识当型循环pAYN先判断后循环条件为真循环直到型循环先循环后判断条件为真退出循环pAYN基础知识当型语句While…EndWhileWhilep循环体EndWhile当型循环直到型语句Do…EndDoDo循环体UntilpEndDo直到型循环ForIFrom“初值”To“终值”Step“步长”循环体EndForFor…EndFor直到型循环经典例题4例4设计计算1×2×3×…×99的一个算法（用伪代码表示）．思路分析例4设计计算1×2×3×…×99的一个算法（用伪代码表示）．思路1：逐行书写．思路2：用While语句．思路3：用Do语句．过于繁琐，不适合思路4：用For语句．循环次数有限，均适合求解过程I←1存放乘积结果计数变量不惟一，I100也可以追踪WhileS←S×II←I＋1EndWhileS←1PrintSI≤99解法1（思路2）改为2？求解过程解法2（思路2）I←1不惟一，I99也可以WhileI←I＋1S←S×IEndWhileS←1PrintSI≤98求解过程解法3（思路2）I←0S←1WhileI≤EndWhilePrintSI←I＋1S←S×IS←S×II←I＋1要注意初始值错误98求解过程解法4I←1S←1DoS←S×II←I＋1UntilEndDoPrintS不惟一，I≥100也可以，与While语句中条件的关系I99求解过程解法5S←1ForIFrom1To99Step1S←S×IEndForPrintS赋初值循环体I←I+1简洁，经济回顾反思（1）通性通法：追踪，归纳．（2）思路比较：思路2、思路3能对任何条件进行判断，思路4实际上是在只对计数变量有限制的情况下对思路3的简化．变题1用循环语句描述计算数列21{}2nnn的前100项和的一个算法．思路求数列前100项的和，可以使用循环语句，由于循环次数确定，故使用For语句描述．S←0FornFrom1To100S←S+(n+1)/(n*n+2n)EndForPrintS循环体中使用的语句S←S+an引申变化1说明Fibonacci数列，121aa，对于任意的正整数n，都有21nnnaaa．思路数列求第99项，可以使用循环语句，由于循环次数确定，应使用For语句描述．引申变化2变题2用循环语句描述求Fibonacci数列第99项的一个算法．求解过程变题2用循环语句描述求Fibonacci数列第99项的一个算法．a←1b←1ForIFrom3To99c←a＋ba←bb←cEndForPrintc从第3项起21nnnaaa后移一次为下次循环作准备廓清疑点:输出结果问题研究For语句在使用中虽然很经济，但在解决待求循环次数的问题中无法使用．对于这类问题，常常使用Do或While两种语句，尤其以使用While语句居多，那么这种循环中最终的输出结果是什么呢？方法扫描1．“追踪”：对每次运行时各个变量的情况进行研究，从而判断程序是否按照设计思路运行.常见验证算法设计的方法：2．猜测检验：为了验证程序的合理性，可以取特殊值对结论验证.经典例题5例5用循环语句描述求使1×3×5×…×≥106成立的最小正奇数的一个算法．思路分析例5用循环语句描述求使1×3×5×…×≥106成立的最小正奇数的一个算法．思路1：用For语句描述ForIFrom3ToStep2S←S×IEndFor无法确定思路2：用While语句描述求解过程S←1I←1WhileS1000000S←S×II←I＋2EndWhile解法1由于无法预知结果，不妨设15为满足条件的输出值，即1×3×5×…×15≥1061×3×5×…×13106追踪S和I两个变量变化过程SI11×13×35×57×……×1315×1517最后修正PrintII←I-2求解过程S←1I←1WhileS1000000I←I＋2S←S×IEndWhilePrintI解法2由于无法预知结果，不妨设15为满足条件的输出值，即1×3×5×…×15≥1061×3×5×…×13106追踪S和I两个变量变化过程IS113×35×57×7…×…13×1315×15最后检验过程对比S←1I←1WhileS1000000S←S×II←I＋2EndWhileI←I-2PrintI解法1S←1I←1WhileS1000000I←I＋2S←S×IEndWhilePrintI解法2回顾反思（1）基本方法：①追踪．②猜测检验．（2）方法比较：解法1与解法2主要是在循环体的语句先后顺序上不同，导致结果不同，两种方法都比较常见，但要检验．（3）思维误区：忽视对于结果的检验．总结提炼知识与内容一、聚焦重点流程图，基本算法语句．三、廓清疑点“输出”一定是n吗？二、破解难点当型和直到型两种循环结构与循环语句．总结提炼思想与方法（2）程序化思想（复杂问题简单化，简单问题程序化）（1）程序模拟运行：追踪（3）辩证思维（来源于细心观察、分析）再见同步练习1．根据下面的伪代码写出对应的函数：ReadxIfx0Theny←x+1ElseIfx1Theny←x+2Elsey←x+3EndIfEndIfPrinty同步练习2．用循环语句描述求数列{}1n的前50项的和的一个算法．3．用循环语句描述求满足使1111++++323n成立的最大正整数n的一个算法．4．用循环语句描述输入50个数据后输出其中最大值的一个算法．参考答案1,0,2,11,3,1.1.≤≥xxyxxxx2．S←0ForIFrom1To50S←S+1/IEndForPrintS参考答案S←1I←1WhileS3S←S+1/II←I＋1EndWhileI←I-2PrintI3.4．S←0ForIFrom1To50ReadxIfSxThenS←xEndIfEndForPrintS