《第十讲 算法初步》由会员分享，可在线阅读，更多相关《第十讲 算法初步（65页珍藏版）》请在金锄头文库上搜索。
1、第十讲 算法初步,一、算法在高考中的要求,1算法的含义、程序框图 （1）了解算法的含义，了解算法的思想 （2）理解程序框图的三种基本逻辑结构：顺序、条件分支、循环 2基本算法语句 了解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句的含义,二、知识点归纳与总结,(一) 算法的含义 程序框图,1算法的概念 （1）算法的定义：广义的算法是指完成某项工作的方法和步骤，因此我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等. 在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成,（2）算法的
2、特征： 确定性：算法的每一步都应当做到准确无误、“不重不漏”.“不重”是指不是可有可无的、甚至无用的步骤，“不漏” 是指缺少哪一步都无法完成任务. 逻辑性(有序性)：算法从开始的“第一步”直到“最后一步”之间做到环环相扣.分工明确，“前一步”是“后一步”的前提， “后一步”是“前一步”的继续. 有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行. （3）算法的描述：自然语言、程序框图、程序语言.,2程序框图 （1）程序框图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图
3、形； （2）构成程序框的图形符号及其作用,（3）程序框图的构成 一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字.,3几种重要的结构 （1）顺序结构 顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构.,（3）循环结构 在一些算法中要求重复执行同一操作的结构称为循环结构.即从算法某处开始，按照一定条件重复执行某一处理过程.重复执行的处理步骤称为循环体. 循环结构有两种形式：当型循环结构和直到型循环结构.,当型循环结构，如左下图所示，它的功
4、能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立，返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构.继续执行下面的框图.,直到型循环结构，如右下图所示，它的功能是先执行重复执行的A框，然后判断给定的条件P是否成立，如果P仍然不成立，则返回来继续执行A框，再判断条件P是否成立.以次重复操作，直到某一次给定的判断条件P时成立为止，此时不再返回来执行A框，离开循环结构.继续执行下面的框图.,(二) 基本算法语句,如何在计算机上实现算法？ 输入语句 输出语句 赋值语句 条件语句 循环语句,描写分支结构
5、的基本语句,不完整的If语句： if 表达式语句序列;end 完整的If语句： if 表达式语句序列1;else语句序列1;end,If 语句的例,不完整的If语句的例：if x5 y=3*x+8;end 完整的If语句的例：if x/2=0disp(“x is a even”);elsedisp(“x is a odd”);end,循环,指的是反复地执行一个或多个步骤. 类型 固定(循环次数为已知的情形) 可变(循环次数为未知的情形),固定的 进行固定次数的重复操作. 循环内计算或处理的数值对循环操作的次数没有影响. 可变的 重复操作,直到一个指定的条件满足. 循环次数可以变化.,描写循环结
6、构的基本语句,While型循环：while 表达式语句序列（即循环体）end for型循环：for 循环变量=初值：步长：终值语句序列（即循环体）end,循环语句的例,1. While 1+eps1eps=eps/2;end 2. For I=1:1:6n=n*I;end,算法结构总结,三种基本结构顺序结构 分支结构 循环结构,(三) 算法案例,1求最大公约数 （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到
7、小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 .,（3）辗转相除法 辗转相除法求两个数的最大公约数，其算法可以描述如下： 输入两个正整数m和n； 求余数r：计算m除以n，将所得余数存放到变量r中； 更新被除数和余数：m=n，n=r； 判断余数r是否为0.若余数为0，则输出结果；否则转向第步继续循环执行. 如此循环，直到得到结果为止.,（4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术.在九章算术中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也，以等数约之. 步骤： 任意给出两个正数；判断它们是否都是
8、偶数.若是，用2约简；若不是，执行第二步. 以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.,二、热点例题解析,题型1：算法概念,例题1下列说法正确的是（ ） A算法就是某个问题的解题过程； B算法执行后可以产生不同的结果； C解决某一个具体问题算法不同结果不同； D算法执行步骤的次数不可以为很大，否则无法实施.,解析：答案为选项B；选项B，例如：判断一个整数是否为偶数，结果为“是偶数”和“不是偶数”两种；选项A ，算法不能等同于解法；选项C，解决某一个具体问题算法不同结果应该相同，否则算法构造的有问
9、题；选项D，算法可以为很多次，但不可以无限次. 点评：算法一般是机械的，有时需要进行大量的重复计算.只要按部就班去做，总能算出结果.通常把算法过程称为“数学机械化”.数学机械化的最大优点是它可以借助计算机来完成； 实际上处理任何问题都需要算法.如：中国象棋有中国象棋的棋谱、走法、胜负的评判准则；而国际象棋有国际象棋的棋谱、走法、胜负的评判准则；再比如申请出国有一系列的先后手续，购买物品也有相关的手续.,例题2下列语句中是算法的个数为（ ） 从济南到巴黎：先从济南坐火车到北京，再坐飞机到巴黎； 统筹法中“烧水泡茶”的故事； 测量某棵树的高度，判断其是否是大树； 已知三角形的一部分边长和角，借助正
10、余弦定理求得剩余的边角，再利用三角形的面积公式求出该三角形的面积. A1 B2 C3 D4,解析：正确选项为C，中我们对“树的大小”没有明确的标准，无法完成任务，不是有效的算法构造.中，勾画了从济南到巴黎的行程安排，完成了任务；中，节约时间，烧水泡茶完成了任务；中，纯数学问题，借助正、余弦定理解三角形，进而求出三角形的面积. 点评：算法过程要做到能一步一步的执行，每一步执行的操作，必须确切，不能含混不清，且在有限步后的必须得到问题的结果.,题型2：经典算法,问题1：酱油与醋调换的算法:一瓶酱油一瓶醋,利用一个空瓶进行调换.（交换A、B中的数据） 先将酱油倒入空瓶;A C（C=A） 然后将醋倒入
11、原来装酱油的瓶内;B A 再将原来空瓶内的酱油倒入原来装醋的瓶内.C B。 调换完毕.,例题3一个人带着三只狼和三只羚羊过河，只有一条船，同船可容纳一个人和两只动物，没有人在的时候，如果狼的数量不少于羚羊的数量就会吃羚羊.该人如何将动物转移过河？请设计算法？ 解析：任何动物同船不用考虑动物的争斗但需考虑承载的数量，还应考虑到两岸的动物都得保证狼的数量要小于羚羊的数量，故在算法的构造过程中尽可能保证船里面有狼，这样才能使得两岸的羚羊数量占到优势，具体算法如下：,算法步骤： 第一步：人带两只狼过河，并自己返回； 第二步：人带一只狼过河，自己返回； 第三步：人带两只羚羊过河，并带两只狼返回； 第四步
12、：人带一只羊过河，自己返回； 第五步：人带两只狼过河.,点评：算法是解决某一类问题的精确描述，有些问题使用形式化、程序化的刻画是最恰当的.这就要求我们在写算法时应精练、简练、清晰地表达，要善于分析任何可能出现的情况，体现思维的严密性和完整性. 本题型解决问题的算法中某些步骤重复进行多次才能解决，在现实生活中，很多较复杂的问题经常遇到这样的问题，设计算法的时候，如果能够合适地利用某些步骤的重复，不但可以使得问题变得简单，而且可以提高工作效率.,点评：解决这些问题的基本思想并不复杂，很清晰，但叙述起来很烦琐，有的步骤非常多，有的计算量很大，有时候完全依靠人力完成这些工作很困难.但是这些恰恰是计算机
13、的长处，它能不厌其烦的枯燥的、重复的、繁琐的工作.但算法也有优劣，我们要追求高效.,题型3：顺序结构,例题5写出通过尺轨作图确定线段AB一个5等分点的算法. 解析：我们借助于平行线定理，把位置的比例关系变成已知的比例关系，只要按照规则一步一步去做就能完成任务. 算法分析： 第一步：从已知线段的左端点A出发，任意作一条与AB不平行的射线AP； 第二步：在射线上任取一个不同于端点A的点C，得到线段AC； 第三步：在射线上延AC的方向截取线段CE=AC； 第四步：在射线上延AC的方向截取线段EF=AC；,第五步：在射线上延AC的方向截取线段FG=AC； 第六步：在射线上延AC的方向截取线段GD=AC，那么线段AD=5AB； 第七步：连接DB； 第八步：过C作BD的平行线，交线段AB于M，这样点M就是线段AB的一个5等分点.,题型4：条件结构,题型5：求最大公约数,算法步骤： 第一步：将840进行素数分解23357； 第二步：将1764进行素数分解223272； 第三步：确定它们的公共素因数：2，3，7； 第四步：确定公共素因数2，3，7的指数分别是：2，1，1； 第五步：最大公因数为223171=84. 点评：质数是除以外只能被和本身整除的正整数，它应该是无限多个，但是目前没有一个规律来确定所有的质数.,题型6：秦九韶算法,答案：65；20.,结束,同学们再见,
