高中数学人教版A版必修三配套课件13算法案例一

第一章算法初步§1.3算法案例（一）1.理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析；2.了解秦九韶算法及利用它提高计算效率的本质；3.对简单的案例能设计程序框图并写出算法程序.问题导学题型探究达标检测学习目标知识点一求两个数的最大公约数的算法答案问题导学新知探究点点落实思考注意到8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.一般地，求两个数的最大公约数有2种算法：1.辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的的古老而有效的算法.(2)辗转相除法的算法步骤第一步，给定.第二步，计算.第三步，.第四步，若r＝0，则m，n的最大公约数等于；否则，返回.答案最大公约数两个正整数m，n(mn)m除以n所得的余数rm＝n，n＝rm第二步2.更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是.若是，用约简；若不是，执行.第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.答案偶数2第二步较大较小较小相等答案知识点二求n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值的算法思考衡量一个算法是否优秀的重要参数是速度.把多项式f(x)＝x5＋x4＋x3＋x2＋x＋1变形为f(x)＝((((x＋1)x＋1)x＋1)x＋1)x＋1，然后求当x＝5时的值，为什么比常规逐项计算省时？答案从里往外计算，充分利用已有成果，可减少重复计算.秦九韶算法的一般步骤：把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算一次多项式的值，即v1＝，然后由内向外逐层计算一次多项式的值，即最内层括号内anx＋an－1v2＝，v3＝，…vn＝，这样，求n次多项式f(x)的值就转化为求的值.答案返回v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式类型一辗转相除法的现代实现解析答案反思与感悟例1试设计用辗转相除法可以求两个正整数m，n的最大公约数的程序框图和程序.题型探究重点难点个个击破跟踪训练1用辗转相除法求261和319的最大公约数.解析答案解辗转相除法：319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.类型二更相减损术解析答案反思与感悟例2试用程序框图和程序表述更相减损术.解程序框图：程序：INPUTm，nWHILEmnk＝m－nIFnkTHENm＝nn＝kELSEm＝kENDIFWENDPRINTmEND跟踪训练2用更相减损术求261和319的最大公约数.解319－261＝58,261－58＝203，203－58＝145,145－58＝87，87－58＝29,58－29＝29，29－29＝0，所以319与261的最大公约数是29.解析答案类型三秦九韶算法的基本思想解析答案反思与感悟例3已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值.跟踪训练3用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值.解f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，所以有v0＝7，v1＝7×3＋6＝27，v2＝27×3＋5＝86，v3＝86×3＋4＝262，v4＝262×3＋3＝789，v5＝789×3＋2＝2369，v6＝2369×3＋1＝7108，v7＝7108×3＝21324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324.解析答案返回1.下列说法中正确的个数为()①辗转相除法也叫欧几里得算法；②辗转相除法的基本步骤是用较大的数除以较小的数；③求最大公约数的方法，除辗转相除法之外，没有其他方法；④编写辗转相除法的程序时，要用到循环语句.A.1B.2C.3D.4C达标检测12345解析①、②、④正确，③错误.解析答案2.关于利用更相减损术求156和72的最大公约数，下列说法正确的是()A.都是偶数必须约简B.可以约简，也可以不约简C.第一步作差为156－72＝84，第二步作差为72－84＝－12D.以上皆不正确12345B答案3.用辗转相除法求210与98的最大公约数需作除法的次数为()A.1B.2C.3D.412345B答案4.用更相减损术求147和42的最大公约数是()A.6B.7C.21D.42C12345答案123455.用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4时的值时，需做加法和乘法的次数的和为()A.10B.9C.12D.8C解析f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7，∴加法6次，乘法6次，∴6＋6＝12次，故选C.解析答案规律与方法1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.返回3.用秦九韶算法求多项式f(x)当x＝x0的值的思路为(1)改写；(2)计算v0＝anvk＝vk－1x0＋an－kk＝1，2，…，n；(3)结论f(x0)＝vn.