算法概念讲课课件1.ppt
1.1.11.1.1算法的概念算法的概念 骆驼坳中学骆驼坳中学 徐徐 进进 例一例一 请你说出登录腾讯请你说出登录腾讯QQQQ的步骤。的步骤。（电脑已经打开）（电脑已经打开）第一步：打开第一步：打开QQQQ程序。程序。第二步：输入第二步：输入QQQQ号码。号码。第三步：输入密码。第三步：输入密码。第四步：点击登录。第四步：点击登录。一一般般地地,对对于于一一类类问问题题的的机机械械式式地地、统统一一地地、按按 部部 就就 班班 地地 求求 解解 过过 程程 称称 为为 算算 法法(algorithm)(algorithm)它是解决某一问题的程序或步骤它是解决某一问题的程序或步骤.所所谓谓“算算法法”从从更更广广义义的的角角度度来来看看,并并不不是是只只有有“计计算算”的的问问题题才才有有算算法法,日日常常生生活活中中处处处处都都有有.如如乐乐谱谱是是乐乐队队演演奏奏的的算算法法,菜菜谱谱是是做做菜肴的算法菜肴的算法,珠算口诀珠算口诀是使用算盘的算法是使用算盘的算法.预习课本预习课本 2 2、3 3页页思考思考1 1：回顾二元一次方程组有哪些解法？回顾二元一次方程组有哪些解法？思考思考2 2：导入新课导入新课导入新课导入新课思考思考x-2y=-1 2x+y=1 a1x+b1y=c1 a2x+b2y=c2 这这 两个解方程组的算法的适两个解方程组的算法的适用范围有何不同？用范围有何不同？思考思考3:3:根据上述分析，你能归纳出算法的概念吗根据上述分析，你能归纳出算法的概念吗？在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法类问题的明确和有限的步骤称为算法.现在，算法通常可以编成计算机程现在，算法通常可以编成计算机程序，让计算机执行并解决问题。序，让计算机执行并解决问题。讲授新课讲授新课讲授新课讲授新课.一一人人带带着着一一只只狼狼、一一只只羊羊和和一一箱箱蔬蔬菜菜要要过过河河,但但只只有有一一条条小小船船.乘乘船船时时，每每次次只只能能带带狼狼、羊羊和和蔬蔬菜菜中中的的一一种种.当当有有人人在在场场时时，狼狼、羊羊、蔬蔬菜菜都都相相安安无无事事.一一旦旦人人不不在在,狼狼会会吃吃羊羊,羊羊会会吃吃菜菜.请请设设计计一一个个方方案案,安安全全地地将将狼狼、羊和蔬菜带过河羊和蔬菜带过河.过河游戏例二例二 趣味益智游戏方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼到对岸，返回；带狼到对岸，返回；4、带羊到对岸。带羊到对岸。思考思考4:4:有人对哥德巴赫猜想有人对哥德巴赫猜想“任何大于任何大于4 4的的偶数都能写成两个质数之和偶数都能写成两个质数之和”设计了如下操设计了如下操作步骤：作步骤：第一步，检验第一步，检验6=3+36=3+3，第二步，检验第二步，检验8=3+58=3+5，第三步，检验第三步，检验10=5+510=5+5，利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问：这是一个算法吗？请问：这是一个算法吗？思考？思考？请你根据前面两个问题总结请你根据前面两个问题总结一下算法有哪些特点和要求？一下算法有哪些特点和要求？1、有限性、有限性一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。2、确定性、确定性算法对每一个步骤都有确切的，能有效执行且得到确定结果的，不能模棱两可。3、顺序与可行性顺序与可行性算法中的每下一个步骤都是在上一个步骤完成才能执行，并且每一步都是可以完成的。求解某一个问题的解法不一定是唯一的，对于同一个问题可以有不同的解法。4 4、不唯一性、不唯一性知识探究（二）知识探究（二）:算法的步骤设计算法的步骤设计 例例1：（1 1）设计一个算法判断）设计一个算法判断7 7是否为质数。是否为质数。（2 2）设计一个算法判断）设计一个算法判断3535是否为质数。是否为质数。（3 3）设计一个算法判断）设计一个算法判断20112011是否为质数。是否为质数。例例1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数.第第 1 步步,用用 2 除除 7,得到余数得到余数 1.因为余数不因为余数不为为 0，所以，所以 2 不能整除不能整除 7.第第 2 步步,用用 3 除除 7,得到余数得到余数 1.因为余数不为因为余数不为 0，所以，所以 3 不能整除不能整除 7.第第 3 步步,用用 4 除除 7,得到余数得到余数 3.因为余数不因为余数不为为 0，所以所以 4 不能整除不能整除 7.第第4步步,用用 5 除除 7,得到余数得到余数 2.因为余数不因为余数不为为 0，所以所以 5 不能整除不能整除 7.第第 5 步步,用用 6 除除 7,得到余数得到余数 1.因为余数不因为余数不为为 0，所以所以 6 不能整除不能整除 7.因此，因此，7是质数是质数.知识探究（二）知识探究（二）:算法的步骤设计算法的步骤设计(2)设计一个算法判断设计一个算法判断 35 是否为质数？是否为质数？353535 35353535 20 35因此，因此，3535不是质数不是质数2011201120112011201120112011 201120112010因此，因此，20112011是质数是质数2010(3)第第20092009你能写出你能写出“判断整数判断整数n(nn(n2)2)是否为质数是否为质数”的算法吗？的算法吗？第一步，给定大于第一步，给定大于2 2的整数的整数n n。第二步，令第二步，令i=2.i=2.第三步，用第三步，用i i除除n n，得到余数，得到余数r r。判断余数。判断余数r r是否是否 为为0,0,若是则若是则n n不是质数，结束算法；否则，将不是质数，结束算法；否则，将i i的值增加的值增加1 1，仍用，仍用i i表示。表示。第四步，判断第四步，判断i i是否大于是否大于(n-1)(n-1)，若是，则，若是，则n n是是 质数；否则，返回第三步质数；否则，返回第三步算法设计：算法设计：思考？思考？（1）请你）请你设计出求设计出求1+2+3+4+5+6+71+2+3+4+5+6+7的算的算法法.第一步第一步:计算计算1+2,得得3;第二步第二步:将第一步结果将第一步结果3+3，得，得6;第三步第三步:将第二步结果将第二步结果6+4，得，得10;第四步第四步:将第三步结果将第三步结果10+5，得，得15;第五步第五步:将第四步结果将第四步结果15+6，得，得21；第六步第六步:将第五步结果将第五步结果21+7，得，得28.第一步第一步,取取 n=6;第二步第二步,计算计算第三步第三步,计算结果计算结果28.解法解法2.1+2+3+n=n(n+1)/2解法解法1.按照逐一相加的程序进行按照逐一相加的程序进行.-用公式运算用公式运算 课时小结课时小结1:算法的概念算法的概念2:算法的特点算法的特点3:如何设计算法如何设计算法预习：预习：用二分法设计一个求方程用二分法设计一个求方程 x x2 2-2=0 -2=0 的近似正根的算法，精确度的近似正根的算法，精确度0.05.0.05.练习：练习：（1）任意给定一个正实数任意给定一个正实数,设计一个设计一个算法求以这个数为半径的圆的面积算法求以这个数为半径的圆的面积.（2）任意给定一个大于任意给定一个大于1 1的正整数的正整数n n,设计一个算法求出设计一个算法求出n n的所有因数的所有因数.
