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

算法的基本思想,你愿意不厌其烦地去作枯燥的、重复的、繁琐的工作吗？用计算机代替人来完成这些工作，这恰恰是计算机的特长。电脑发展到今天，能有如此广泛而神奇的应用，除了半导体集成电路芯片的制造工艺提高以外，主要靠软件，而软件的核心是算法。,算法初步,“猜数”游戏竞猜者如在规定的时间内猜出某种商品的价格，就可获得该件商品。现有一商品，价格在01000之间，采取怎样的策略才能在较短的时间内说出正确的答案呢？,算法,什么是算法？算法（algorithm）一词源于算术(algorism),算术方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般,算法是解决某类问题的一系列步骤或程序。例如，人们在计算过程中，先乘除，后加减，从内到外去括号等规则，都是按部就班必须遵守的算法。又如求解方程的步骤；发送电子邮件；计算机动画的设计等,算法,例1,在给定素数表的条件下，设计算法，将936分解成素因数的乘积.,1.判断936是否为素数：否.,2.确定936的最小素因数：2.,9362468,3.判断468是否为素数：否.,4.确定468的最小素因数：2.,93622234,5.判断234是否为素数：否.,6.确定234的最小素因数：2.,936222117,7.判断117是否为素数：否.,8.确定117的最小素因数：3.,936222339,9.判断39是否为素数：否.,10.确定39的最小素因数：3.,9362223313,11.判断13是否为素数：是.,(1)输入三个数：a,b,c,(2)比较a与b的大小，maxa,b=M,(3)比较M与c的大小，maxM,c=N.,若ab,则M=b;否则M=a.,若Mc,则N=c;否则N=M.,(4)输出N.,N为三数中的最大数.,解:,设计算法，找出三个数中的最大。,例2,例3,设计一个算法，求840与1764的最大公因数.,1.先将840进行素因数分解：,84023357,2.将1764进行素因数分解：,1764223272,3.确定它们的公共素因数：,2，3，7,223784,4.确定它们的公共素因数的指数：,2，1，1,5.最大公因数为：,练习1请设计一个算法，求三个数：324，440，556的最大公因数？,设计一个算法，求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）结束。,例4,1.计算判别式b2-4ac.,2.判断的符号：,（1）若0,则输出方程有两不等实数解：,解：,描述一元二次方程求解的算法,例5,有9枚银元，其中有一枚略轻的是假银元，,找假银元问题,你能用天平（不用砝码）将假银元找出来吗？,例6,设给定的两个正整数为m和n，求它们的最大公约数的步骤(算法)为：,（1）以m除以n，令所得的余数为r（r必小于n）；,（2）若r0，则输出结果n，算法结束；否则，继续步骤（3),（3）令m=n，n=r,并返回步骤（1）继续进行。,欧几里得算法辗转相除法,例7,令士兵从13报数，结果最后一个士兵报2；,例8,令士兵从15报数，结果最后一个士兵报3；,令士兵从17报数，结果最后一个士兵报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的油瓶.,例9,设区间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.判断是