第十讲 算法初步.ppt

1．算法的含义、程序框图 （1）了解算法的含义，了解算法的思想． （2）理解程序框图的三种基本逻辑结构：顺序、条件分支、循环． 2．基本算法语句 了解几种基本算法语句—输入语句、输出语句、赋值语句、条件语句、循环语句的含义． (一) 算法的含义 程序框图 1．算法的概念 （1）算法的定义：广义的算法是指完成某项工作的方法和步骤，因此我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等. 在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成 （2）算法的特征： ①确定性：算法的每一步都应当做到准确无误、“不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏” 是指缺少哪一步都无法完成任务. ②逻辑性(有序性)：算法从开始的“第一步”直到“最后一步”之间做到环环相扣.分工明确，“前一步”是“后一步”的前提， “后一步”是“前一步”的继续. ③有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行. （3）算法的描述：自然语言、程序框图、程序语言. （3）程序框图的构成 一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字. 3．几种重要的结构 （1）顺序结构 顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构. （3）循环结构 在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始，按照一定条件重复执行某一处理过程.重复执行的处理步骤称为循环体. 循环结构有两种形式：当型循环结构和直到型循环结构. ①当型循环结构，如左下图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立，返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构.继续执行下面的框图. ②直到型循环结构，如右下图所示，它的功能是先执行重复执行的A框，然后判断给定的条件P是否成立，如果P仍然不成立，则返回来继续执行A框，再判断条件P是否成立.以次重复操作，直到某一次给定的判断条件P时成立为止，此时不再返回来执行A框，离开循环结构.继续执行下面的框图. (二) 基本算法语句 如何在计算机上实现算法？ 输入语句 输出语句 赋值语句 条件语句 循环语句 循环 指的是反复地执行一个或多个步骤. 类型 固定(循环次数为已知的情形) 可变(循环次数为未知的情形) 固定的 进行固定次数的重复操作. 循环内计算或处理的数值对循环操作的次数没有影响. 可变的 重复操作,直到一个指定的条件满足. 循环次数可以变化. 算法结构总结 三种基本结构 顺序结构 分支结构 循环结构 (三) 算法案例 1．求最大公约数 （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 . （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法可以描述如下： ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r； ④判断余数r是否为0.若余数为0，则输出结果；否则转向第②步继续循环执行. 如此循环，直到得到结果为止. （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术.在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数，以少减多，更相减损，求其等也，以等数约之. 步骤： Ⅰ．任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步. Ⅱ．以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. 二、热点例题解析 题型1：算法概念 例题1．下列说法正确的是（ ） A．算法就是某个问题的解题过程； B．算法执行后可以产生不同的结果； C．解决某一个具体问题算法不同结果不同； D．算法执行步骤的次数不可以为很大，否则无法实施. 解析：答案为选项B；选项B，例如：判断一个整数是否为偶数，结果为“是偶数”和“不是偶数”两种；选项A ，算法不能等同于解法；选项C，解决某一个具体问题算法不同结果