人教版算法的基本思想 新课标 人教.ppt

《人教版算法的基本思想 新课标 人教.ppt》由会员分享，可在线阅读，更多相关《人教版算法的基本思想 新课标 人教.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法的基本思想算法的基本思想2021/8/9 星期一1你愿意不厌其烦地去作枯燥的、重复的、你愿意不厌其烦地去作枯燥的、重复的、繁琐的工作吗？繁琐的工作吗？用计算机代替人来完成这些工作，这恰恰用计算机代替人来完成这些工作，这恰恰是计算机的特长。是计算机的特长。电脑发展到今天，能有如此广泛而神奇的应用，电脑发展到今天，能有如此广泛而神奇的应用，除了半导体集成电路芯片的制造工艺提高以外，除了半导体集成电路芯片的制造工艺提高以外，主要靠软件，而软件的核心是主要靠软件，而软件的核心是算法算法。算法初步算法初步2021/8/9 星期一2“猜数猜数”游戏游戏竞猜者如在规定的时间内猜出某种商品的价格，竞猜者如

2、在规定的时间内猜出某种商品的价格，就可获得该件商品。现有一商品，价格在就可获得该件商品。现有一商品，价格在01000之间，采取怎样的策略才能在较短的时之间，采取怎样的策略才能在较短的时间内说出正确的答案呢间内说出正确的答案呢？2021/8/9 星期一3什么是算法？什么是算法？算法（算法（algorithm）一词源于算术）一词源于算术(algorism),算术算术方法的原义是一个由已知推求未知的运算过程。后方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般来，人们把它推广到一般,算法是解决某类问题的一算法是解决某类问题的一系列步骤或程序。系列步骤或程序。例如，人们在计算过程中，先

3、乘除，后加减，从内例如，人们在计算过程中，先乘除，后加减，从内到外去括号等规则，都是按部就班必须遵守的算法。到外去括号等规则，都是按部就班必须遵守的算法。又如求解方程的步骤；发送电子邮件；计算机动画又如求解方程的步骤；发送电子邮件；计算机动画的设计等的设计等2021/8/9 星期一4例例1 在给定素数表的条件下，设计算法，在给定素数表的条件下，设计算法，将将936分解成素因数的乘积分解成素因数的乘积.1.1.判断判断936936是否为素数：否是否为素数：否.2.2.确定确定936936的最小素因数：的最小素因数：2.2.936936246824683.3.判断判断468468是否为素数：否是否

4、为素数：否.4.4.确定确定468468的最小素因数：的最小素因数：2.2.93693622234222345.5.判断判断234234是否为素数：否是否为素数：否.6.6.确定确定234234的最小素因数：的最小素因数：2.2.936936222221171177.7.判断判断117117是否为素数：否是否为素数：否.8.8.确定确定117117的最小素因数：的最小素因数：3.3.93693622222339399.9.判断判断3939是否为素数：否是否为素数：否.10.10.确定确定3939的最小素因数：的最小素因数：3.3.93693622222331331311.11.判断判断1313

5、是否为素数：是是否为素数：是.2021/8/9 星期一5(1)(1)输入三个数：输入三个数：a,b,ca,b,c(2)(2)比较比较a a与与b b的大小，的大小，maxa,b=Mmaxa,b=M(3)(3)比较比较MM与与c c的大小，的大小，maxM,c=N.maxM,c=N.若若ab,ab,则则M=b;M=b;否则否则M=a.M=a.若若Mc,Mc,则则N=c;N=c;否则否则N=M.N=M.(4)(4)输出输出N.N.N N为三数中的最大数为三数中的最大数.解解解解:设计算法，找出三个数中的最大设计算法，找出三个数中的最大。例例22021/8/9 星期一6例例3 设计一个算法，求设计一

6、个算法，求840与与1764的最大公因数的最大公因数.1.1.先将先将840840进行素因数分解：进行素因数分解：8408402 23 33573572.2.将将17641764进行素因数分解：进行素因数分解：176417642 22 2332 2772 23.3.确定它们的公共素因数：确定它们的公共素因数：2 2，3 3，7 72 22 2373784844.4.确定它们的公共素因数的指数：确定它们的公共素因数的指数：2 2，1 1，1 15.5.最大公因数为：最大公因数为：练习练习1 1 请设计一个算法，求三个数：请设计一个算法，求三个数：324 324，440440，556556的最大公

