12.1 算法的概念

20 世纪最伟大的科学技术发明是计算机.没有软件的支持，计算机只是一堆废铁而已.,软件的核心就是算法 ！,2,§12.1算法的概念,3,先去括号,再乘除,后加减,1、,什么是算法呢？,4,问要把大象装冰箱，分几步？,答：分三步：,第一步：打开冰箱门.,第二步：把大象装冰箱.,第三步：关上冰箱门.,想一想,5,第一步，插入银行卡；,课本第38页探究：小李想用银行卡从自动取款机上取500元钱，由于他第一次用银行卡取钱，所以向你求助，你能写下用银行卡取钱的具体步骤，帮助他顺利取出钱吗？,第二步，输入取款密码；,第三步，输入取款金额；,第四步，从出钞口取走钱；,第五步，取回银行卡。,6,算法：是指用来解决问题的一系列明确而有效的步骤，是解决问题的清晰的指令。,1.算法的定义,新知建构,7,例1.写出求1+2+3+4+5的一个算法.,解：算法为：,S1:计算1+2得到3；,S2:将第一步中的运算结果3与3相加得到6；,S3:将第二步中的运算结果6与4相加得到10；,S4:将第三步中的运算结果10与5相加得到15.,算法2:,S1：取n=5.,S2：计算,S3：输出运算结果.,同一问题的解决算法一般是不唯一的,典型例题,8,一个好的算法的特点:,高效性:运算的次数少，执行的速度快，占用的资源少。,9,练习：1写出求123100的一个算法.可以运用公式123n 直接计算. 第一步 ； 第二步 ； 第三步 输出运算结果.,取n100,计算,10,2已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99，求他的总分和平均成绩的一个算法为： 第一步 取A89，B96，C99; 第二步 ； 第三步 ； 第四步 输出D，E.,计算总分DA+B+C,计算平均成绩E,×,例2 写出交换两个大小相同的杯子中 的液体 (A杯中为水、 B杯中为 酒) 的一个算法,第一步,找一个大小与A相同的空杯子C.,解：算法为：,第二步,将A杯中的水倒入C杯中.,第四步,将C杯中的水倒入B杯中,结束.,第三步,将B杯中的酒倒入A杯中.,12,练习,1、 写出求1×2×3××9×10的值的一个算法.,解 算法为:,第一步 求1×2,得到结果2;,第二步 求2×3,得到结果6;,第三步 求6×4,得到结果24;,第四步 求24×5,得到结果120;,第九步 将362 880再乘以10,得到3 628 800.,13,2、 写出从12，3，-1，2，6,9，18,5，-3,17搜索出5的一个算法.,解 算法为:,第一步 输入数列的第一个数12，并与5比较，发现它不是数据5;,第二步 输入数列的第二个数3，并与5比较，发现它不是数据5;,第七步 输入数列的第七个数18，并与5比较，发现它不是数据5;,第八步 输入数列的第八个数5，并与5比较，发现它是数据5，输出“已找到数据5，它是数列的地八项”。,14,第一步:用2除以7,得到余数1.因为余数不为0, 所以2不能整除7. 第二步:用3除以7,得到余数1.因为余数不为0, 所以3不能整除7. 第三步:用4除以7,得到余数3.因为余数不为0, 所以4不能整除7. 第四步:用5除以7,得到余数2.因为余数不为0, 所以5不能整除7. 第五步:用6除以7,得到余数1.因为余数不为0, 所以6不能整除7.,练习.设计一个算法,判断7是否为质数.,15,例3 设计一个算法，判断整数n（n2）是否为质数。,第二步：令i=2；,第三步：用i除以n，得到余数r；,第一步：给定大于2的整数n；,第四步：判断“r0”是否成立，若是，则n不是质数，结束算法；否则，令i=i+1；,第五步：判断“i(n-1)”是否成立，若是，则n是质数，结束算法；否则，返回第三步。,解 算法为:,16,练习：设计一个算法,判断35是否为质数.,第一步:用2除以35,得到余数1.因为余数不为0, 所以2不能整除35. 第二步:用3除以35,得到余数2.因为余数不为0, 所以3不能整除35. 第三步:用4除以35,得到余数3.因为余数不为0, 所以4不能整除35. 第四步:用5除以35,得到余数0.因为余数为0, 所以5能整除35.因此,35不是质数.,17,变量和赋值的概念,给变量赋值的一般格式为：,变量名=表达式,在解决问题的过程中，可以取不同数值的量叫做变量。,例如：n=2,s=a+b,i=i+1,期中的符号“=”为赋值号,18,第一步，令A=1,B=2,C=3;,第二步，A=A+B;,第三步，A=A+B+C;,第四步，输出A，B，C。,例4：读下列算法，回答问题：,问：最后输出A，B，C的值各为多少？,解：A=8，B=2，C=3.,19,例1.写出求1+2+3+4+5的一个算法.,解：算法为：,第一步:S=1；,典型例题,第二步:S=S+2；,第五步:S=S+5；,第六步:输出S.,20,例5.写出一个能找出在a,b,c,d四个数中最大的数的算法.,第一步:输入a,b,c,d四个数;,第二步:max=a;,第三步:如果bmax,则max=b;,第四步:如果cmax,则max=c;,第五步:如果dmax,则max=d;,第六步:输出max.,点评:算法要求“按部就班”地做,每做一步都有唯一的结果,且有限步之后总能得到结果.,21,一个有效算法的特点:,确切性:不存在歧义。,有0个、一个或多个输入:以刻画运算对象的初始情况。“0个输入”是指算法本身给出了初始条件.,有一个或多个输出:以反映对输入数据加工后的结果。,有穷性:算法应由有限步组成,必须在有限操作之后停止,并给出计算结果。,可行性:或有效性，每个步骤都可以在有限时间内完成。,22,1.知识结构,算法的概念,算法的步骤,算法的特点,算法,2.算法的特点:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作. 正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,课堂小结,23,作业,继续探索 作业探究,教材12.1,阅 读,P44习题1,2,3,4。 选作：5,作业本,12.1,学习指导用书,24,1.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r；,第二步:计算圆的面积: S=r2;,第三步:输出圆的面积S.,练习,2.任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.,答案1：第一步：依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.,第二步：在n的因数中加入1和n.,第三步：输出n的所有因数.,答案2:第一步:给定大于1的整数n 第二步:令i=1 第三步:用i除n,得余数r 第四步:判断“ r=0” 是否成立,若是,则i是n的因数,输出i, 第五步:将i的值增加1,仍用i表示. 第六步:判断“in结束算法,否则返回第三步.,巩固概念,×,3、写出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,计算=b2-4ac.,第二步,如果0,则原方程无实数解 ;否则(0)时，,第三步:输出x1, x2或无实数解的信息.,27,4下面的四种叙述不能称为算法的是（ ） （A）广播的广播操图解 （B）歌曲的歌谱 （C）做饭用米 （D）做米饭需要刷锅、淘米、添水、加热这些步骤,练习题,C,28,5下列关于算法的说法正确的是（ ） （A）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操作的原则,D,29,6下列关于算法的说法中，正确的是（ ）. A. 算法就是某个问题的解题过程 B. 算法执行后可以不产生确定的结果 C. 解决某类问题的算法不是惟一的 D. 算法可以无限地操作下去不停止,C,30,7下列运算中不属于我们所讨论算法范畴的是（ ）. A. 已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取3张扑克牌抽到24点的可能性 C. 已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则,B,