算法的基本思想 新课标 人教版 课件VIP专享VIP免费

算法的基本思想•你愿意不厌其烦地去作枯燥的、重复的、繁琐的工作吗？•用计算机代替人来完成这些工作，这恰恰是计算机的特长。•电脑发展到今天，能有如此广泛而神奇的应用，除了半导体集成电路芯片的制造工艺提高以外，主要靠软件，而软件的核心是算法。算法初步“猜数”游戏•竞猜者如在规定的时间内猜出某种商品的价格，就可获得该件商品。现有一商品，价格在0~1000之间，采取怎样的策略才能在较短的时间内说出正确的答案呢？•什么是算法？•算法（algorithm）一词源于算术(algorism),算术方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般,算法是解决某类问题的一系列步骤或程序。•例如，人们在计算过程中，先乘除，后加减，从内到外去括号等规则，都是按部就班必须遵守的算法。•又如求解方程的步骤；发送电子邮件；计算机动画的设计等例例11在给定素数表的条件下，设计算法，将936分解成素因数的乘积.1.判断936是否为素数：否.2.确定936的最小素因数：2.936＝2×4683.判断468是否为素数：否.4.确定468的最小素因数：2.936＝2×2×2345.判断234是否为素数：否.6.确定234的最小素因数：2.936＝2×2×2×1177.判断117是否为素数：否.8.确定117的最小素因数：3.936＝2×2×2×3×399.判断39是否为素数：否.10.确定39的最小素因数：3.936＝2×2×2×3×3×1311.判断13是否为素数：是.(1)输入三个数：a,b,c(2)比较a与b的大小，max{a,b}=M(3)比较M与c的大小，max{M,c}=N.若a0,则输出方程有两不等实数解：abxx221abxabx2,221解：解：描述一元二次方程求解的算法例例55有9枚银元，其中有一枚略轻的是假银元，找假银元问题问题你能用天平（不用砝码）将假银元找出来吗？例例66设给定的两个正整数为m和n，求它们的最大公约数的步骤(算法)为：（1）以m除以n，令所得的余数为r（r必小于n）；（2）若r＝0，则输出结果n，算法结束；否则，继续步骤（3)（3）令m=n，n=r,并返回步骤（1）继续进行。欧几里得算法——辗转相除法例例77令士兵从1～3报数，结果最后一个士兵报2；例例88令士兵从1～5报数，结果最后一个士兵报3；令士兵从1～7报数，结果最后一个士兵报4；韩信点兵：你能算出韩信至少有多少兵吗？分油问题问题一个大油瓶装8kg油，还有两个空油瓶，一个能装5kg,另一个能装3kg,请设计一种算法，将这8kg油平均分成两份.1.将这8kg油倒满5kg的油瓶.2.将5kg油瓶中的油倒满3kg的油瓶.3.将3kg油倒入8kg的油瓶.4.将这5kg油瓶中的2kg油倒入3kg的油瓶.5.将8kg油瓶中的油倒满5kg的油瓶.6.将5kg油瓶中的油倒满3kg的油瓶.7.将这3kg油倒入8kg的油瓶.例例99设区间[a，b]是方程f(x)=0的有解区间，画出用二分法算法求方程f(x)=0在区间[a，b]上的一个近似解的流程图，要求精确度为.1.确定有解区间[a,b](f(a)·f(b)<0)2.取[a,b]的中点x=3.计算f()的值（2)如果不为0，分两种情况确定新的有解区间4.判断是否为0)2(abf＋（1）如果为0，就是方程的解.2abx5.判断新的有解区间长度是否小于精确度（2）如果是，则取新区间的中点为方程的解（1）如果不是，则在新区间的基础上取中点，重复上述步骤2ba2ba例例1010