高中数学典型例题解析： 算法初步

1、第十三章 算法初步 13.1 流程图一、 知识导学流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序.2算法的三种根本的逻辑结构：顺序结构、条件结构、循环结构.3根据对条件的不同处理，循环结构又分为两种：直到型(until型)循环：在执行了一次循环体之后，对控制循环条件进行判断，当条件不满足时执行循环体.满足那么停止.如图13-1-3，先执行A框，再判断给定的条件是否为“假，假设为“假，那么再执行A，如此反复，直到为“真为止. 当型while型循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环

2、体，不满足那么停止.如图13-1-4，当给定的条件成立“真时，反复执行A框操作，直到条件为“假时才停止循环. 图13-1-1 图13-1-2二、疑难知识导析1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：1有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的.2确定性：算法的每一步骤和次序应当是确定的.3有效性：算法的每一步骤都必须是有效的.2. 画流程图时必须注意以下几方面： 1使用标准的图形符号. 2流程图一般按从上到下、从左到右的方向画. 3除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号. 4判断

3、框分两大类，一类判断框“是与“否两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果. 5在图形符号内描述的语言要非常简练清楚.3. 算法三种逻辑结构的几点说明：1顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.在流程图中的表达就是用流程线自上而下地连接起来，按顺序执行算法步骤.2一个条件结构可以有多个判断框.3循环结构要在某个条件下终止循环，这就需要条件结构来判断.在循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.三、经典例题导讲例1 三个单元存放

4、了变量，的值，试给出一个算法，顺次交换， 的值即取的值，取的值，取的值，并画出流程图.错解：第一步 第二步 第三步 流程图为 图13-1-3 错因：未理解赋值的含义，由上面的算法使得，均取的值.举一形象的例子：有蓝和黑两个墨水瓶，但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤完成算法. 我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：S1 取一只空的墨水瓶，设其为白色； S2 将黑墨水瓶中的蓝墨水装入白瓶中； S3

5、将蓝墨水瓶中的黑墨水装入黑瓶中； S4 将白瓶中的蓝墨水装入蓝瓶中； S5 交换结束.正解：第一步 先将的值赋给变量，这时存放的单元可作它用 第二步 再将的值赋给，这时存放的单元可作它用 第三步 同样将的值赋给，这时存放的单元可作它用 第四步 最后将的值赋给，三个变量，的值就完成了交换流程图为 图13-1-4点评：在计算机中，每个变量都分配了一个存储单元，为了到达交换的目的，需要一个单元存放中间变量.例2三个数，.试给出寻找这三个数中最大的一个算法，画出该算法的流程图. 解：流程图为图13-1-5点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条

6、件分别用两个判断框表示，两两比拟也很清晰.假设改为求100个数中的最大数或最小数的问题那么选择此法较繁琐，可采用假设第一数最大最小将第一个数与后面的数依依比拟，假设后面的数较大较小，那么进行交换，最终第一个数即为最大最小值.点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构.例3画出求的值的算法流程图.解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号. 思路一：采用-1的奇偶次方利用循环变量来解决正负符号问题； 图13-1-6 图13-1-7 思路二：采用选择结构分奇偶项求和； 图13-1-8 思路三：可先将化简成，转化为一个等差数列求和问题，易

7、利用循环结构求出结果. 例4 设计一算法，求使成立的最小正整数的值.解： 流程图为 图13-1-9 点评：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法.假设将题改为求使成立的最大正整数的值时，那么需注意的是输出的值.例5任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判断. 解：算法为：S1 判断n是否等于2，假设n=2，那么n是质数；假设n2，那么执行S2S2 依次从2n-1检验是不是的因数，即整除n的数，假设有这样的数，那么n不是质数；假设没有这样的数，那么n是质数.点评：要验证是否为质数首先必须对质数的本质含义作深入分析：1质数是只能被1和自

8、身整除的大于1的整数. 2要判断一个大于1的整数n是否为质数，只要根据定义，用比这个整数小的数去除n.如果它只能被1和本身整除，而不能被其它整数整除，那么这个数便是质数. 图13-1-10 例6设计一个求无理数的近似值的算法.分析：无理数的近似值可看作是方程的正的近似根，因此该算法的实质是设计一个求方程的近似根的算法.其根本方法即运用二分法求解方程的近似解.解：设所求近似根与精确解的差的绝对值不超过0.005,算法:S1 令.因为,所以设S2 令,判断是否为0,假设是,那么m为所求;假设否,那么继续判断大于0还是小于0.S3 假设0,那么;否那么,令.S4 判断是否成立，假设是，那么之间的任意

