《人教A版高中数学必修三1.1.1算法的概念 课件.ppt》由会员分享，可在线阅读，更多相关《人教A版高中数学必修三1.1.1算法的概念 课件.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.1.1 算法的概念我国古代的计算工具我国古代的计算工具世世界界上上第第一一台台电电子子计计算算机机我我国国第第一一台台电电子子计计算算机机 算筹、算盘、计算机等从古到今的计算算筹、算盘、计算机等从古到今的计算工具的基础都是工具的基础都是“算法算法”.算法对我们而言并算法对我们而言并不陌生，其实我们从小学就开始接触算法，不陌生，其实我们从小学就开始接触算法，例如，做四则运算要先乘除后加减、从里往例如，做四则运算要先乘除后加减、从里往外去括号外去括号、竖式笔算等都是算法，至于乘法、竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现口诀、珠算口诀更是算法的具体体现.在现代社会里，计算机
2、已经成为人们日常在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具听音乐、看电影、生活和工作不可缺少的工具听音乐、看电影、玩游戏、画卡通画、处理数据玩游戏、画卡通画、处理数据计算机几乎可计算机几乎可以是一个全能的助手，你可以用它来做你想做以是一个全能的助手，你可以用它来做你想做的任何事情那么，计算机是怎样工作呢？要的任何事情那么，计算机是怎样工作呢？要想弄清楚这个问题，就需要学习算法想弄清楚这个问题，就需要学习算法 l第一步：把冰箱门打开l第二步：把大象放进去l第三步：把冰箱门带上n n情境情境1 1：把大象放冰箱，共分几步把大象放冰箱，共分几步?情境情境2：农夫过河问题农夫过河问题
3、 有一个农夫带三只狼和三只羚羊过河，只有一条船，有一个农夫带三只狼和三只羚羊过河，只有一条船，同船可以容纳一个人和两只动物。没有人在的时候，如果同船可以容纳一个人和两只动物。没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊狼的数量不少于羚羊的数量，狼就会吃掉羚羊。农夫应农夫应该如何渡河？该如何渡河？河河 流流第一步：人带两只狼过河，自己返回；第一步：人带两只狼过河，自己返回；第二步：人带一只羊过河，并带两只狼返回；第二步：人带一只羊过河，并带两只狼返回；第三步：人带两只羊过河，自己返回；第三步：人带两只羊过河，自己返回；第四步：人带两只狼过河，自己返回；第四步：人带两只狼过河，自己
4、返回；第五步：人带一只狼过河第五步：人带一只狼过河算法自然语言描述：算法自然语言描述：如何求解二元一次方程组？如何求解二元一次方程组？回顾回顾二元一次方程组二元一次方程组的求解过程的求解过程.归纳它的步骤归纳它的步骤:第一步第一步:-2，得，得 5y=3 第三步第三步:第二步第二步:解解得得 y=第二步第二步:解解得得 y=思考？第二步：解第二步：解，得，得第一步：第一步：-，得，得 第三步：将第三步：将 代入代入，得，得 我们做每件事情都需要设计出我们做每件事情都需要设计出“行动步骤行动步骤”.上述上述步骤构成了解二元一次方程组的算法，步骤构成了解二元一次方程组的算法，我们可以进一步根据这一
5、算法编制计算机程序，我们可以进一步根据这一算法编制计算机程序，让计算机来解二元一次方程组让计算机来解二元一次方程组.1.1.算法的概念：算法的概念：在数学中在数学中“算法算法”通常是指按照一定的规则来通常是指按照一定的规则来解决的某一类问题的解决的某一类问题的明确明确和和有限有限的的步骤步骤。3.3.算法的基本思想与特征算法的基本思想与特征:2.2.算法的表示方法：算法的表示方法：自然语言、程序框图、程序语言自然语言、程序框图、程序语言(1)解决某一类问题解决某一类问题(2)在在有限步有限步之内完成之内完成(3)每一步都是明确的，有确定的结果和有效性每一步都是明确的，有确定的结果和有效性(4)
6、每一步具有顺序每一步具有顺序(5)解决问题的算法不唯一解决问题的算法不唯一(普遍性普遍性)(有限性有限性)(确定性与可行性确定性与可行性)(有有序性序性)(不唯不唯一一性性)练习练习判断下列关于算法的说法是否确：判断下列关于算法的说法是否确：1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的；2、算法必须在有限步操作之后停止；、算法必须在有限步操作之后停止；3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧义或模糊；义或模糊；4、算法执行后一定产生确定的结果、算法执行后一定产生确定的结果.练习练习判断下列关于算法的说法是否确：判断下列关于算法的说法是否确：
7、1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的；2、算法必须在有限步操作之后停止；、算法必须在有限步操作之后停止；3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧义或模糊；义或模糊；4、算法执行后一定产生确定的结果、算法执行后一定产生确定的结果.例题例题1(2).设计一个算法，判断设计一个算法，判断35是否为质数？是否为质数？(1).设计一个算法，判断设计一个算法，判断7是否为质数？是否为质数？只能被只能被1 1和自身整除的大于和自身整除的大于1 1的整数叫质数的整数叫质数.例题例题1(1).设计一个算法，判断设计一个算法，判断7是否为质数？是否为质
8、数？解：解：算法分析：算法分析：由质数的定义，可以这样判断由质数的定义，可以这样判断:依次用依次用26除除7,若它们中有一个能整除若它们中有一个能整除7，则，则7不是质数，否则不是质数，否则7是质数是质数.根据以上分析，可以写出如下的算法：根据以上分析，可以写出如下的算法：第一步第一步,用用2除除7,余数不为余数不为0,第二步第二步,用用3除除7,余数不为余数不为0,得到余数得到余数1.2不能整除不能整除7.得到余数得到余数1.3不能整除不能整除7.第三步第三步,用用4除除7,余数不为余数不为0,得到余数得到余数3.4不能整除不能整除7.第四步第四步,用用5除除7,余数不为余数不为0,得到余数
9、得到余数2.5不能整除不能整除7.第五步第五步,用用6除除7,余数不为余数不为0,得到余数得到余数1.6不能整除不能整除7.故故7是质数是质数.例题例题1(2).设计一个算法，判断设计一个算法，判断35是否为质数？是否为质数？解：解：根据以上分析，可以写出如下的算法：根据以上分析，可以写出如下的算法：第一步第一步,用用2除除35,余数不为余数不为0,第二步第二步,用用3除除35,余数不为余数不为0,得到余数得到余数1.2不能整除不能整除35.得到余数得到余数2.3不能整除不能整除35.第三步第三步,用用4除除35,余数不为余数不为0,得到余数得到余数3.4不能整除不能整除35.第四步第四步,用
10、用5除除35,余数为余数为0,得到余数得到余数0.5能整除能整除35.故故35不是质数不是质数.探究：探究：你能写出你能写出“判断整数判断整数n(n2)是否为质数是否为质数”的算法吗？的算法吗？【算法分析算法分析】对于对于任意任意的整数的整数n(n2)，若用，若用i表示表示2(n-1)中的任意中的任意整数，则整数，则“判断判断n是否为质数是否为质数”的算法包含下面的的算法包含下面的重复操作：重复操作：用用i除除n，得到余数，得到余数r，判断余数，判断余数r是否为是否为0，若为若为0，则，则n不是质数，否则将不是质数，否则将i 的值增加的值增加1，再执行同样的操作，一直到再执行同样的操作，一直到
11、i的值等于的值等于n-1为止为止.写出写出“判断整数判断整数n(n2)是否为质数是否为质数”的算法。的算法。解：解：第一步：给定大于第一步：给定大于2的整数的整数n；第二步：令第二步：令i=2；第三步：用第三步：用i除除n，得到余数，得到余数r；第四步：判断第四步：判断“r=0”是否成立，若是，则是否成立，若是，则n不是不是质数，结束算法；否则，将质数，结束算法；否则，将i的值增加的值增加1，仍用，仍用i表表示；示；第五步，判断第五步，判断“in-1”是否成立，若成立，则是否成立，若成立，则n是质数，结束算法；否则，返回第三步是质数，结束算法；否则，返回第三步.写出写出“判断整数判断整数n(n
12、2)是否为质数是否为质数”的算法。的算法。分析：分析：1二分法求方程近似解是通过求对应函二分法求方程近似解是通过求对应函数的近似零点得到的，所以首先要建立数的近似零点得到的，所以首先要建立函数，而且要有具体精确度要求，因此函数，而且要有具体精确度要求，因此第一步应该怎么做？第一步应该怎么做？2二分法分的是什么？二分法分的是什么？3如何确定新区间的端点？如何确定新区间的端点？4如何表达出反复二分区间的过程？如何表达出反复二分区间的过程？例例2、用二分法设计一个求方程用二分法设计一个求方程x2-2=0的近的近似解的算法（精确度为似解的算法（精确度为0.005）.什么是二分法？什么是二分法？对于区间
13、对于区间a,b a,b 上连续不断、且上连续不断、且f(a)f(b)0f(a)f(b)0)-2(x0)xa 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 062 51.414 062 51.4
14、21 8751.421 8750.007 812 50.007 812 51.414 062 51.414 062 51.417 968 751.417 968 750.003 906 250.003 906 25对于方程对于方程x x2 2-2=0(x0),-2=0(x0),给定给定d=0.005.d=0.005.此步骤也是求的近似值的一个算法此步骤也是求的近似值的一个算法.例例2、用二分法设计一个求方程用二分法设计一个求方程x2-2=0的近的近似根的算法（精确度为似根的算法（精确度为0.005）.第一步：第一步：令令f(x)=x2-2，给定精确度，给定精确度d.根据以上分析，可以写出如下的
15、算法：根据以上分析，可以写出如下的算法：1、任意给定一个正实数，设计一个算法求以、任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积。这个数为半径的圆的面积。算法步骤：算法步骤：第一步：给定一个正实数第一步：给定一个正实数 r.第二步：计算以第二步：计算以r为半径的圆的面积为半径的圆的面积 .第三步：得到圆的面积第三步：得到圆的面积S.练一练练一练 2、任意给定一个大于、任意给定一个大于1的正整数的正整数n，设计一个算，设计一个算法求出法求出n的所有因数。的所有因数。算法步骤：算法步骤：第一步：给定一个大于第一步：给定一个大于1的正整数的正整数n.第二步：令第二步：令i=1.（i表示表
16、示1n中的任意整数）中的任意整数）.第三步：用第三步：用i除除n，得到余数，得到余数r.第四步：判断第四步：判断“r=0”是否成立，若是，则是否成立，若是，则i是是n的因数；的因数；否则否则i不是不是n的因数的因数.第五步：将第五步：将i的值增加的值增加1，仍用，仍用i表示表示.第六步，判断第六步，判断“i n”是否成立，若是，则结束算法；是否成立，若是，则结束算法；否则，返回第三步否则，返回第三步.例例3.写出一个求整数写出一个求整数a、b、c最大值的算法最大值的算法解：解：步骤一步骤一:max=a步骤二步骤二:如果如果bmax，则，则max=b.步骤三步骤三:如果如果cmax，则，则max
17、=c.思考：思考：你能写出一个求有限整数列中的最大值的算法吗？你能写出一个求有限整数列中的最大值的算法吗？思考：思考：写出一个求有限整数列中的最大值的算法。写出一个求有限整数列中的最大值的算法。步骤一步骤一:先假定序列中的第一个整数为先假定序列中的第一个整数为“最大值最大值”。步骤二步骤二:将序列中的下一个整数值与将序列中的下一个整数值与“最大值最大值”比较，比较，如果它大于此如果它大于此“最大值最大值”，这时你就假定，这时你就假定“最大值最大值”是这个整数。是这个整数。步骤三步骤三:如果序列中还有其他整数，重复如果序列中还有其他整数，重复步骤二步骤二。步骤四步骤四:在序列中一直到没有可比的数为止，在序列中一直到没有可比的数为止，这时假定的这时假定的“最大值最大值”就是这个序列中的最大值就是这个序列中的最大值.解：解：