算法的概念课件.ppt

1、 20 20 世纪最伟大的科学技术发明世纪最伟大的科学技术发明是计算机是计算机.没有软件的支持，计算机没有软件的支持，计算机只是一堆废铁而已只是一堆废铁而已.软件的核心就是算法软件的核心就是算法 ！1.1.1算法的概念算法的概念主页主页【1】一个农夫带着一条狼、一头山羊和一筐蔬】一个农夫带着一条狼、一头山羊和一筐蔬菜要过河菜要过河,但只有一条小船但只有一条小船.乘船时乘船时,农夫只能带农夫只能带一样东西一样东西.当农夫在场的时候当农夫在场的时候,这三样东西相安无这三样东西相安无事事.一旦农夫不在一旦农夫不在,狼会吃羊狼会吃羊,羊会吃菜羊会吃菜.请设计一请设计一个算法个算法,使农夫能安全地将这三

2、样东西带过河使农夫能安全地将这三样东西带过河.第一步第一步:农夫带羊过河农夫带羊过河;第二步第二步:农夫独自回来农夫独自回来;第三步第三步:农夫带狼过河农夫带狼过河;第四步第四步:农夫带羊回来农夫带羊回来;第五步第五步:农夫带蔬菜过河农夫带蔬菜过河;第六步第六步:农夫独自回来农夫独自回来;第七步第七步:农夫带羊过河农夫带羊过河.1.1.1算法的概念算法的概念主页主页 一般地一般地,对于一类问题的机械式地、统一对于一类问题的机械式地、统一地、按部就班地求解过程称为算法地、按部就班地求解过程称为算法(algorithm)(algorithm)它是解决某一问题的程序或步骤它是解决某一问题的程序或步骤

3、.按照这样的理解按照这样的理解,我们可以设计出很多具我们可以设计出很多具体数学问题的算法体数学问题的算法.下面看几个例子下面看几个例子:所谓所谓“算法算法”就是解题方法的精确描述就是解题方法的精确描述.从更广义的角度来看从更广义的角度来看,并不是只有并不是只有“计算计算”的问的问题才有算法题才有算法,日常生活中处处都有日常生活中处处都有.如如歌谱是一首歌谱是一首歌曲的算法歌曲的算法;菜谱菜谱是做菜的算法是做菜的算法;珠算口诀珠算口诀是使是使用算盘的算法用算盘的算法;空调说明书是空调使用的算法等空调说明书是空调使用的算法等.1.1.1算法的概念算法的概念主页主页解：第一步解：第一步:+2,得得第

4、二步第二步:解解,得得机械的统一的方法机械的统一的方法5x=1.1.5x 第三步第三步:-2,得得5y=3.第四第四 步步:解解,得得3.5y 第五第五 步步:得到方程组的解为得到方程组的解为1,53.5xy 例例1.写出解二元一次方程组写出解二元一次方程组 的一个算法的一个算法.21,21xyxy 1.1.1算法的概念算法的概念主页主页x练练1 1.写写出出解解方方程程2 2+3 3=0 0的的一一个个算算法法.xS1:移项,得 2=-3.3 3S S2 2:去去系系数数 得得=-.2 2,xabS S1 1:令令=2 2,=3 3.算法1算法2S S2 2:计计算算=-.bxa问问:ax+

5、b=0?,.abS1:输入 S S2 2:若若0 0,则则 =-.baxa abx S S3 3:若若0 0，0 0,则则 R R.S S4 4:若若0 0，0 0,则则 .aba 1.1.1算法的概念算法的概念主页主页练练2.2.写出求写出求1+2+3+4+51+2+3+4+5的一个算法的一个算法.算法算法1 1：S1:S1:计算计算1+21+2得到得到3 3；S2:S2:将第一步中的运算结果将第一步中的运算结果3 3与与3 3相加得到相加得到6 6；S3:S3:将第二步中的运算结果将第二步中的运算结果6 6与与4 4相加得到相加得到1010；S4:S4:将第三步中的运算结果将第三步中的运算