9、值均为满足条件的近似根；假设否，那么返回第二步.点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述.四、典型习题导练1两个单元分别存放了变量和的值，那么可以实现变量交换的算法是 . AS1 BS1 CS1 DS1 S2 S2 S2 S2 S3 S3 下面流程图中的错误是 图13-1-11 A没有赋值 B循环结构有错 CS的计算不对 D判断条件不成立3.将“打 的过程描述成一个算法，这个算法可表示为 ，由此说明算法具有以下特性 . 4. 在表示求直线，为常数，且，不同时为0的斜率的算法的流程图中，判断框中应填入的内容是 5. 3个正实数，设计一个算法，判断分别以这3个数为三

10、边边长的三角形是否存在，画出这个算法的流程图.6.一队士兵来到一条有鳄鱼的深河的左岸.只有一条小船和两个小孩，这条船只能承载两个小孩或一个士兵.试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示.13.2根本算法语句一、知识导学赋值语句用符号“表示，“表示将 的值赋给，其中是一个变量，是一个与同类型的变量或表达式.条件语句主要有两种形式：“行If 语句和“块If语句. “行If 语句的一般形式为：If A Then B Else C .一个行If 语句必须在一行中写完，其中方括号中的Else局部可以缺省.“块If 语句的一般格式为: If A Then B Else C End if

11、 Then 局部和 Else 局部是可选的，但块If语句的出口“End if不能省.循环语句主要有两种类型：For语句和While语句.当循环的次数已经确定，可用“For语句表示.“For语句的一般形式为：For I from“初值 to step“步长 End for 上面“For和“End for之间缩进的步骤称为循环体.当循环次数不能确定是，可用“While语句来实现循环.“While语句的一般形式为：While AEnd while其中A表示判断执行循环的条件.上面“While和“End While之间缩进的步骤称为循环体.二、疑难知识导析有的条件语句可以不带“Else分支，即满足条件

12、时执行B，否那么不执行任何操作.条件语句也可以进行嵌套，在进行条件语句的嵌套时，书写要有层次.例如：If A Then BElse if C Then DElse EEnd if2.“For语句是在执行过程中先操作，后判断.而“While语句的特点是“前测试，即先判断，后执行.假设初始条件不成立，那么一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现.三、经典例题导讲例1 以下程序的运行结果是 .If 5 Then If 4 Then If 3 Then Print 错解：8+7=15错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分

13、支相混淆.If A Then B Else C 假设满足条件A 那么执行B，否那么是执行C，B和C是这个条件语句的分支，而这个程序省略了Else局部.正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27.例2 下面的伪代码的效果是 While 10End WhileEnd错解：执行10次循环错因：将For语句和While语句混淆. For语句中有步长使循环变量不断变化，而While语句那么无.正解：无限循环下去，这是因为这里始终为0，总能满足条件“，故是一个“死循环.点评：“死循环是设计循环结构的大忌，此题可改变的初始值或每一次循环都

14、增加一个值. 例3下面的程序运行时输出的结果是 While End while Print SEnd 错解：第一次循环时，I被赋予2，S被赋予4；第二次循环时，I被赋予3，S被赋予4+=13；第三次循环时，I被赋予4，S被赋予13+=29；第四次循环时，I被赋予5，S被赋予.由于此时，故循环终止，输出S为54.正解：由于在循环内，每经过一次循环后S都被赋值0，因此，只要求满足条件的最后一次循环S的值，即当时，.例4用语句描述求使成立的最大正整数的算法过程.解： While End while Print 点评：此题易错的是输出值，根据While循环语句的特征当时跳出循环体，此时的值是时的最小的

15、整数，那么使的最大整数应为的前一个奇数即.例5当时，当时，当时，设计一算法求的值.解： Read xIf then Else if Then Else End if End 点评：嵌套If语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，那么需注意一个块If语句对应一个End If，不可省略或缺少. 例6设计一个算法，使得输入一个正整数，输出1！+2！+3！+！的值.写出伪代码.解：思路一：利用单循环，循环体中必须包括一个求各项阶乘的语句以及一个求和语句. Read n For I from 1 to n End For Print S 思路二：运用内外双重循环，但尤其注意的是每一次外