7、因数？的最大公因数？2021/8/9 星期一7 设计一个算法，求设计一个算法，求100以内能被以内能被3整数的数。整数的数。分析问题：分析问题：设能被设能被3整除的数为整除的数为I，令，令I1，2，3，100，如果，如果I能能被被3整数，则输出整数，则输出I，否则，检查下一个，知道，否则，检查下一个，知道I100为止。为止。设计算法：设计算法：1）令）令I1；（2）如果）如果I能被能被3整除的数，则输出整除的数，则输出I；（3）I=I+1;（4）如果）如果I=100,则返回第（则返回第（2）步；）步；（5）结束。）结束。例例42021/8/9 星期一81.1.计算判别式计算判别式b b2 2-

8、4ac.-4ac.2.2.判断判断的符号：的符号：（1 1）若）若0,0,0,则输出方程有两不等实数解：则输出方程有两不等实数解：解：解：解：解：描述一元二次方程求解的算法描述一元二次方程求解的算法例例52021/8/9 星期一9有有9 9枚银元，其中有一枚略轻的是假银元，枚银元，其中有一枚略轻的是假银元，找假银元找假银元问题问题你能用天平（不用砝码）将假银元找出来吗？你能用天平（不用砝码）将假银元找出来吗？例例62021/8/9 星期一10设给定的两个正整数为设给定的两个正整数为m和和n，求它们的最大，求它们的最大公约数的步骤公约数的步骤(算法算法)为：为：（1）以）以m除以除以n，令所得的

9、余数为，令所得的余数为r（r必小于必小于n）；）；（2）若）若r0，则输出结果，则输出结果n，算法结束；否则，继续步骤（，算法结束；否则，继续步骤（3)（3）令）令m=n，n=r,并返回步骤（并返回步骤（1）继续进行。）继续进行。欧几里得算法欧几里得算法辗转相除法辗转相除法例例72021/8/9 星期一11令士兵从令士兵从1 13 3报数，结果最后一个士兵报报数，结果最后一个士兵报2 2；例例8令士兵从令士兵从1 15 5报数，结果最后一个士兵报报数，结果最后一个士兵报3 3；令士兵从令士兵从1 17 7报数，结果最后一个士兵报报数，结果最后一个士兵报4 4；韩信点兵：韩信点兵：你能算出韩信至

10、少有多少兵吗？你能算出韩信至少有多少兵吗？2021/8/9 星期一12分油分油问题问题 一个大油瓶装一个大油瓶装 8kg 8kg油，还有两个空油瓶，油，还有两个空油瓶，一个能装一个能装5kg,5kg,另一个能装另一个能装3kg,3kg,请设计一种算法，请设计一种算法，将这将这8kg8kg油平均分成两份油平均分成两份.1.1.将这将这8kg8kg油倒满油倒满5kg5kg的油瓶的油瓶.2.2.将将5kg5kg油瓶中的油倒满油瓶中的油倒满3kg3kg的油瓶的油瓶.3.3.将将3kg3kg油倒入油倒入8kg8kg的油瓶的油瓶.4.4.将这将这5kg5kg油瓶中的油瓶中的2kg2kg油倒入油倒入3kg3

11、kg的油瓶的油瓶.5.5.将将8kg8kg油瓶中的油倒满油瓶中的油倒满5kg5kg的油瓶的油瓶.6.6.将将5kg5kg油瓶中的油倒满油瓶中的油倒满3kg3kg的油瓶的油瓶.7.7.将这将这3kg3kg油倒入油倒入8kg8kg的油瓶的油瓶.例例92021/8/9 星期一13 设区间设区间aa，bb是方程是方程f(x)=0f(x)=0的有解区间，的有解区间，画出用二分法算法求方程画出用二分法算法求方程f(x)=0f(x)=0在区间在区间aa，bb上的一个近似解的流程图，要求精确度为上的一个近似解的流程图，要求精确度为 .1.1.确定有解区间确定有解区间a,b (f(a)f(b)0)a,b (f(

12、a)f(b)0)2.2.取取a,ba,b的中点的中点x=x=3.3.计算计算f()f()的值的值（2)2)如果不为如果不为0 0，分两种情况确定新的有解区间，分两种情况确定新的有解区间4.4.判断判断 是否为是否为0 0（1 1）如果为如果为0 0，就是方程的解就是方程的解.5.5.判断新的有解区间长度是否小于精确度判断新的有解区间长度是否小于精确度（2 2）如果是，则取新区间的中点为方程的解）如果是，则取新区间的中点为方程的解（1 1）如果不是，则在新区间的基础上取中点，重复上述步骤）如果不是，则在新区间的基础上取中点，重复上述步骤例例102021/8/9 星期一142021/8/9 星期一15