算法案例教案4苏教版必修.doc

第八课时 算法案例教学目标：本节通过算法案例的学习，进一步理解算法的含义，掌握算法设计的常用方法.教学重点：如何在伪代码中运用条件语句.教学难点：如何在伪代码中运用条件语句.教学过程：.课题导入1.中国古代数学中算法的内容是非常丰富的，比如，中国古代数学著作九章算术中介绍了下述“约分术”：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”给出了求任意两个数的最大公约数的一种算法，被后人称为“更相减损术”.这种方法与欧氏的辗转相除法异曲同工，本质上是相同的.2.中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的张丘建算经中的百鸡问题标志着中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.研究不定方程要解决三个问题：判断何时有解；有解时决定解的个数；求出所有的解.二分法是用计算机求解多项式方程的一种常用方法.基本思想是：如果取a，b的中点x0=（a+b）/2；若f(x0)=0，则x0就是方程的根，若f(a)f(x0)0，则解在（x0，b）上，以x0代替a，否则解在（a，x0）之间，以x0代替b，重复上述步骤，直到|ab|c，c是一个很小的正数，计算终止，x0就是方程的根.讲授新课例1：古今中外，许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值，一代代的数学家为这个神秘的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率.“割圆术”被称为千古绝技，它的原理是用圆内接正多边形的面积去逼近圆的面积，具体计算如下：在单位圆内作内接正六边形，其面积记为A1，边长记为a1，在此基础上作圆内接正12边形，面积记为A2，边长为a2一直做下去，记该圆的内接正62n1边形面积为An，边长为an.由于所考虑的是单位圆，计算出的An即为圆周率的近似值，n越大，An与越接近.你能设计这样计算圆周率的一个算法吗？我的思路：应首先推导出an，an1，An，An1的关系.如图，设PQ为圆内接正62n1边形的一边，即PQ=an1，OR为与PQ垂直的半径，R为PQ弧的平分点，显然PR=an.a1=1，an=PR=（n=2，3，4），A1=61=，An=62n1|OR|PT|=32n2an1（n=2，3，4）.通过上面两式，从a11开始进行迭代，可逐步计算出an与An.由于所考虑的是单位圆，计算出的An即为圆周率的近似值，n越大，An与越接近.算法和流程图如下：BeginRead n1aFor I from 2 to nA32I2aaSqrt22Sqrt1a2/4；Print I，A，aEnd forEnd流程图：例2：有一个故事是讲唐代大官杨埙提拔官员的经过.他让两个资格职位相同的候选人解答下面这个问题，谁先答出就提拔谁.“有人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹.若每人分6匹，就剩5匹；若每人分7匹，就差8匹.问共有强盗几个？布匹多少？”你能用一个简单算式求出强盗个数和布匹数吗？我的思路：这个问题可看作二元一次方程组问题.问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分.中国古代的九章算术一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为“盈不足术”.这种算法可以概括为两句口诀：有余加不足，大减小来除.公式：（盈不足）两次所得之差人数，每人所得数人数盈物品总数，求得强盗有（85）（76）13（人），布匹有613583（匹）.伪代码：Read a，b，c，dx（a+b）/（dc）ycx+aprint x，y流程图：例3：由F0=1，F1=1，Fn=Fn2+Fn1所定义的数列Fn，称为斐波那契数列，试设计一个求数列的前100项的值的算法，画出流程图并用伪代码表示.我的思路：数列Fn有个特点，前两个数都是1，从第3个数开始，每个数都是前两个数的和，例如：3是1和2的和；13是5和8的和等等.此问题的算法用流程图和伪代码表示：a1；b1；n1；输出n，；while nb），求它们的最大公约数.解析：求两个正整数a、b（ab）的最大公约数，可以归结为求一数列：a，b，r1，r2，rn1，rn，rn+1，0此数列的首项与第二项是a和b，从第三项开始的各项，分别是前两项相除所得的余数，如果余数为0，它的前项rn+1即是a和b的最大公约数，这种方法叫做欧几里得辗转相除法，其算法如下：S1输入a，b（ab）；S2求a/b的余数r；S3如果r0，则将ba，rb，再次求a/b的余数r，转至S2；S4输出最大公约数b.伪代码如下：10Read a，b20rmod（a，b）30Ifr=0thenGoto 8040Else50ab60br70Goto 2080Print b流程图如下：点评：算法的多样性：对于同一个问题，可以有不同的算法.例如求1+2+3+100的和，可以采用如下方法：先求1+2，再加3，再加4，一直加到100，最后得到结果5050.也可以采用这样的方法：1+2+3+100=（1+100）+（2+99）+（3+98）+（50+51）=50101=5050.显然，对于算法来说，后一种方法更简便，而循环累加更适用于计算机解题.因此，为了有效地进行解题，不仅要保证算法正确，还要选择好的算法，即方法简单、运算步骤少，能迅速得出正确结果的算法.例5：求1734，816，1343的最大公约数.分析：三个数的最大公约数分别是每个数的约数，因此也是任意两个数的最大公约数的约数，也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.解：用“辗转相除法”.先求1734和816的最大公约数，1734=8162+102；816=1028；所以1734与816的最大公约数为102.再求102与1343的最大公约数，1343=10213+17；102=176.所以1343与102的最大公约数为17，即1734，816，1343的最大公约数为17.例6：猴子吃桃问题：有一堆桃子不知数目，猴子第一天吃掉一半，觉得不过瘾，又多吃了一只，第二天照此办法，吃掉剩下桃子的一半另加一个，天天如此，到第十天早上，猴子发现只剩一只桃子了，问这堆桃子原来有多少个？解析：此题粗看起来有些无从着手的感觉，那么怎样开始呢？假设第一天开始时有a1只桃子，第二天有a2只第9天有a9只，第10天有a10只.在a1，a2，a10中，只有a10=1是知道的，现要求a1，而我们可以看出a1，a2，a10之间存在一个简单的关系：a9=2（a10+1），a8=2（a9+1），a1=2（a2+1）.也就是：ai=2（ai+1+1）i=9，8，7，6，1.这就是此题的数学模型.再考察上面从a9，a8直至a1的计算过程，这其实是一个递推过程，这种递推的方法在计算机解题中经常用到.另一方面，这九步运算从形式上完全一样，不同的只是ai的下标而已.由此，我们引入循环的处理方法，并统一用a0表示前一天的桃子数，a1表示后一天的桃子数，将算法改写如下：S1a11；第10天的桃子数，a1的初值S2i9；计数器初值为9S3a02（a1+1）；计算当天的桃子数S4a1a0；将当天的桃子数作为下一次计算的初值S5ii1；S6若i1，转S3；S7输出a0的值；伪代码如下：10a1120i930a02（a1+1）40a1a0.50ii160Ifi1 then Goto 3070Else80Print a0流程图如下：点评：这是一个从具体到抽象的过程，具体方法：（1）弄清如果由人来做，应该采取哪些步骤；（2）对这些步骤进行归纳整理，抽象出数学模型；（3）对其中的重复步骤，通过使用相同变量等方式求得形式的统一，然后简练地用循环解决.课堂练习课本P30 1，2.课时小结算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说，就是计算机解题的过程.1.本节通过对解决具体问题过程与步骤的分析（如求两个数的最大公约数），体会算法的思想，进一步了解算法的含义.2.本节通过阅读中国古代数学中的算法案例，如约分术，体会中国古代数学对世界数学发展的贡献.通过学生自己的亲身实践，亲自去解决几个算法设计的问题，才能体会到算法的基本思想.数学的其他内容与算法密切相关，如函数、数列等.我们在学习这些内容时要和算法联系起来.课后作业课本P31 1，3.变式练习1.数4557、1953、5115的最大公约数是（）A.31B.93C.217D.651答案：B2.下面的伪代码的算法目的是（）10Read x，y20mx30ny40If m/n=int（m/n） then Goto 9050cmint（m/n）n60mn70nc80Goto 4090a（xy）/n100 Print aA.求x，y的最小公倍数B.求x，y的最大公约数C.求x被y整除的商D.求y除以x的余数答案：B3.下面的伪代码的算法目的是.ReadX，YIf XY thenPrint XElsePrint YEnd if答案：输出x，y两个值中较大的一个值4.下面的伪代码的算法目的是.Reada，b，c，If ab thentaabbtElse if ac thentaacctElse if bc thentbbccbEnd ifPrint a，b，c答案：输入三个数，要求由小到大的顺序输出5.流程图填空：输入x的值，通过函数y=求出y的值.其算法流程图如下：答案：x1x0，则ax0；否则bx0；S3若|ab|c，计算终止，x0就是方程的根，否则转S1.写出用区间二分法求方程2x34x2+3x6=0在区间（10，10）之间的一个近似解（误差不超过0.001）的一个算法.答案：解：伪代码：10Read a，b，c20x0（a+b）/230f（a）2a34a2+3a640f（x0）2x34x2+3x650If f（x0）=0 then Goto 12060If f（a）f（x0）0 then70bx080Else90ax0100End if110If |ab|cthen Goto 20120Print x0流程图：11.求三个数390，455，546的最大公约数.答案：13.12.迭代法是用于求方程或方程组近似根的一种常用的算法设计方法.设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0；（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算.若方程有根，则按上述方法求得的x0就认为是方程的根.试用迭代法求某个数的平方根，用流程图和伪代码表示问题的算法.已知求平方根的迭代公式为x1=（x0+）.答案：解：设平方根的解为x，可假定一个初值x0=a/2（估计值），根据迭代公式得到一个新的值x1，这个新值比初值x0更接近要求的值x；再以新值作为初值，即x1x0，重新按原来的方法求x1，重复这一过程直到|x1x0|（某一给定的精度）.此时可将x0作为问题的解.伪代码：Readx0，Repeatx1（x0+a/x0）/2r|x1x0|x0x1UntilrPrintx0流程图：13.写出计算1+2!+3!+20!的算法的伪代码和流程图.答案：解析：这是一个循环结构，可以用循环语句实现.伪代码和流程图如下：T1S0For n from 1 to 20TTnSS+TEnd forPrint S14.未知数的个数多于方程个数的方程（组）叫做不定方程.最早提出不定方程的是我国的九章算术.实际生活中有很多不定方程的例子，例如“百鸡问题”：公元五世纪末，我国古代数学家张丘建在算经中提出了“百鸡问题”：“鸡母一，值钱三；鸡翁一，值钱二；鸡雏二，值钱一.百钱买百鸡，问鸡翁、母、雏各几何？”算法设计：（1）设母鸡、公鸡、小鸡数分别为I、J、K，则应满足如下条件：I+J+K=100；3I+2J+1/2K=100.（2）先分析一下三个变量的可能值.I的最小值可能为零，若全部钱用来买母鸡，最多只能买33只，故I的值为033中的整数.J的最小值为零，最大值为50.K的最小值为零，最大值为100.（3）对I、J、K三个未知数来说，I取值范围最少.为提高程序的效率，先考虑对I的值进行一一列举.（4）在固定一个I的值的前提下，再对J值进行一一列举.（5）对于每个I，J，怎样去寻找满足百钱买百鸡条件的K.由于I，J值已设定，便可由下式得到：K=100IJ.（6）这时的I，J，K是一组可能解，它只满足“百鸡”条件，还未满足“百钱”条件.是否真实解，还要看它们是否满足3I+2J+1/2K=100，满足即为所求解.根据上述算法思想，画出流程图并用伪代码表示.答案：解：这是一个循环结构的嵌套，可以用循环语句实现.伪代码：For I from 0 to 32For J from 0 to 49K100IJIf 3I+2J+0.5K=100 thenPrint I，J，KEnd forEnd for流程图：