算法概念讲课课件1

1、1.1.11.1.1算法的概念算法的概念 骆驼坳中学骆驼坳中学 徐徐 进进 例一例一 请你说出登录腾讯请你说出登录腾讯QQQQ的步骤。的步骤。 （电脑已经打开）（电脑已经打开）第一步：打开第一步：打开QQQQ程序。程序。第二步：输入第二步：输入QQQQ号码。号码。第三步：输入密码。第三步：输入密码。第四步：点击登录。第四步：点击登录。 一般地一般地, ,对于一类问题的机械式地、统一对于一类问题的机械式地、统一地 、 按 部 就 班 地 求 解 过 程 称 为 算 法地 、 按 部 就 班 地 求 解 过 程 称 为 算 法(algorithm)(algorithm)它是解决某一问题的程序或步骤

2、它是解决某一问题的程序或步骤. . 所谓所谓 “算法算法” 从更广义的角度来看从更广义的角度来看,并不并不是只有是只有“计算计算”的问题才有算法的问题才有算法,日常生活中日常生活中处处都有处处都有.如如乐谱乐谱是乐队演奏的算法是乐队演奏的算法,菜谱菜谱是做是做菜肴的算法菜肴的算法,珠算口诀珠算口诀是使用算盘的算法是使用算盘的算法.预习课本预习课本 2 2、3 3页页思考思考1 1：回顾二元一次方程组有哪些解法？回顾二元一次方程组有哪些解法？思考思考2 2：导入新课导入新课思考思考x-2y=-1 2x+y=1 a1x+b1y=c1 a2x+b2y=c2 这这 两个解方程组的算法的适两个解方程组的

3、算法的适用范围有何不同？用范围有何不同？思考思考3:3:根据上述分析，你能归纳出算法的概念吗？根据上述分析，你能归纳出算法的概念吗？ 在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法类问题的明确和有限的步骤称为算法. . 现在，算法通常可以编成计算机程现在，算法通常可以编成计算机程序，让计算机执行并解决问题。序，让计算机执行并解决问题。 讲授新课讲授新课. . 一人带着一只狼、一只羊和一箱蔬菜要过河一人带着一只狼、一只羊和一箱蔬菜要过河,但只但只有一条小船有一条小船.乘船时，每次只能带狼、羊和蔬菜中的一乘船时，每次只能带狼、羊和蔬菜中的一种种.当有人

4、在场时，狼、羊、蔬菜都相安无事当有人在场时，狼、羊、蔬菜都相安无事.一旦人一旦人不在不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.请设计一个方案请设计一个方案,安全地将狼、安全地将狼、羊和蔬菜带过河羊和蔬菜带过河.过河游戏例二例二 趣味益智游戏方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼到对岸，返回；带狼到对岸，返回；4、带羊到对岸。带羊到对岸。思考思考4:4:有人对哥德巴赫猜想有人对哥德巴赫猜想“任何大于任何大于4 4的的偶数都能写成两个质数之和偶数都能写成两个质数之和”设计了如下操设计了如下操作步骤：作步骤：第一步，

5、检验第一步，检验6=3+36=3+3，第二步，检验第二步，检验8=3+58=3+5，第三步，检验第三步，检验10=5+510=5+5， 利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问：这是一个算法吗？请问：这是一个算法吗？思考？思考？请你根据前面两个问题总结请你根据前面两个问题总结一下算法有哪些特点和要求？一下算法有哪些特点和要求？1、有限性、有限性一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。2、确定性、确定性算法对每一个步骤都有确切的，能有效执行且得到确定结果的，不能模棱两可。3、顺序与可行性顺序与可行性算法中的每下一个步骤都是在上一个步骤完成才能执行，并且每一步

6、都是可以完成的。求解某一个问题的解法不一定是唯一的，对于同一个问题可以有不同的解法。4 4、不唯一性、不唯一性知识探究（二）知识探究（二）: :算法的步骤设计算法的步骤设计 例例1： （1 1）设计一个算法判断）设计一个算法判断7 7是否为质数。是否为质数。 （2 2）设计一个算法判断）设计一个算法判断3535是否为质数。是否为质数。 （3 3）设计一个算法判断）设计一个算法判断20112011是否为质数。是否为质数。例例1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数. .第第 1 步步, 用用 2 除除 7, 得到余数得到余数 1. 因为余数不因为余数不为为 0

7、，所以，所以 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是质数是质数.知识探

8、究（二）知识探究（二）: :算法的步骤设计算法的步骤设计(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，得到余数

9、，得到余数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;第三步第三步:将第二步结果将第二步

10、结果6+4，得，得10;第四步第四步:将第三步结果将第三步结果10+5，得，得15;第五步第五步:将第四步结果将第四步结果15+6，得，得21；第六步第六步:将第五步结果将第五步结果21+7，得，得28.第一步第一步,取取 n =6;第二步第二步,计算计算第三步第三步, 计算结果计算结果28.2)1( nn解法解法2.1+2+3+n=n(n+1)/2解法解法1.按照逐一相加的程序进行按照逐一相加的程序进行.-用公式运算用公式运算 课时小结课时小结1:算法的概念算法的概念2:算法的特点算法的特点3:如何设计算法如何设计算法预习：预习：用二分法设计一个求方程用二分法设计一个求方程 x x2 2-2=0 -2=0 的近似正根的算法，精确度的近