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

第十三章初步算法13.1流程图一、知识指导1.流程图：由一些画框和带箭头的流程线组成，其中画框代表各种操作的类型，画框中的文字和符号代表操作的内容，带箭头的流程线代表操作的顺序。2.算法的三种基本逻辑结构：序列结构、条件结构和循环结构。3.根据不同的待遇条件，流通结构分为两种：直到循环：循环体执行一次后，判断控制循环条件，不满足条件时执行循环体。如果条件满足，停止。如图13-1-3所示，首先执行方框a，然后判断给定条件是否为假，如果为假，则执行方框a，并重复直到为真。当(同时)循环：在执行每个循环体之前判断控制循环条件，当条件满足时执行循环体，当条件不满足时停止循环。如图13-1-4所示，当给定的条件为真(“真”)时，反复执行框a操作，直到条件为假，循环才停止。图13-1-1图13-1-2二、难点知识分析1.“算法”没有精确的定义。教科书只描述它。该算法具有以下特点：(1)有限性：算法的步骤是有限的，必须在有限操作后停止，而不是无限的。(2)确定性：算法的每个步骤和序列都应该是确定的。(3)有效性：算法的每一步都必须有效。2.绘制流程图时注意以下几个方面：(1)使用标准图形符号。(2)流程图通常从上到下、从左到右绘制。(3)除了判断框，大多数流程图符号只有一个入口点和一个出口点。判断框有独特的符号，有多个出口点。(4)有两种类型的判断框。一种类型的判断框有“是”和“否”两个分支，并且只有两个结果。另一个是多分支判断，有几个不同的结果。(5)图形符号中描述的语言应该非常简洁明了。3.算法的三种逻辑结构的几种解释：(1)序列结构是最简单的算法结构。语句和语句以及框和框是从上到下执行的。流程图中的实施例是从上到下连接流程线，并依次执行算法步骤。(2)条件结构可以有多个判断框。(3)循环结构是在一定条件下终止循环，这需要条件结构来判断。在循环结构中，有一个计数变量和一个累加变量。计数变量用于记录循环数，累加变量用于输出结果。计数变量和累加变量通常同步执行，一次累加，一次计数。三、经典范例指南示例1众所周知，三个单元存储变量的值，尝试给出一种算法来依次交换、的值(即取值、取值、取值)，并画出流程图。错误的解决方案：第一步第二步第三步流程图是图13-1-3错误原因：没有理解赋值的含义，以上算法做的，都取值。举一个生动的例子：有蓝色和黑色的墨水瓶，但是现在蓝色的墨水被放进黑色的墨水瓶，而黑色的墨水被错误地放进蓝色的墨水瓶。请设计一个算法来解决这个问题。对于这个非数值问题的算法设计问题，应该首先建立一个过程模型，并按照过程设计步骤完成算法。我们不能直接交换两个墨水瓶里的墨水，因为两个墨水瓶里都是墨水，直接交换是不可能的。正确的解决方案应该是：S1拿起一个空墨水瓶，把它调成白色；S2，将黑色墨水瓶中的蓝色墨水注入白色墨水瓶；S3，将蓝色墨水瓶中的黑色墨水装入黑色瓶子中；S4，将白色瓶中的蓝色墨水装入蓝色瓶中；S5交换结束。积极的解决方法：步骤1 首先将的值赋给变量，然后存储的单位可用于其他目的步骤2 再次将的值赋给，则存储的单位可用于其他目的步骤3 也将的值赋给，则存储的单位可用于其他目的第4步最后将的值赋给三个变量，交换的值流程图是图13-1-4注释：在计算机中，每个变量都有一个存储单元。为了达到交换的目的，需要一个单元来存储中间变量。示例2已知三个数字，尝试给出一个算法，找出三个数字中最大的一个，并画出算法的流程图。解决方案：流程图是图13-1-5备注：条件结构可以包含多个判断框，判断框中的内容应简洁、准确、清晰。这个话题也可以分别用两个判断框来表达第一个判断框中的两个条件，两者之间的比较也很清楚。如果找到100个数的最大值或最小值的问题改变了，选择这种方法就更复杂了。即使假设第一个数的最大(最小)数，第一个数也可以与下一个数进行比较，如果下一个数较大(较小)，则进行交换，最后的第一个数是最大(最小)值。注释：根据过程的相似性，求和可以用循环结构代替序列结构来实现。示例3绘制计算值的算法流程图。解决方法：这是一个求和问题。设计算法可以在循环结构中实现。然而，应该注意的是，奇数项是正符号，偶数项是负符号。想法1:使用-1的奇偶幂(使用循环变量)来解决正负符号问题；图13-1-6图13-1-7第二个想法是使用选择结构来总结奇数和偶数项。图13-1-8思路3:它可以简化为一个算术级数求和问题，结果可以很容易地通过使用循环结构获得。示例4设计了一种算法来寻找保持不变的最小正整数的值。解决方案：流程图是图13-1-9注释：这个问题仍然是一个检验求和循环结构应用的问题。需要强调的是求和语句的表达方法。如果问题被改变以找到所建立的最大正整数的值，输出值应该被注意。示例5给定任何大于1的整数n，尝试设计一个程序或步骤来判断n是否是质数。解决方案：算法是：S1判断n是否等于2，如果n=2，则n为素数；如果n2，S2被处决S2依次检查因子是否是2 n-1，也就是说，n的个数被精确地除了。如果有这样一个数，n不是质数；如果没有这样的数，那么n就是质数。备注：要验证它是否是质数，我们必须首先对质数的基本含义进行深入分析：(1)质数是大于1的整数，只能被1和它本身整除。(2)为了判断大于1的整数n是否是质数，仅根据定义，n被小于该整数的数移除。如果它只能被1整除，不能被其他整数整除，那么这个数就是质数。图13-1-10示例6设计一个算法来近似无理数。分析：无理数的近似值可视为方程的正近似根，因此该算法的实质是设计一种算法来寻找方程的近似根。其基本方法是用二分法求解方程的近似解。解决方案：假设近似根和精确解之间的差值的绝对值不超过0.005，算法：订购S1。因为，因此S2顺序，判断它是否为0，如果是，m是请求；如果不是，继续判断它是大于0还是小于0。S3如果0，那么；否则，命令。S4，判断条件是否成立，如果成立，两者之间的任何值都是满足条件的近似根；如果没有，返回第二步。注释：方程近似解的二分法算法是一个重要的算法案例，将在第三节详细阐述。四、典型练习指导练习1.给定两个单元分别存储变量值和，变量交换的算法是()。A.S1S1S1S1S2S2S2S2S3S31.以下流程图中的错误是()图13-1-11A.无赋值b .循环结构错误c.s .的计算不正确，d .判断条件无效。3.将“调用”过程描述为一个算法，它可以表示为，从而表明该算法具有以下特征。4.一种求直线斜率的算法(它是常数，同时不是0)在的流程图中，判断框中应该填写的内容是5.3个正实数，设计算法判断三边三角形和三边三角形是否存在，并绘制给出了该算法的流程图。6.一群士兵带着鳄鱼来到一条深河的左岸。只有一艘小船和两个孩子。这艘船只能载两个孩子或一名士兵。试着设计一个算法，把一群士兵摆到另一边，用流程图展示这个算法。13.2基本算法语句一、知识指导1.赋值语句由符号“”表示，这意味着将的值赋给，其中是一个变量、一个变量或同一类型的表达式。2.条件语句有两种主要形式：“行If语句”和“块If语句”。“行如果语句”的一般形式是：如果是A，那么是B，。一行If语句必须写在一行中，方括号中的Else部分可以默认。“块If语句”的一般格式是：如果是，那么B其他C结束于“然后”部分和“否则”部分是可选的，但是不能保存块If语句的退出“结束”。3.循环语句有两种主要类型：For语句和While语句。当周期数确定后，可以用“For”语句来表示。“for”语句的一般形式是：对于我从“初始值”到“步长”.结束上面“For”和“End for”之间的缩进步骤称为循环。当无法确定周期数时，可以使用“While”语句来实现周期。“同时”语句的一般形式是：而甲结束时其中a表示判断执行周期的条件。上面的“同时”和“结束时”之间的缩进步骤称为循环。二、难点知识分析1.一些条件语句可以没有“否则”分支，即当条件满足时执行B，否则不执行任何操作。条件语句也可以嵌套。当嵌套条件语句时，编写应该是分层的。例如：如果是，那么B否则，如果C那么D其他E结束于2.“for”语句是在执行过程中先操作后判断。“虽然”语句的特点是“预先测试”，即先判断后执行。如果初始条件没有建立，循环体的内容将不会一次执行。任何需要重复处理的问题都可以通过这个预测试循环来实现。三、经典范例指南例1以下程序的结果如下。如果是5，那么如果4，那么如果是3，那么打印误解：8 7=15错误原因：错误地认为在一个程序中只执行一个条件语句与在一个条件语句中只选择一个分支相混淆。如果A然后B否则C满足条件A，则执行B；否则，c、b和c是这个条件语句的分支，在这个程序中省略了Else部分。积极的解决方案：这里有三个条件语句。每个条件语句都是独立的，所有三个条件都是真的，所以它们是按顺序执行的。结果是8 7 6 6=27。示例2以下伪代码的效果是10岁时结束时间目标误解：执行10个周期错误原因：将For语句与While语句混淆。For语句中的步长会导致循环变量不断变化，而While语句不会。积极的解决办法：无限循环继续下去，因为这里总是0，条件 总是可以满足的，所以它是一个死循环。点评：“死循环”是设计循环结构的一大禁忌。这个问题可以改变初始值或为每个周期增加一个值。示例3以下程序在运行时的输出是()正在结束时打印序列号目标误解：在第一个周期，我得了2分，S得了4分；在第二个循环中，我得到3，S得到4=13。在第三个循环中，我得到4，S得到13=29。在第四个周期，我得了5分，S分。因此，循环终止，输出S为54。正解：由于在循环中的每个循环之后，s被赋值为0，所以只有最后一个循环中的s的值满足条件，也就是说，在那个时间，示例4使用语句描述寻找构成集合的最大正整数的算法过程。解决方案：正在结束时打印注释：这个问题中容易出错的部分是输出值。根据While循环语句的特点，它当时跳出了循环。如果此时的值是该时间的最小整数，那么最大的整数应该是前一个奇数。例5众所周知，当时，当时，当时，通过算法获得的值被设计。解决方案：读取x如果是这样否则，如果然后其他结束于目标注释：嵌套的If语句