_111算法与程序框图_.ppt

问题的提出问题的提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如只够农夫带一样东西过河。问农夫该如何解此难题？何解此难题？方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；带狼狗到对岸，返回；4、带羊到对岸。带羊到对岸。1.1.1 算法的概念算法的概念问题问题请你写出解二元一次方程组的详细求解过请你写出解二元一次方程组的详细求解过程程.第一步第一步:+2得得:5x=1 第二步第二步:解解得得:第三步第三步:-2，得，得 5y=3 第四步：解第四步：解，得，得 第五步：得方程组的解第五步：得方程组的解 你能你能写出解一般的二元一次方程组的步写出解一般的二元一次方程组的步 骤吗？骤吗？第一步第一步,第二步第二步,解（解（3）得）得 思考 第四步第四步,解（解（4）得）得 第三步第三步,第五步第五步,得到方程得到方程组组的解的解为为 解解，得，得 将将带入带入得得 得得解解 得得第一步第一步：第二步：第二步：第三步：第三步：+2 2，得，得将将 代入代入,得得思考思考这这 两个解方程组的两个解方程组的算法算法的的适用范围有何不同？适用范围有何不同？第一步：第一步：第二步：第二步：第三步：第三步：第二步第二步：计算：计算第三步第三步：给出运算结果。：给出运算结果。第一步第一步:取取解方程组解方程组现在你对算法有了新现在你对算法有了新的认识了吗？的认识了吗？这些步骤就构成了解二元一次方程组的这些步骤就构成了解二元一次方程组的算法算法,我们可以根据这一算法编制计算机程序我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组让计算机来解二元一次方程组.算法的概念与特征算法的概念与特征算法算法(algorithm)这个词出现于这个词出现于12世纪世纪,指的是用阿拉伯数字进行算术运算的过程指的是用阿拉伯数字进行算术运算的过程.在数学上在数学上,现代意义上的现代意义上的“算法算法”通常是指通常是指可以用计算机按照一定规则解决某一类问题可以用计算机按照一定规则解决某一类问题的的明确和有限的程序或步骤明确和有限的程序或步骤,这些程序或步这些程序或步骤必须是明确和有效的骤必须是明确和有效的,而且能够在有限步而且能够在有限步之内完成之内完成.算法的概念算法的概念:算法是指解决给定问题的算法是指解决给定问题的有穷有穷操作步骤操作步骤的描述，的描述，简单的说，算法简单的说，算法就是解决问题的步骤和方法。就是解决问题的步骤和方法。(1)事实上算法并没有精确化的定义事实上算法并没有精确化的定义.(2)算法虽然没有一个明确的定义算法虽然没有一个明确的定义,但其特但其特点是鲜明的点是鲜明的,不仅要注意不仅要注意算法的程序性、有算法的程序性、有限性、构造性、精确性的特点，还应该充限性、构造性、精确性的特点，还应该充分理解算法问题的指向性，即算法往往指分理解算法问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有向解决某一类问题，泛泛地谈算法是没有意义的。意义的。说明说明 例题例题1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数.第一步第一步,用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以，所以2不能整除不能整除7.第二步第二步,用用3除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以，所以3不能整除不能整除7.第三步第三步,用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0，所以，所以4不能整除不能整除7.第五步第五步,用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以，所以6不能整除不能整除7.因此，因此，7是质数是质数.算法分析：算法分析：根据质数的定义，可以这样判断：依次用根据质数的定义，可以这样判断：依次用2-6除除7，如果他们中有一个能整除，如果他们中有一个能整除7，则，则7不是质数，否则不是质数，否则7是质数。具是质数。具体算法如下体算法如下;第四步第四步,用用5除除7,得到余数得到余数2.因为余数不为因为余数不为0，所以，所以5不能整除不能整除7.例题解析例题解析例题例题.(2)(2)设计一个算法判断设计一个算法判断3535是否为质数是否为质数.算法分析：算法分析：第一步第一步,用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0，所以，所以2不能整除不能整除35.第二步第二步,用用3除除35,得到余数得到余数2.因为余数不为因为余数不为0，所以，所以3不能整除不能整除35.第三步第三步,用用4除除35,得到余数得到余数3.因为余数不为因为余数不为0，所以，所以4不能整除不能整除7.第四步第四步,用用5除除35,得到余数得到余数0.因为余数为因为余数为0，所以，所以5能整除能整除35.因因 此，此，35不是质数不是质数.题后小结：题后小结：用语言描述一个算法用语言描述一个算法,最便捷的最便捷的方式就是按解决问题的步骤进行描述方式就是按解决问题的步骤进行描述.每一每一步做一件事情步做一件事情.任意给定一任意给定一任意给定一任意给定一个整数个整数个整数个整数n n(n n2)2)，试设计一，试设计一，试设计一，试设计一个程序或步个程序或步个程序或步个程序或步骤对骤对骤对骤对n n是否为是否为是否为是否为质数做出判质数做出判质数做出判质数做出判定。定。定。定。第一步，给定大于第一步，给定大于2 2的整数的整数n。第二步，令第二步，令i=2=2探究探究第三步，用第三步，用i除除n,得到余数得到余数r.第四步，判断第四步，判断“r=0”=0”是否成立，若是，是否成立，若是，则则n不是质数，结束算法；否则，将不是质数，结束算法；否则，将i的的值增加值增加1 1，仍用，仍用i表示。表示。第五步，判断第五步，判断“i(n-1)”-1)”是否成立，是否成立，若是，则若是，则n是质数，结束算法；否则，是质数，结束算法；否则，返回第三步。返回第三步。例例2.用二分法设计一个求方程用二分法设计一个求方程的近似根的算法的近似根的算法.二分法 对于区间对于区间a,b 上连续不断、且上连续不断、且f(a)f(b)0的函数的函数y=f(x),通过不断地通过不断地把函数把函数f(x)的零点所在的区间一分的零点所在的区间一分为二，使区间的两个端点逐步逼近为二，使区间的两个端点逐步逼近零点，进而得到零点或其近似值的零点，进而得到零点或其近似值的方法叫做方法叫做二分法二分法.第二步第二步,给定区间给定区间a,b,满足满足f(a)f(b)0算法步骤：算法步骤：第一步第一步,令令 ,给定精确度给定精确度d.第四步第四步,若若f(a)f(m)0,则含零点的区间为则含零点的区间为a,m；第三步第三步,取中间点取中间点将新得到的含零点的仍然记为将新得到的含零点的仍然记为a,b.第五步第五步,判断判断f(m)是否等于或者是否等于或者a,b的长的长度是否小于度是否小于d，若是，则，若是，则m是方程的近似解是方程的近似解;否否则，返回第三步则，返回第三步当当d d=0.005=0.005时，按照以上算法，可得下面表和图时，按照以上算法，可得下面表和图.a ab b|a-b|a-b|1 12 21 11 11.51.50.50.51.251.251.51.50.250.251.3751.3751.51.50.1250.1251.3751.3751.437 51.437 50.062 50.062 51.406 251.406 251.437 51.437 50.031 250.031 251.406 251.406 251.421 8751.421 8750.015 6250.015 6251.414 6251.414 6251.421 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 75 0.003 906 250.003 906 25y=x2-2121.51.3751.25 于是，开区间于是，开区间（1.4140625,1.41796875）中）中的实数都是当精确度为的实数都是当精确度为0.005时的原方程的近时的原方程的近似解似解.算法的基本特点算法的基本特点1、有穷性、有穷性 一个算法应包括有限的操作步骤，一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。能在执行有穷的操作步骤之后结束。2、确定性确定性 算法的计算规则及相应的计算步骤算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，必须是唯一确定的，既不能含糊其词，也不能有二义性。也不能有二义性。3、可行性可行性 算法中的每一个步骤都是可以在有算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得限的时间内完成的基本操作，并能得到确定的结果到确定的结果。注注:与一般的解决问题的过程比较与一般的解决问题的过程比较,算法有以算法有以下特征下特征:设计一个具体问题的算法时设计一个具体问题的算法时,与过去熟悉地与过去熟悉地解数学题的过程有直接的联系解数学题的过程有直接的联系,但这个过程必但这个过程必须被分解成若干个明确的步骤须被分解成若干个明确的步骤,而且这些步骤而且这些步骤必须是有效的必须是有效的.算法要算法要“面面俱到面面俱到”,不能省略任何一个细不能省略任何一个细小的步骤小的步骤,只有这样只有这样,才能在人设计出算法后才能在人设计出算法后,把具体的执行过程交给计算机完成把具体的执行过程交给计算机完成.计算机解决任何问题都要依赖计算机解决任何问题都要依赖于算法于算法.只有将解决问题的过程分只有将解决问题的过程分解为若干个明确的步骤解为若干个明确的步骤,即算法即算法,并用计算机能够接受的并用计算机能够接受的“语言语言”准确地描述出来准确地描述出来,计算机才能够解计算机才能够解决问题决问题.练习一练习一:任意给定一个正实数任意给定一个正实数,设计一个设计一个算法求以这个数为半径的圆的面积算法求以这个数为半径的圆的面积.算法分析算法分析:第一步第一步:输入任意一个正实数输入任意一个正实数r;第二步第二步:计算以计算以r为半径的圆的面积为半径的圆的面积S=r2;第三步第三步:输出圆的面积输出圆的面积.练习二练习二:任意给定一个大于任意给定一个大于1的正整数的正整数n,设计一个算法求出设计一个算法求出n的所有因数的所有因数.算法分析算法分析:第一步第一步:依次从依次从2(n-1)为除数去除为除数去除n,判断判断余数是否为余数是否为0,若是若是,则是则是n的因数的因数;若不是若不是,则不是则不是n的因数的因数.第二步第二步:在在n的因数中加入的因数中加入1和和n;第三步第三步:输出输出n的所有因数的所有因数.作业作业:课本课本P5页页T2(只需用自然语言写出算法步骤只需用自然语言写出算法步骤)再再 见见