1.1+算法引论
- 格式:ppt
- 大小:772.50 KB
- 文档页数:32
1.1 算法的意义1.算法的意义:对一类问题的机械的、统一的求解方法称为算法.2.算法的特性:有限性,即在执行算法时,必须能在有限步骤内完成;确定性,即算法的每一个步骤只能有一个确定的后继步骤.3.设计算法的基本方法:(1)找到解决问题的方法;(2)将解决问题的方法按照一定的步骤表示出来(即设计成统一的、机械的程序)1.算法的有穷性是指( )A .算法必须包含输出B .算法中每个操作步骤都是可执行的C .算法的步骤必须是有限的D .以上说法均不正确2.已知直角三角形两直角边长为a ,b ,求斜边长c 的一个算法分下列三步: ①计算c =a ,b 的值; ③输出斜边长c 的值,其中正确的顺序是( )A .①②③B .②③①C .①③②D .②①③3.计算下列各式中的S 值,能设计计算法求解的是( )①S=1+2+3+ (100)②S=1+2+3+…+100+…;③S=1+2+3+…+n (n ≥1,n ∈N ).A .①②B .①③C .②③D .①②③4.下面给出了计算球的体积的一个算法:第一步 取R=3;第二步 计算334R V π=; 第三步 输出运算结果是 .5.完成解不等式3x +2<4x -1的算法:第一步 移项并合并同类项,得 ;第二步 不等式两边同除以x 的系数,得 .6.在课本中的“猜数”游戏中,主持人告诉竞猜者:某商品价格低于4000元,而该商品的实际价格为1500元,则竞猜者用二分搜索法猜数时,第一次的报数为 ;按照课本中的规则,此人需 次即可猜中.7.著名数学家华罗庚“烧水泡茶”的两个算法如下:算法一:第一步,烧水;第二步,水烧开后,洗刷茶具;第三步,沏茶.算法二:第一步,烧水;第二步,烧水过程中,洗刷茶具;第三步,水烧开后沏茶.两个算法比较,算法 更高效.8.你要乘火车去外地办一件急事,请你写出从自己房间出发到火车车厢内的三步主要算法. 第一步, ;第二步, ;第三步, .9.给出求解方程组⎩⎨⎧=+=+175673y x y x )2()1( 的一个算法.1.1 算法的意义答案1.C 2.D 3.B 4.36π 5.―2x<―3;23>x . 6.2000;3. 7.二 8.去火车站 买车票 凭票上车,对号入座.9.第一步,方程(1)变形为x y 37-=(3);第二步,将(3)代入方程(2),消去y ,得到6x +5(7-3x )=17,即x =2;第三步,将x =2代入方程(3),得到方程组的解为⎩⎨⎧==12y x .。
在中央电视台幸运52节目中,有一个猜商品价格的环节,竟猜者如在规定的时间内大体猜出某种商品的价格,就可获得该件商品.现有一商品,价格在0-8000元之间,采取怎样的策略才能在短的时间内说出正确(大体上)的答案呢?第一步:报“4000”;第二步:若主持人说高了(说明答案在0~4000之间),就报“2000”,否则(答数在4000~8000之间)报“6000”;第三步:重复第二步的报数方法取中间数,直至得到正确结果.先去括号再乘除后加减65(42)+⨯-1、什么是算法呢?狭义而言,算法是专指用计算机解决某一问题的方法和步骤.著名计算机科学家D.E.Knuth 在其《计算机程序设计技巧》一书中为算法所下的定义是:“一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算系列”.一般地,按照一定规则解决某一类问题的明确和有限的步骤称为算法(algorithm)。
例1.给出求1+2+3+4+5的一个算法第一步:计算1+2,得到3第二步:将第一步中的运算结果3与3相加,得到6第三步:将第二步中的运算结果6与4相加,得到10第四步:将第三步中的运算结果10与5相加,得到15第一步:第二步:第三步:(消元)(解一元一次方程)①+②×2,得③711x =解③得117x =(带入求解)117x =将代入①,得67y =解方程组{32324x y x y -=+=①②例2的步骤练习•1.写出解方程的一个算法•2.写出求的一个算法•3.已知平面直角坐标系中的两点A (-1,0),•B (3,2),写出求直线AB 的方程的一个算法•4.写出1+2+3+4+......+100的一个算法032=+x 7531⨯⨯⨯。
算法的概念知识要点:一、定义:我们把用来解决问题的一系列步骤叫做算法。
二、算法必须符合以下条件:1、确定性:算法的每一步要做什么必须是明确的,不能含糊不清,模棱两可;例如,要把全班同学分成两队,“高个子的同学站出来”这个步骤就是不确定的,含糊的,哪些同学算高,哪些同学算矮?个子中等的同学就会不知所措。
2、有限性:算法必须在有限步内完成,如果需要无限步完成,就失去了实际意义。
算法的有限性往往指“在合理的范围之内”。
如果让计算机执行一个历时1000年才结束的算法,虽然是有限的,但超过了合理的限度,人们也不把它视作有效算法。
究竟什么算“合理限度”并无严格标准,由人们的常识和需要而定。
3、顺序性与正确性:算法从初始步骤开始,分为若干明确的步骤,每一步骤只能有一个确定的后继步骤,前一步是后一步的前提,并且每一步都应当能有效的执行,并得到确定的结果。
例如若0,b a b =÷则是无效的,不能执行的。
三、设计算法的要求:1、写出的算法必须能解决一类问题,并且能够重复使用。
2、要使算法尽量简单、步骤尽量少。
3、要保证算法正确且计算机能够执行。
题型讲解:例1 下列关于算法的说法中,正确的是( C )A 、算法就是某个问题的解题过程B 、算法执行后可以不产生确定的结果C 、解决某类问题的算法不是唯一的D 、算法可以无限地操作下去不停止例2 设计一个解一元二次方程()2ax bx c 0a 0++=≠的算法解:第一步:计算2b 4ac =-第二步:若0<;第三步:输出方程无实数根;第四步:若0≥;第五步:计算并输出方程的根,212b b 4ac x 2a-±-=。
例3 写出求123456+++++的值的一个算法解:第一步:取6n =;第二步:计算()n n 12+ 第三步:输出运算结果例4 写出求过()(),,1122P a b Q a b 、两点的直线斜率的一个算法解:第一步:取,,,11112222x a y b x a y b ====;第二步:若12x x =;第三步:输出斜率不存在;第四步:若12x x ≠;第五步:计算2121y y k x x -=-; 第六步:输出运算结果。
1.1.1 算法的概念三维目标1.知识与技能(1)了解算法的含义,体会算法的思想.(2)能够用自然语言叙述算法.(3)掌握正确的算法应满足的要求.(4)会设计一些简单问题的算法.2.过程与方法通过求解二元一次方程组,体会解方程的一般性步骤,从而得到一个解二元一次方程组的步骤,这些步骤就是算法.不同的问题有不同的算法,由于思考问题的角度不同,同一个问题也可能有多个算法,能模仿求解二元一次方程组的步骤,写出一个求有限整数序列中的最大值的算法.3.情感、态度与价值观通过本节的学习,使我们对计算机的算法语言有一个基本的了解,明确算法的要求,认识到计算机是人类征服自然的一个有力工具,进一步提高探索、认识世界的能力.重点难点重点:算法的含义、解二元一次方程组和判断一个数为质数的算法设计.难点:把自然语言转化为算法语言.教学建议1.算法这部分的实用性很强,与日常生活联系紧密,虽然是新引入的章节,但很容易激发学生的兴趣,让学生明确算法实际上就是解决某一类问题的一种程序化方法.重点培养学生的算法意识,这是在算法教学中始终要注意的.2.本节课宜采用“问题探究式”教学法,以教材中的两个例题为引线,先让学生回顾这两个问题的解题过程,自己动手整理出步骤.并用有条理的语言叙述出来.通过这样的教学,使学生体会设计算法的基本思路,同时教师以多媒体为辅助手段,让学生主动发现问题、分析问题、解决问题,培养学生的探究论证、逻辑思维能力.教学流程课标解读1.算法的概念的理解.(重点)2.算法的应用.(难点)知识1算法的概念【问题导思】电视娱乐节目中,有一种有趣的“猜数”游戏:竞猜者如在规定的时间内猜出某种商品的价格(或重量等),就可获得该件商品.现有一商品,价格在0~8 000元之间,采取怎样的策略才能在较短的时间内猜出正确的答案呢?解决这个问题有多种途径,其中一种较好的方法是:第一步报“4 000”.第二步若主持人说:“高了”(说明答数在0~4 000之间),就报“2 000”;否则(答数在4 000~8 000之间)报“6 000”.第三步重复第二步的报数方法,直至得到正确结果.1.竞猜者每一步的报价有一定的规则吗?【提示】有,报价为上一个有效范围的中间值.2.猜出这种商品的步骤是有限的吗?【提示】是.数学中的算法通常指按照一定规则解决某一类问题的明确和有限的步骤.知识2算法与计算机计算机解决任何问题都要依赖于算法,只有将解决问题的过程分解为若干个明确的步骤,即算法,并用计算机能够接受的“语言”准确地描述出来,计算机才能够解决问题.类型1算法的概念1.对算法含义的理解(1)算法是机械的算法的设计要“面面俱到”不能省略任何一个小小的步骤,有时可能要进行大量重复计算,但只要按步骤一步一步地执行,总能得到结果.算法的这种机械化的特点,在设计出算法后,便于把具体过程交给计算机去完成.(2)算法是普遍存在的实际上处理任何问题都需要算法,如国际象棋的棋谱、走法、胜负的评判标准,邮寄物品的相关手续,求一个二元一次方程组的解等等.(3)求解某个具体问题的算法一般是不唯一的算法实际上是解决问题的步骤和方法,求解问题的出发点不同,就会得到不同的算法.如求二元一次方程组的解有代入消元法和加减消元法,但不同的算法可能会有“优劣”之分.例1早上从起床到出门需要洗脸刷牙(5 min)、刷水壶(2 min)、烧水(8 min)、泡面(3 min)、吃饭(10 min)、听广播(8 min)几个步骤.从下列选项中选出最好的一种流程() A.1.洗脸刷牙、2.刷水壶、3.烧水、4.泡面、5.吃饭、6.听广播B .1.刷水壶、2.烧水同时洗脸刷牙、3.泡面、4.吃饭、5.听广播C .1.刷水壶、2.烧水同时洗脸刷牙、3.泡面、4.吃饭同时听广播D .1.吃饭同时听广播、2.泡面、3.烧水同时洗脸刷牙、4.刷水壶分析 处理问题的算法要求能够一步一步地执行,好的算法还要花费时间少.【解析】 A 中洗脸刷牙可以在烧水的过程中进行,听广播可以和吃饭同时进行;D 中吃饭要在刷水壶、烧水、泡面之后.【答案】 C变式训练下列语句不是算法的是________.(填写序号)①从济南到巴黎,可以先乘火车到北京,再坐飞机抵达巴黎.②利用公式s =4πr 2,计算半径为2的球的表面积,即计算4π×22.③方程2x 2-x -1=0有两个实数根.④12x >x +2. 【解析】 ①②都描述了解决问题的过程,可以看作算法,而③④只描述了一个事实,没说明如何解决问题,不是算法.【答案】 ③④类型2算法设计 2.算法与数学问题解法的区别与联系(1)联系算法与解法是一般与特殊的关系,也是抽象与具体的关系.如教材中由具体的二元一次方程组的求解过程(解法)出发,归纳出了二元一次方程组求解的步骤;同时指出,这样的求解步骤也适合有限制条件的二元一次方程组,这些步骤就构成了二元一次方程组的算法.算法的获得要借助一般意义上具体问题的求解方法,而任何一个具体问题都可利用这类问题的一般算法解决.(2)区别算法是解决某一类问题所需要的程序和步骤的统称,也可理解为数学中的“通法通解”;而解法是解决某一个具体问题的过程和步骤,是具体的解题过程.例2 给出求解方程组⎩⎪⎨⎪⎧2x +y =7. ①4x +5y =11 ②的一个算法. 解:方法一 (消元法)S1 ②-①×2,得3y =-3,③S2 解③得y =-1;④S3 将④代入①,得x =4;S4 输出x =4,y =-1.方法二 (公式法)S1 计算D =2×5-4×1=6;S2 因为D =6,所以x =5×7-11×16=4,y =11×2-7×46=-1; S3 输出x =4,y =-1.点评 本题中的方法二,直接利用高斯消去法的算法步骤,显得更为简捷. 变式训练写出求方程组1233162x y z x y z x y z ⎧++=⎪--=⎨⎪--=-⎩①②③ 的解的算法步骤.解: 法一第一步,①+③,得x =5.④第二步,将④分别代入①和②可得{ y +z =7,3y +z =-1. ⑤⑥ 第三步,⑥-⑤可得,y =-4.⑦第四步,将⑦代入⑤可得z =11.第五步,得到方程组的解为{ x =5,y =-4,z =11. 法二第一步,(①+②)÷2得2x -y =14.④第二步,(②-③)÷2得x -y =9.⑤第三步,④-⑤,得x =5.⑥第四步,将⑥代入⑤,得y =-4.⑦第五步,将⑥和⑦代入①式,得z =11.第六步,得到方程组的解为{ x =5,y =-4,z =11.类型3算法的应用 例3 已知函数2+11-1x x y x x ⎧=⎨≥⎩(<)()试设计一个算法,输入x 的值,求对应的函数值. 【思路探究】 解答本题的关键是对x 进行判断,根据x 的不同范围求出y ,输出y 的值.解: 算法如下:第一步,输入x 的值.第二步,当x <1时,计算y =x +1;否则执行第三步.第三步,计算y =-x 2.第四步,输出y .规律方法1.本题是分段函数的求值问题,设计算法时,要对输入的自变量值分类.2.设计算法解决具体问题时,通常按自然语言确定问题的解法,然后根据算法的要求设计成一系列的操作步骤.变式训练若将本例函数改为1(0)001(0)x x x y x x ⎧-⎪⎪⎪=⎨⎪⎪⎪⎩<(=)>该如何设计算法? 解: 算法如下:第一步,输入x 的值.第二步,若x <0,则计算y =-1x;否则执行第三步. 第三步,若x =0,则y =0;否则执行第四步.第四步,计算y =1x. 第五步,输出y .误区突破1.算法的确定性理解不到位例1 求2+4+6+8+…+100的算法.【错解】 算法:S1 计算2+4+6+8+ (100)S2 输出第一步中的结果. 错解辨析 对于连加连乘的问题,不能直接得到答案,应当逐步进行.【正解】 算法:S1 计算2+4得到6;S2 将第一步的结果与6相加得到12;S3 将第二步的结果与8相加得到20;S4 如此继续下去,一直加到100;S5 输出运算结果.2.程序框图中循环结构功能、条件出错例2 如图所示是某一算法的程序框图,根据该框图指出这一算法的功能.【错解】 求S =12+14+16+18+110的值. 【正解】 在该程序框图中,S 与n 为两个累加变量,k 为计数变量,所以该算法的功能是求12+14+16+…+120的值. 设计算法的三种思路1.按部就班法此法是基本方法,要求按问题的解题步骤“按部就班”地做,每一步都有唯一的结果,且在有限步之后得出结果.例1 写出作∠ABC 的平分线的一个算法.分析 解决这个问题,只需按作图方法“按部就班”地设计算法.解:S1 以B 为圆心,以任意长为半径画弧,与边BA 交于M 点,与边BC 交于N 点.S2 以M 为圆心,以大于12MN 的长d 为半径画弧. S3 以N 为圆心,以大于12MN 的长d 为半径画弧. S4 取第二、三两步所得的弧的交点P .S5 过B ,P 作射线BP ,射线BP 即为∠ABC 的平分线.2.公式法利用现有公式解决问题是设计算法的重要思路.例2 计算上底为2,下底为4,高为5的梯形的面积.分析 根据梯形的面积公式S =12(a +b )h .其中a 是上底,b 是下底,h 是高,只需令a =2,b =4,h =5,代入公式即可.解:算法如下:S1 a =2,b =4,h =5;S2 S =12(a +b )h ; S3 输出S .3.循环法有些问题需要重复计算,而这正是计算机的强项,因此我们可以利用循环来实现. 例3 设计出一个求23+43+63+…+603的算法.解:S1 p =0,i =2.S2 p =p +i 3.S3 i =i +2.S4 如果i >60,算法结束,否则,返回第二步.S5 输出p .当堂检测1.算法的有限性是指( )A .算法必须包含输出B .算法中每个步骤都是可执行的C .算法的步骤是有限的D .以上说法均不正确【解析】 算法的有限性是指算法必须保证执行有限步后结束,故选C.【答案】 C2.计算下列各式中的S 值,能设计算法求解的是( )①S =1+2+3+ (100)②S =1+2+3+…+100+…;③S =1+2+3+…+n (n ≥1,且n ∈N +).A .①②B .①③C .②③D .①②③【解析】 算法的设计要求步骤是可行的,并且在有限步之内能完成任务.②是无限项求和,不能用算法求解.【答案】 B3.下面是某人出家门先打车去火车站,再坐火车去北京的一个算法,请补充完整.第一步,出家门.第二步,________.第三步,坐火车去北京.【解析】按照这个人出门去北京的顺序,第二步应该为打车去火车站.【答案】打车去火车站4.设计一个解方程组⎩⎪⎨⎪⎧2x +y -1=0,x -2y +3=0的算法,算法步骤用自然语言描述. 解:⎩⎪⎨⎪⎧ 2x +y -1=0 ①x -2y +3=0②算法步骤为: S1 ①×2+②得5x +1=0;③S2 解③得x =-15;④ S3 将④代入①,可得y =75; S4 输出x ,y 的值.。