6、结果1010与与5 5相加得到相加得到15.15.算法算法2:S1：取：取n=5.(1).2n n S2：计算：计算S3：输出运算结果：输出运算结果.同一问题的解决算法一般是不唯一的同一问题的解决算法一般是不唯一的1.1.1算法的概念算法的概念主页主页第一步第一步:计算计算12,得得2;第二步第二步:将第一步中的运算结果将第一步中的运算结果2与与3相乘得相乘得6;第三步第三步:将第二步中的运算结果将第二步中的运算结果6与与4相乘得相乘得24;第四步第四步:将第三步中的运算结果将第三步中的运算结果24与与5相乘得相乘得120;第五步第五步:将第四步中的运算结果将第四步中的运算结果120与与6相乘

7、得相乘得720.练练3.求求123456的值，写出其算法的值，写出其算法.1.1.1算法的概念算法的概念主页主页 在在数学数学中中,算法通常是指按照一定规则解算法通常是指按照一定规则解决某一类问题的明确的有限的步骤决某一类问题的明确的有限的步骤.现在现在,算法算法通常可以编成计算机程序通常可以编成计算机程序,让计算机执行并解让计算机执行并解决问题决问题.1.1.算法的定义算法的定义算法算法:广义上讲广义上讲，做任何事情都有一定的步，做任何事情都有一定的步骤骤,为解决一个问题而采取的方法和步骤就是为解决一个问题而采取的方法和步骤就是算法算法.算法过程算法过程:要能一步一步执行，每一步执行要能一步

8、一步执行，每一步执行的操作的操作,必须确切，不能含混不清楚，而且必须确切，不能含混不清楚，而且经过有限步后能得出结果经过有限步后能得出结果.1.1.1算法的概念算法的概念主页主页小结小结通过练习说明算法有三个主要特点：通过练习说明算法有三个主要特点：（3 3）确定性）确定性 算法的每一个步骤和次序算法的每一个步骤和次序 应当是确定的应当是确定的（2 2）有限性）有限性 一个算法在执行有限个步一个算法在执行有限个步 骤后必须结束；骤后必须结束；（1 1）可行性）可行性 一个算法必须一步步可执一个算法必须一步步可执 行行1.1.1算法的概念算法的概念主页主页【1】有人对歌德巴赫猜想】有人对歌德巴赫

9、猜想“任何大于任何大于4的偶数的偶数都能写成两个奇质数之和都能写成两个奇质数之和”设计了如下操作步设计了如下操作步骤：骤：第一步：检验第一步：检验6=3+36=3+3第二步：检验第二步：检验8=3+58=3+5利用计算机无穷地进行下去！利用计算机无穷地进行下去！利用这种程序能够证明猜想的正确性吗？利用这种程序能够证明猜想的正确性吗？第三步：检验第三步：检验10=5+510=5+5 1.1.1算法的概念算法的概念主页主页【2 2】问要把大象装冰箱，分几步？】问要把大象装冰箱，分几步？答：分三步：答：分三步：第一步：打开冰箱门第一步：打开冰箱门.第二步：把大象装冰箱第二步：把大象装冰箱.第三步：关

10、上冰箱门第三步：关上冰箱门.对算法你有新对算法你有新的认识了吗？的认识了吗？1.1.1算法的概念算法的概念主页主页第一步第一步:用用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.因为余数不为因

11、为余数不为0,所以所以6不能整除不能整除7.例例2.(1)2.(1)设计一个算法设计一个算法,判断判断7 7是否为质数是否为质数.1.1.1算法的概念算法的概念主页主页例例2.2.(2)(2)设计一个算法设计一个算法,判断判断3535是否为质数是否为质数.第一步第一步:用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0,所以所以2不能整除不能整除35.第二步第二步:用用3除除35,得到余数得到余数2.因为余数不为因为余数不为0,所以所以3不能整除不能整除35.第三步第三步:用用4除除35,得到余数得到余数3.因为余数不为因为余数不为0,所以所以4不能整除不能整除35.第四步第四步:

