算法的概念课件

1.1.1算法的概念,主页,20 世纪最伟大的科学技术发明是计算机.没有软件的支持，计算机只是一堆废铁而已.,软件的核心就是算法！,20 世纪最伟大的科学技术发明是计算机.没有软件的支,算法的含义,算法的含义,【1】一个农夫带着一条狼、一头山羊和一筐蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使农夫能安全地将这三样东西带过河.,第一步:农夫带羊过河;,第二步:农夫独自回来;,第三步:农夫带狼过河;,第四步:农夫带羊回来;,第五步:农夫带蔬菜过河;,第六步:农夫独自回来;,第七步:农夫带羊过河.,创设情境,【1】一个农夫带着一条狼、一头山羊和一筐蔬菜要过河,但只有一,一般地,对于一类问题的机械式地、统一地、按部就班地求解过程称为算法(algorithm)它是解决某一问题的程序或步骤.,按照这样的理解,我们可以设计出很多具体数学问题的算法.下面看几个例子:,所谓“算法”就是解题方法的精确描述.从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有,.如,歌谱是一首歌曲的算法;菜谱,是做菜的算法;,珠算口诀,是使用算盘的算法;空调说明书是空调使用的算法等.,一般地,对于一类问题的机械式地、统一地、按部就班地求,解：第一步:+2,得,第二步:解,得,机械的统一的方法,5,x=,1,.,第三步:,-,2,得,5,y=,3,.,第四 步:解,得,第五 步:得到方程组的解为,新知建构,例1.写出解二元一次方程组 的一个算法.,解：第一步:+2,得第二步:解,得机械的统一的,算法1,算法2,问:,ax,+b,=,0,?,算法1算法2问:ax+b=0?,练,2.写出求1+2+3+4+5的一个算法.,算法1：,S1:计算1+2得到3；,S2:将第一步中的运算结果3与3相加得到6；,S3:将第二步中的运算结果6与4相加得到10；,S4:将第三步中的运算结果10与5相加得到15.,算法2:,S1：取,n,=5.,S2：计算,S3：输出运算结果.,同一问题的解决算法一般是不唯一的,练2.写出求1+2+3+4+5的一个算法.算法1：S1:计算,第一步:计算12,得2;,第二步:将第一步中的运算结果2与3相乘得6;,第三步:将第二步中的运算结果6与4相乘得24;,第四步:将第三步中的运算结果24与5相乘得120;,第五步:将第四步中的运算结果120与6相乘得720.,练,3.,求123456的值，写出其算法,.,第一步:计算12,得2;第二步:将第一步中的运算结果2与3,在,数学,中,算法通常是指按照一定规则解决某一类问题的明确的有限的步骤.现在,算法通常可以编成计算机程序,让计算机执行并解决问题.,1.算法的定义,新知建构,算法:,广义上讲,，做任何事情都有一定的步骤,为解决一个问题而采取的方法和步骤就是算法.,总结,算法过程:要能一步一步执行，每一步执行的操作,必须确切，不能含混不清楚，而且经过有限步后能得出结果.,在数学中,算法通常是指按照一定规则解决某一类,小结,通过练习说明算法有三个主要特点：,（3）确定性 算法的每一个步骤和次序,应当是确定的,（2）有限性 一个算法在执行有限个步,骤后必须结束；,（1）可行性 一个算法必须一步步可执 行,小结通过练习说明算法有三个主要特点：（3）确定性 算法的,想一想,【1】有人对歌德巴赫猜想“,任何大于4的偶数都能写成两个奇质数之和,”设计了如下操作步骤：,第一步：检验6=3+3,第二步：检验8=3+5,利用计算机无穷地进行下去！,利用这种程序能够证明猜想的正确性吗？,第三步：检验10=5+5,想一想【1】有人对歌德巴赫猜想“任何大于4的偶数都能写成两个,【2】问要把大象装冰箱，分几步？,答：分三步：,第一步：打开冰箱门.,第二步：把大象装冰箱.,第三步：关上冰箱门.,想一想,对算法你有新的认识了吗？,【2】问要把大象装冰箱，分几步？答：分三步：第一步：打开冰箱,例题讲解,第一步:用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.,例,2.(1)设计一个算法,判断7是否为质数.,例题讲解第一步:用2除7,得到余数1.因为余数不为0,例2.,例,2.(2),设计一个算法,判断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不是质数.,例2.(2)设计一个算法,判断35是否为质数.第一步:用2除,例2.任意给定一个大于2的整数,n,试设计一个程序或步骤对,n,是否为质数做出判定.,第二步:令,i,=2.,第一步：,给定一个大于2的整数,n,.,第三步:用,i,除,n,得到,余数,r.,解析,:,n,是否为质数,2(,n,-1),这是判断一个大于1的整数的最基本算法.,例题讲解,第四步:判断“,r,=0”是否成立.若是,则,n,不是质数,结束算法;否则,将,i,的值增加1,仍,i,用表示.,第五步:判断“,i,(,n,-1)”是否成立.若是,则,n,是质数,结束算法;否则返回第三步.,例2.任意给定一个大于2的整数n,试设计一个程序或步骤对n是,第五步:判断,a,b,的长度是否小于,d,或,f,(,m,)是否等于0.若是，则,m,是方程的近似解；否则，返回第三步.,例3.用二分法设计一个求方程,x,2,-,2,=,0(,x,0),的近似根的算法.,第一步：令,f,(,x,)=,x,2,-,2，给定精确度,d,.,第二步：确定区间,a,b,满足,f,(,a,),f,(,b,)0.,例题讲解,第三步：取区间中点,m,=,第四步：若,f,(,a,),f,(,m,)ma,x,则ma,x,=,b,;,第四步:如果,c,ma,x,则ma,x,=,c,;,第五步:如果,d,ma,x,则ma,x,=,d,;,第六步:输出ma,x,.,点评:算法要求“按部就班”地做,每做一步都有唯一的结果,且有限步之后总能得到结果.,例4.写出一个能找出在a,b,c,d四个数中最大的数的算法.,例,5.,写出一个求有限整数列中的最大值的算法,.,S1:,先假定序列中的第一个整数为“最大值”,.,S2:,将序列中的下一个整数值与“最大值”比较,如果它大于此“最大值”，这时你就假定“最大值”是这个整数,.,S3:,如果序列中还有其他整数,.,重复,S2.,S4:,在序列中一直到没有可比的数为止,这时假定的“最大值”就是这个序列中的最大值,.,例5.写出一个求有限整数列中的最大值的算法.S1:先假定序列,1.知识结构,算法的概念,算法的步骤,算法的特点,算法,2.,算法的特点,:思路简单清晰,叙述复杂,步骤繁琐,计算量大,完全依靠人力难以完成.而这些恰恰就是计算机的特长,它能不厌其烦地完成枯燥的、重复的繁琐的工作.正因为这些,现代算法的作用之一就是使计算机代替人完成某些工作,这也是我们学习算法的重要原因之一.,课堂小结,1.知识结构算法的概念算法的步骤 算法的特点算法2.算法的特,小结,通过例题说明算法有两个主要特点：,（1）有限性 一个算法在执行有限个步,骤后必须结束；,（2）确定性 算法的每一个步骤和次序,应当是确定的,小结通过例题说明算法有两个主要特点：（1）有限性 一个算,学案,:删第1页例1，第2页3，,拓展提高2,完成:,学案 P.,1,-,2,华罗庚天才在于积累。,聪明在于勤奋，,布置作业,学案:删第1页例1，第2页3，完成:学案 P,