16、循环T的值都要从1开始. Read n For I from 1 to n For J from 1 to I End For End For Print S四 、典型习题导练1 以下的循环语句循环的次数为 For I from 1 to 7 For J from 1 to 9 Pint I+J End for End forEndA.7次 B.9次 C.63次 D.16次2运行下面的程序后输出的结果是 ，假设将程序中的A语句与B语句的位置互换，再次执行程序后输出的结果为 .While A语句 B语句End WhilePrint x,yEnd3.伪代码描述的求T的代数式是 ,求的代数式是 .

17、Read n For I from 1 to n End forPrint T,S4.运行下面程序后输出的结果为 For I from 10 to 1 step -2 Print I End forEnd 5. 将100名学生的一门功课的成绩依次输入并计算输出平均成绩. 133 算法案例一、知识导学1算法设计思想：1“韩信点兵孙子问题对正整数m从2开始逐一检验条件，假设三个条件中有任何一个不满足，那么m递增1，一直到m同时满足三个条件为止(循环过程用Goto语句实现)2用辗转相除法找出的最大公约数的步骤是：计算出的余数，假设，那么为的最大公约数；假设，那么把前面的除数作为新的被除数，继续运算，

18、直到余数为0，此时的除数即为正整数的最大公约数.2.更相减损术的步骤：1任意给出两个正数，判断它们是否都是偶数.假设是，用2约简；假设不是，执行第二步.2以较大的数减去较小的数，接着把较小的数与所得的差比拟，并以大数减小数.继续这个操作，直到所得的数相等为止，那么这个数等数就是所求的最大公约数.3二分法求方程在区间内的一个近似解的解题步骤可表示为S1 取的中点，将区间 一分为二；S2 假设，那么就是方程的根；否那么判别根在的左侧还是右侧：假设，以代替；假设，那么，以代替；S3 假设，计算终止，此时，否那么转S1.二、疑难知识导析 1表示不超过的整数局部，如，但当是负数时极易出错，如就是错误的，

19、应为-2.2表示除以所得的余数，也可用 表示.3辗转相除法与更相减损术求最大公约数的联系与区别：1都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.2从结果表达形式来看，辗转相除法表达结果是以相除余数为0那么得到，而更相减损术那么以减数与差相等而得到.4用二分法求方程近似解，必须先判断方程在给定区间上是否有解,即连续且满足.并在二分搜索过程中需对中点处函数值的符号进行屡次循环判定，故需要选择结构、循环结构，即可用Goto 语句和条件语句实现算法.三、经典例题导讲例1 ， ， ， 7=

20、 .A16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3错解：根据表示不超过的整数局部, 表示除以所得的余数,选择B.错因:对表示的含义理解不透彻,将不超过-0.05的整数错认为是0,将负数的大小比拟与正数的大小比拟相混淆.正解：不超过-0.05的整数是-1,所以答案为D.例2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于1000的整数是否为同构数.错解： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，假设相等，那么为同构数. Read x If or or Then Print x End

21、 if End 错因：在表示个位或最后两位或最后三位出现错误，“/仅表示除，y/10,y/100,y/1000都仅仅表示商.正解：可用来表示个位，最后两位以及最后三位.Read x If or or Then Print x End if End 例3?孙子算经?中的“物不知数问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15，到得出7除2的时候，就是答数.试用流程图和伪代码表示这一算法.解：流程图为： 伪代码为：10 20 30 If Then Goto 2040 If

22、Then Print Goto 8050 End if60 70 Goto 4080 End 点评：这是孙子思想的表达，主要是依次满足三个整除条件.例4分别用辗转相除法、更相减损法求192与81的最大公约数.解：辗转相除法： S1 S2 S3 S4 S5 故3是192 与81 的最大公约数.更相减损法：S1 S2 S3 S4 S5 S6 S7 S8 S9 故3 是192与81的最大公约数.点评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数，更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数. 例5为了设计用区间二分法求方程在0，1上的一个近似解误差不超过0.001的算法,流程图的各个框图如下所示,请重新排列各框图,并用带箭头的流线和判断符号“Y、“N组成正确的算法流程图,并写出其伪代码.(其中分别表示区间的左右端点) 图13-3-2流程图为 图13-3-3伪代码为10 Read 20 30 40 50 If Then Goto 12060 If Then70 100 End if80 Else90 100 End if110 If Then Goto 20120 Print 130 End 点评：二分法的根本思想在必