12、用用5除除35,得到余数得到余数0.因为余数为因为余数为0,所以所以5能整除能整除35.因此因此,35不是质数不是质数.1.1.1算法的概念算法的概念主页主页例例2.任意给定一个大于任意给定一个大于2的整数的整数n,试设计一个试设计一个程序或步骤对程序或步骤对n是否为质数做出判定是否为质数做出判定.第二步第二步:令令i=2.第一步：第一步：给定一个大于给定一个大于2的整数的整数n.第三步第三步:用用 i 除除n,得到得到余数余数r.解析解析:n是否为质数是否为质数 2 2(n-1)-1)这是判断一这是判断一个大于个大于1的整数的最基本算法的整数的最基本算法.第四步第四步:判断判断“r=0”=0

13、”是否成立是否成立.若是若是,则则n不是质不是质数数,结束算法结束算法;否则否则,将将i的值增加的值增加1,1,仍仍i用表示用表示.第五步第五步:判断判断“i(n-1)”-1)”是否成立是否成立.若是若是,则则n是质数是质数,结束算法结束算法;否则返回第三步否则返回第三步.1.1.1算法的概念算法的概念主页主页第五步第五步:判断判断a,b的长度是否小于的长度是否小于d 或或f(m)是否是否等于等于0.若是，则若是，则m是方程的近似解；否则，返是方程的近似解；否则，返回第三步回第三步.例例3.3.用二分法设计一个求方程用二分法设计一个求方程 x2-2=0(x0)的的近似根的算法近似根的算法.第一

14、步：令第一步：令f(x)=x2-2，给定精确度，给定精确度d.第二步：确定区间第二步：确定区间a,b,满足满足f(a)f(b)0.2ab 第三步：取区间中点第三步：取区间中点m=第四步：若第四步：若f(a)f(m)max,则则max=b;第四步第四步:如果如果cmax,则则max=c;第五步第五步:如果如果dmax,则则max=d;第六步第六步:输出输出max.点评点评:算法要求算法要求“按部就班按部就班”地做地做,每做一步都每做一步都有唯一的结果有唯一的结果,且有限步之后总能得到结果且有限步之后总能得到结果.1.1.1算法的概念算法的概念主页主页例例5.写出一个求有限整数列中的最大值的算法写

15、出一个求有限整数列中的最大值的算法.S1:先假定序列中的第一个整数为先假定序列中的第一个整数为“最大值最大值”.S2:将序列中的下一个整数值与将序列中的下一个整数值与“最大值最大值”比较比较,如果它大于此如果它大于此“最大值最大值”，这时你就假，这时你就假定定“最大值最大值”是这个整数是这个整数.S3:如果序列中还有其他整数如果序列中还有其他整数.重复重复S2.S4:在序列中一直到没有可比的数为止在序列中一直到没有可比的数为止,这时这时假定的假定的“最大值最大值”就是这个序列中的最大值就是这个序列中的最大值.1.1.1算法的概念算法的概念主页主页1.1.知识结构知识结构算法的概念算法的概念算法

16、的步骤算法的步骤 算法的特点算法的特点算法算法2.2.算法的特点算法的特点:思路简单清晰思路简单清晰,叙述复杂叙述复杂,步骤步骤繁琐繁琐,计算量大计算量大,完全依靠人力难以完成完全依靠人力难以完成.而这些而这些恰恰就是计算机的特长恰恰就是计算机的特长,它能不厌其烦地完成枯它能不厌其烦地完成枯燥的、重复的繁琐的工作燥的、重复的繁琐的工作.正因为这些正因为这些,现代算现代算法的作用之一就是使计算机代替人完成某些工法的作用之一就是使计算机代替人完成某些工作作,这也是我们学习算法的重要原因之一这也是我们学习算法的重要原因之一.1.1.1算法的概念算法的概念主页主页小结小结通过例题说明算法有两个主要特点：通过例题说明算法有两个主要特点：（1 1）有限性）有限性 一个算法在执行有限个步一个算法在执行有限个步 骤后必须结束；骤后必须结束；（2 2）确定性）确定性 算法的每一个步骤和次序算法的每一个步骤和次序 应当是确定的应当是确定的学案学案:删第删第1 1页例页例1 1，第，第2 2页页3 3，拓展提高拓展提高2 2完成完成:学案学案 P.1-2华罗庚华罗庚天才在于积累。天才在于积累。聪明在于勤奋，聪明在于勤奋，