高三数学典型例题解析：第十三章算法初步

第13章算法初步13.1流程图一、知识地图1.流程图：由带有边界和箭头的流线组成，用于指示各种操作的类型。图形边框中的文本和符号表示操作的内容，带箭头的流线表示操作的顺序。算法的三个基本逻辑结构：顺序结构、条件结构和循环结构。循环结构根据条件分为两类。至(until类型)循环：在运行循环后确定控制循环条件，并在不满足条件时运行循环。如果满意，则停止。图13-1-3，首先运行a框，然后检查指定条件是否为假，如果为假，则执行a以重复操作，直到变为真。类型(while类型)循环：在执行每个循环之前确定控制循环条件，如果满足条件，则执行循环，如果不满足条件，则停止。图13-1-4，如果指定的条件为真(“true”)，则重复执行框操作，直到条件为“false”。图13-1-1图13-1-2二、困难的知识指南1.“算法没有准确的定义，教科书只有说明性的说明，算法具有以下特点：(1)有限性：一种算法的步骤是有限的，在有限的操作后必须停止，不能无限。(2)确定性：算法的所有步骤和顺序都必须确定。(3)有效性：算法的每个阶段都必须有效。绘制流程图时要注意以下方面：(1)使用标准图形符号。(2)流程图通常从上到下、从左到右绘制。(3)除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有唯一的符号，该符号具有两个或更多出口点。(4)判断框分为两类，只有判断框“是”和“否”两种类型的判断和两种结果。另一类是有多种结果的多种判断。(5)图形符号中描述的语言必须非常简洁明了。(。算法的三种逻辑结构的几点说明：(1)顺序结构是最简单的算法结构，语句和语句之间，框和框之间有自上而下的顺序。流程图的实现是自上而下连接进程行，按顺序执行算法步骤。(2)一个条件结构中可能有多个判断框。(3)周期结构在某些条件下结束周期需要条件结构。周期结构有系数变量和累积变量。系数变量记录周期数，累计变量术语输出，系数变量和累计变量通常累计一次，计算一次。三、经典案例指南示例1知道存储变量、的值的三个单位，提供按顺序交换的值(值、值、值)的算法，并绘制流程图。解决错误：第一步第二步第三步流程图如下所示图13-1-3错误原因：不理解分配的含义，是以上算法生成的值。图像示例：有一个蓝色和黑色的墨水瓶，但现在在黑色墨水瓶中安装了蓝色墨水，黑色墨水错误地装入了蓝色墨水瓶。如果需要交换，请设计算法解决这个问题。对于这些非数值问题的算法设计问题，必须首先建立过程模型，并按照过程设计阶段完成算法。两个墨水瓶都含有墨水，不能直接交换，所以不能直接交换两个墨水瓶的墨水。正确的解决方案包括：S1取空墨水瓶，将其设置为白色。S2将黑色墨水瓶的蓝色墨水装入白色瓶子。将S3蓝色墨水瓶的黑色墨水放入黑色瓶子。S4将白色瓶子的蓝色墨水装入蓝色瓶子。S5交换结束。正解：将的值赋给第一步变量。此时，可以使用保存的单位。将第二步的值指定给。此时，可以使用保存的单位。第三步将相同的值指定给。此时，可以使用保存的单位。第四步最后，将的值指定给，3个变量，的值已完成交换流程图如下所示图13-1-4意见：计算机需要为每个变量分配存储设备，为了交换目的，需要存储中间变量的单元。示例2我知道三个数字。提出三个中最大的数的算法，画出该算法的流程图。解决方案：流程图如下所示图13-1-5意见：条件结构可以包含多个判断框，判断框内的内容必须简洁、准确、明确。此外，这个问题可以用两个判断框分别表示第一个判断框内的两个条件，两个比较也很明确。如果要查找100个数字中的最大或最小数目的问题，则选择此方法会更麻烦，并且假设第一个数字与最大(最小)和下一个数字比较，如果第一个数字较大(较小)，则第一个数字可以交换，最后一个数字是最大(最小)值。意见：根据流程的类同性可用周期结构，而不是聚合时的顺序结构。示例3绘制所需值的算法流程图。解决方案：这是一个可以使用迭代结构实现设计算法的求和问题。但是，奇数项目是正数，偶数项目是负数符号。想法1:要解决正负符号问题，请使用-1的奇偶校验平方(使用循环变量)图13-1-6图13-1-7想法2:使用选择结构划分奇偶校验和。图13-1-8想法3:可以先转换为简洁，等价序列求和问题。使用循环结构可以轻松找到结果。示例4设计一种算法，以获得设定的最小正整数值。解决方案：流程图如下所示图13-1-9注释：这个问题还是调查合计的循环结构的使用问题，应该强调合计语句的显示方法。如果问题更改为设置的最大正整数的值，则应注意输出中的值。示例5随机指定大于1的整数n，以设计判断n是否是小数的程序或步骤。解决方案：算法如下：S1判断n等于2，如果n=2，则n是小数。如果是N2，则会执行S2S2是依次从2到n-1整数n的系数，如果有这样的数字，n就不是小数。如果没有这样的数字，n是小数。意见：要验证是否是少数，首先要深入分析少数的本质意义。(1)小数是大于1的整数，只能除以1及其本身。(2)要确定大于1的整数n是否为小数，请根据定义，以小于此整数的数去除n。如果只能被1(而不是其他整数)及其本身整除，那么这个数就是小数。图13-1-10例6设计了求不合理数近似值的算法。分析：不合理数字的近似可以看作是方程的正近似根，因此，该算法的本质是设计一种求方程近似根的算法。其基本方法是用二分法求解方程的近似解。解决方案：设置近似根和精确解的差异的绝对值不超过0.005的算法：S1命令。因为S2命令，判断是否为零，在情况下，m是要求。否则，请继续检查是否大于0或小于0。S3 0表示；否则，命令。判断S4是否为真时，之间的任意值是满足条件的近似根。否则，返回到第二步。意见：用二分法求方程近似解的算法是重要的算法实例，将在第3节详细说明。四、典型的实践练习1.如果已知两个单位分别具有变量和的值，则启用变量交换的算法为()。A.S1 B.S1 C.S1 D.S1S2 S2 S2 S2S3 S31.以下流程图中的错误为()图13-1-11A.无分配b .循环结构出错C.s的计算无效。d .判断条件不成立3.将“电话”过程描述为具有以下特征的算法：4.表示常数和非零直线斜率的算法流程图的判断框中需要填写的内容如下：5.设计了一种算法，用以确定是否存在由3个正实数、3条边组成的三角形给出了该算法的流程图。6.一队士兵来到了鳄鱼所在的深河的左边。只有一条小船和两个孩子。这艘船只能运送两个孩子或一个士兵。设计了一种将该部队穿越到另一边的算法，用流程图表示了该算法。13.2基本算法语句一、知识地图1.赋值语句用符号“”表示，“”表示将的值指定给。其中是变量，是与类型相同的变量或表达式。条件语句主要有两种形式：行If语句和块If语句。行If语句的一般形式如下：If A Then B Else C。If语句行必须写入到可以将方括号中的Else部分用作默认值的一行中。块If语句的常规格式为：If A ThenbElsecEnd ifThen和Else部分是可选的，但不能保存块If语句的出口“End if”。回圈叙述句主要有两种类型：For叙述句和While叙述句。确定循环次数后，可以使用 For 语句表示以下内容：“For”语句的一般形式如下：For I from 初始值 to step step.end for在上面的“For”和“End for”之间缩进的步骤称为循环体。如果不确定循环数是否为是，请使用“While”语句实现循环。“While”语句的一般形式如下：While A.End while其中a表示判断执行周期的条件。循环主体中在上面的“While”和“End While”之间缩进的步骤。二、困难的知识指南1.某些条件语句可以在满足条件的情况下执行，而无需执行b的“Else”分支。否则，不执行任何操作。条件语句可以嵌套，嵌套条件语句时也会创建层次结构。例如：If A ThenbElse if C ThendElseeEnd if2.“for”语句在执行过程中先操作，然后再判断。“While”语句的特点是“预测试”。也就是说，先判断后执行。如果不满足初始条件，则不一次运行循环的内容。需要重复处理的所有问题都可以使用这些预测试循环来完成。三、经典案例指南示例1以下程序的结果是。If 5 ThenIf 4 ThenIf 3 Then打印解决错误：8 7=15错误原因：在一个条件语句中仅执行一个条件语句与在一个条件语句中仅选择一个分支混淆。如果If A Then B Else C条件A满足，则执行B；否则，执行C、B和C是此条件语句的分支，此程序将跳过Else部分。正解：有三个条件语句。各条件语句是独立的，所有三个条件都成立，因此按顺序执行，结果为8 7 6=27。示例2下面的伪代码的效果是While 10End WhileEnd解决错误：运行10次循环错误原因：将While语句与For语句混淆。For语句包含更改迭代变量的步骤，而While语句不是。正解：无限循环总是零，总是“死循环”，因为它满足条件“”。注释：“死循环”是设计循环结构的一大禁忌，可以更改为这个问题的初始值或循环值会增加一个。在“示例3”下，程序运行时输出的结果为()WhileEnd while打印End解决错误：在第一个循环中，I给出2，s给出4；在第二个循环中，I被赋予3，s被赋予4=13；在第三个循环中，I被赋予4，s被赋予13=29；在第四个循环中，I被赋予5，s。因此，循环终止，输出s为54。正解：在循环内，s在每个循环后给0赋值，所以满足条件的最后一个循环s的值，也就是当时。示例4查找已建立的最大正整数的算法过程由语句说明。解决方案：WhileEnd while打印意见：这个问题输出值错误。根据While循环语句的特征，从循环跳下，此时值是时间的最小整数，最大整数必须是的第一个奇数。例5知道的时候，设计了算法，得出的值。分析：Read xIf thenElse if ThenElseEnd ifEnd注释：嵌套的If语句可以采用上述紧凑形式编写。如果不是紧凑形式，则块If语句对应于End