高中数学 第一章 算法初步 1.3算法案例学案 新人教A版必修3

第1课时辗转相除法与更相减损术、秦九韶算法1．理解辗转相除法与更相减损术的含义，了解其执行过程．2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．1．辗转相除法与更相减损术(1)辗转相除法①辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．②辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．(2)更相减损术的算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．(3)辗转相除法和更相减损术的区别与联系(1)秦九韶算法简介①秦九韶算法要解决的问题是求多项式的值．②秦九韶算法的特点通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题．③秦九韶算法的原理将f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写为：f(x)＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0＝…先计算最内层括号内一次多项式的值，即v1＝a n x＋a n－1，再由内向外逐层计算一次多项式v k的值．(2)秦九韶算法的操作方法①算法步骤如下第一步，输入多项式次数n、最高次项的系数a n和x的值．第二步，将v的值初始化为a n，将i的值初始化为n－1.第三步，输入i次项的系数a i.第四步，v＝vx＋a i，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.②程序框图如图所示③程序如下INPUT “n＝”；nINPUT “an＝”；aINPUT “x＝”；xv＝ai＝n－1WHILE i＞＝0INPUT “ai＝”；av＝v*x＋ai＝i－1WENDPRINT vEND1．实际应用更相减损术时要做的第一步工作是什么？[提示] 先判断a，b是否为偶数，若是，都除以2再进行．2．判断正误．(正确的打“√”，错误的打“×”)(1)辗转相除法的基本步骤是用较大的数除以较小的数．( )(2)求最大公约数的方法除辗转相除法之外，没有其他方法．( )(3)编写辗转相除法的程序时，要用到循环语句．( )[提示] (1)√(2)×(3)√题型一辗转相除法和更相减损术的应用【典例1】用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．[思路导引] 将612作为大数，468作为小数，执行辗转相除法和更相减损术的步骤即可.[解] 用辗转相除法：612＝468×1＋144,468＝144×3＋36,144＝36×4，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117,153－117＝36,117－36＝81,81－36＝45,45－36＝9,36－9＝27,27－9＝18,18－9＝9，所以612和468的最大公约数为9×2×2＝36.求最大公约数的两种方法步骤(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．[针对训练1] 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．[解] 80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝40,36÷2＝18；40÷2＝20,18÷2＝9；20－9＝11,11－9＝2；9－2＝7,7－2＝5；5－2＝3,3－2＝1；2－1＝1,1×2×2＝4；所以80与36的最大公约数为4.题型二求三个正整数的最大公约数【典例2】求325,130,270三个数的最大公约数[思路导引] 求三个数的最大公约数，可先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数．[解] 解法一(辗转相除法)：因为325＝130×2＋65,130＝65×2，所以325和130的最大公约数为65.因为270＝65×4＋10,65＝10×6＋5,10＝5×2,所以65和270的最大公约数为5,故325,130,270三个数的最大公约数为5.解法二(更相减损术)：325－130＝195,195－130＝65,130－65＝65.所以325和130的最大公约数是65.270－65＝205,205－65＝140,140－65＝75,75－65＝10,65－10＝55,55－10＝45,45－10＝35,35－10＝25,25－10＝15,15－10＝5,10－5＝5.所以65和270的最大公约数为5，故325,130,270三个数的最大公约数为5.理解辗转相除法的实质，从计算结果上看，辗转相除法是以相除余数为零而得到结果的.[针对训练2] 求三个数175,100,75的最大公约数.[解] 先求175与100的最大公约数：175＝100×1＋75,100＝75×1＋25,75＝25×3,∴175与100的最大公约数是25.再求25与75的最大公约数：75－25＝50,50－25＝25,∴75和25的最大公约数是25.∴175,100,75的最大公约数是25.题型三秦九韶算法【典例3】已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值.[思路导引] 可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算．[解] 将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式，当x＝5时的值：v0＝4；v 1＝4×5＋2＝22； v 2＝22×5＋3.5＝113.5； v 3＝113.5×5－2.6＝564.9； v 4＝564.9×5＋1.7＝2826.2； v 5＝2826.2×5－0.8＝14130.2.所以当x ＝5时，多项式的值等于14130.2.(1)用秦九韶算法求多项式f (x )当x ＝x 0的值的思路为： ①改写．②计算⎩⎪⎨⎪⎧v 0＝a n ，v k ＝v k －1x 0＋a n －k (k ＝1，2，…，n ).③结论f (x 0)＝v n .(2)应用秦九韶算法计算多项式的值应注意的3个问题 ①要正确将多项式的形式进行改写． ②计算应由内向外依次计算．③当多项式函数中间出现空项时，要以系数为零的齐次项补充．[针对训练3] 用秦九韶算法计算多项式f (x )＝12＋35x －8x 2＋6x 4＋5x 5＋3x 6在x ＝－4时的值时，v 3的值为( )A ．－144B ．－136C ．－57D ．34[解析] 根据秦九韶算法多项式可化为f (x )＝(((((3x ＋5)x ＋6)x ＋0)x －8)x ＋35)x ＋12.由内向外计算v 0＝3；v 1＝3×(－4)＋5＝－7； v 2＝－7×(－4)＋6＝34； v 3＝34×(－4)＋0＝－136.[答案] B课堂归纳小结1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．1．辗转相除法可解决的问题是( )A．求两个正整数的最大公约数B．多项式求值C．求两个正整数的最小公倍数D．排序问题[解析] 辗转相除法可以求两个正整数的最大公约数.[答案] A2．用辗转相除法求72与120的最大公约数时，需要做除法次数为( )A．4 B．3C．5 D．6[解析] 120＝72×1＋48,72＝48×1＋24,48＝24×2.[答案] B3．用更相减损术求36与134的最大公约数，第一步应为________．[解析] ∵36与134都是偶数，∴第一步应先除以2，得到18与67.[答案] 先分别除以2，得到18与674．用秦九韶算法求f(x)＝2x3＋x－3当x＝3时的值v2＝________.[解析] f(x)＝((2x＋0)x＋1)x－3，v0＝2，v1＝2×3＋0＝6，v2＝6×3＋1＝19.[答案] 195．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．[解] 根据秦九韶算法，把多项式改写成如下形式：f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.而x＝2，所以有v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1397.所以当x＝2时，多项式的值为1397.算法案例在实际生活中的应用通过算法案例的学习，知道算法的核心是一般意义上的解决问题的策略的具体化．对于一个实际问题，我们在分析、思考后可将之转化为数学问题，从而获得解决它的基本思路.【典例】现有长度为2.4 m和5.6 m两种规格的钢筋若干，要焊接一批棱上无接点的正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？[思路导引] 要焊接正方体，就是将两种规格的钢筋截成长度相等的钢筋条．为了保证不浪费材料，应使得每种规格的钢筋截取后没有剩余，因此截取的长度应为2.4与5.6的公约数；为使得正方体的体积最大，因此截取的长度应为2.4与5.6的最大公约数.[解] 用更相减损术来求2.4与5.6的最大公约数：5．6－2.4＝3.2,3．2－2.4＝0.8,2．4－0.8＝1.6,1．6－0.8＝0.8,因此2.4与5.6的最大公约数为0.8.所以使得正方体的棱长为0.8 m时，正方体的体积最大且不浪费材料.[针对训练] 甲，乙，丙三种溶液的质量分别为147 g，343 g，133 g，现要将它们分别全部装入小瓶中，每个小瓶中装入溶液的质量相同，问每瓶最多装多少？[解] 由题意，每个小瓶中装入的溶液的质量应是三种溶液质量的最大公约数．先求147与343的最大公约数：343－147＝196,196－147＝49,147－49＝98,98－49＝49，所以147与343的最大公约数是49.再求49与133的最大公约数：133－49＝84,84－49＝35,49－35＝14,35－14＝21,21－14＝7,14－7＝7，所以147,343,133的最大公约数为7，即每瓶最多装7 g.课后作业(八)(时间45分钟)学业水平合格练(时间25分钟)1．秦九韶算法与直接计算相比较，下列说法错误的是( )A．秦九韶算法与直接计算相比，大大节省了做乘法的次数，使计算量减少，并且逻辑结构简单B．秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度C．秦九韶算法减少了做乘法的次数，在计算机上也就降低了计算的速度D．秦九韶算法避免了对自变量x单独做幂的计算，而且与系数一起逐次增长幂次，从而提高计算的精度[解析] 秦九韶算法减少了做乘法的次数，在计算机上也就加快了计算的速度，故选项C错误．[答案] C2．下列说法中正确的个数为( )①辗转相除法也叫欧几里得算法；②辗转相除法的基本步骤是用较大的数除以较小的数；③求最大公约数的方法，除辗转相除法之外，没有其他方法；④编写辗转相除法的程序时，要用到循环语句．A．1 B．2C．3 D．4[解析] ①、②、④正确，③错误．[答案] C3．利用秦九韶算法求f(x)＝1＋2x＋3x2＋…＋6x5当x＝2时的值时，下列说法正确的是( )A．先求1＋2×2B．先求6×2＋5，第二步求2×(6×2＋5)＋4C．f(2)＝1＋2×2＋3×22＋4×23＋5×24＋6×25直接运算求解D．以上都不对[解析] 利用秦九韶算法应先算a n x＋a n－1，再算(a n x＋a n－1)x＋a n－2，故选B.[答案] B4．中国古代有计算多项式值的秦九韶算法，下图是实现该算法的程序框图．执行该程序框图，若输入的x＝2，n＝2，依次输入的a为2,2,5，则输出的s＝( )A．7 B．12C．17 D．34[解析] 该题考查程序框图的运行及考生的识图能力．由程序框图知，第一次循环：x＝2，n＝2，a＝2，s＝0×2＋2＝2，k＝1；第二次循环：a＝2，s＝2×2＋2＝6，k＝2；第三次循环：a＝5，s＝6×2＋5＝17，k＝3.结束循环，输出s的值为17，故选C.[答案] C5．用更相减损术求117和182的最大公约数时，需做减法的次数是( )A．8 B．7C．6 D．5[解析] ∵182－117＝65,117－65＝52,65－52＝13,52－13＝39,39－13＝26,26－13＝13，∴13是117和182的最大公约数，需做减法的次数是6.[答案] C6．用秦九韶算法求n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0当x＝x0时的值，求f(x0)需要乘方、乘法、加法的次数分别为( )A.n(n＋1)2，n，n B．n,2n，nC．0,2n，n D．0，n，n[解析] 因为f(x)＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0，所以乘方、乘法、加法的次数分别为0，n，n.[答案] D7．用秦九韶算法求多项式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6当x＝－4的值时，其中v1的值为________．[解析] ∵f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6，∴v0＝a6＝3，v1＝v0x＋a5＝3×(－4)＋5＝－7.[答案] －78．378和90的最大公约数为________．[解析] 378＝90×4＋18,90＝18×5＋0，∴378与90的最大公约数是18.[答案] 189．求1356和2400的最小公倍数．[解] 2400＝1356×1＋1044，1356＝1044×1＋312，1044＝312×3＋108，312＝108×2＋96，108＝96×1＋12，96＝12×8.所以1356与2400的最大公约数为12.则1356与2400的最小公倍数为(1356×2400)÷12＝271200.10．用秦九韶算法求多项式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.应试能力等级练(时间20分钟)11．下列哪组的最大公约数与1855,1120的最大公约数不同( )A．1120,735 B．385,350C．385,735 D．1855,325[解析] ∵(1855,1120)→(735,1120)→(735,385)→(350,385)→(350,35)，∴1855与1120的最大公约数是35，由以上计算过程可知选D.[答案] D12．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1，当x＝0.4时的值时，需要做乘法和加法的次数分别是( )A．6,6 B．5,6C．5,5 D．6,5[解析] 根据秦九韶算法，把多项式改写为f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，∴需要做6次加法运算，6次乘法运算，故选A.[答案] A13．已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r≤b)成立的q 和r的值分别为________．[解析] 用333除以24，商即为q，余数就是r.333÷24的商为13，余数是21.∴q＝13，r＝21.[答案] 13,2114．用秦九韶算法求多项式f(x)＝1－5x－8x2＋10x3＋6x4＋12x5＋3x6当x＝－4时的值时，v0，v1，v2，v3，v4中最大值与最小值的差是________．[解析] 多项式变形为f(x)＝3x6＋12x5＋6x4＋10x3－8x2－5x＋1＝(((((3x＋12)x＋6)x＋10)x－8)x－5)x＋1，v0＝3，v1＝3×(－4)＋12＝0，v2＝0×(－4)＋6＝6，v3＝6×(－4)＋10＝－14，v4＝－14×(－4)－8＝48，所以v4最大，v3最小，所以v4－v3＝48＋14＝62.[答案] 6215．用辗转相除法和更相减损术两种方法求三个数72,120,168的最大公约数．[解] (辗转相除法)：先求120,168的最大公约数．因为168＝120×1＋48，120＝48×2＋24,48＝24×2，所以120,168的最大公约数是24.再求72,24的最大公约数．因为72＝24×3，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.(更相减损术)：先求120,168的最大公约数．168－120＝48,120－48＝72，72－48＝24,48－24＝24，所以120,168的最大公约数为24.再求72,24的最大公约数．72－24＝48,48－24＝24，所以72,24的最大公约数为24，即72,120,168的最大公约数为24.。

《算法案例》教案——辗转相除法与更相减损术教材：课标版高中《数学》必修第章第节设计思路与指导思想：与传统教学内容相比，《算法初步》为新增内容。

算法是数学及其应用的重要组成部分，是计算科学的重要基础。

现代社会，信息技术飞速发展，算法在科学技术、社会发展中发挥着越来越大的作用，算法思想成为现代人应具备的一种基本数学素养。

本节课是使学生在已经学习算法的初步知识基础上，探究典型的算法案例，理解其中所包含的算法思想，巩固算法三种表示方法。

通过让学生经历分析算法步骤、画出程序框图、编制程序的基本过程，给学生提供探索与交流的活动时间和思维空间，真正使学生经历问题的提出过程、感受知识的形成与发展过程、暴露问题解决的思维过程、体验成功的喜悦过程，培养学生发现问题、解决问题的能力、养成良好的学习习惯、掌握必备的数学知识，从而达到知识与技能、过程与方法、情感与态度三位一体的统一。

教学方法：通过典型实例，使学生经历算法设计的全过程，在解决具体问题的过程中学习一些基本逻辑结构，学会有条理地思考问题、表达算法，并能将解决问题的过程整理成程序框图。

学法指导：在理解最大公约数的基础上去发现辗转相除法与更相减损术中的数学规律，并能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损术的程序框图与算法程序。

教学目标（）知识与技能.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。

（）过程与方法.由具体到抽象、观察探究，理解辗转相除法，体会使用算法解决问题的基本过程，体会算法思想，发展有条理思考和表达的能力，培养逻辑思维能力。

.在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。

《1.3秦九韶算法与进位制（1）》◆教材分析在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序语句三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力。

秦九韶算法是我国古代数学中的著名算法，其中蕴含的算法思想深刻，也更能体现算法的重要性；与进位制有关的算法是计算机科学中普遍使用的算法，其中蕴含的算法思想深刻，也更能体现算法的重要性。

◆教学目标【知识与能力目标】了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数，提高计算效率的实质；了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换。

【过程与方法目标】学习秦九韶算法在多项式求值中的应用，并理解其中的数学规律；学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k取余法，并理解其中的数学规律。

【情感态度价值观目标】理解秦九韶算法，领悟十进制、二进制的特点，培养学生热爱生活勤于实践的品质。

【教学重点】 秦九韶算法的特点及其程序设计；各进位制表示数的方法及各进位制之间的转换。

【教学难点】对秦九韶算法的先进性及其程序设计的理解；对除k 取余法理解以及各进位制之间转换的程序框图的设计。

电子课件调整、相应的教具带好、熟悉学生名单、电子白板要调试好。

一、导入部分设计求多项式f (x )=2x 5−5x 4−4x 3+3x 2−6x +7当x =5时的值的算法程序。

设计意图:从生活实际切入，激发了学生的学习兴趣，又为新知作好铺垫。

二、研探新知，建构概念1.电子白板投影出实例。

x =5y =2*x ^5-5*x ^4-4*x ^3+3*x ^2-6*x +7PRINT yEND上述算法一共做了15次乘法运算，5次加法运算。

优点是简单,易懂；缺点是不通用，不能解决任意多项多求值问题，而且计算效率不高。

第一章算法初步1.1算法与程序框图第一课时算法的概念教学目标1.通过实例体会算法思想，了解算法的含义与主要特点；2.能按步骤用自然语言写出简单问题的算法过程；3.培养学生逻辑思维能力与表达能力.教学重点将问题的解决过程用自然语言表示为算法过程．教学难点用自然语言描述算法．教学过程一．序言算法不仅是数学及其应用的重要组成部分，也是计算机理论和技术的核心．在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工具．听音乐、看电影、玩游戏、打字、画卡通画、处理数据，计算机几乎渗透到了人们生活的所有领域．那么，计算机是怎样工作的呢？要想弄清楚这个问题，算法的学习是一个开始．同时，算法有利于发展有条理的思考与表达的能力，提高逻辑思维能力．在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等，完成这些工作都需要一系列程序化的步骤，这就是算法的思想．二、数学运用 1．算法描述举例例1．给出求1+2+3+4+5的一个算法． 解： 算法1 按照逐一相加的程序进行． 第一步：计算1+2，得到3；第二步：将第一步中的运算结果3与3相加，得到6； 第三步：将第二步中的运算结果6与4相加，得到10； 第四步：将第三步中的运算结果10与5相加，得到15．算法2 运用公式123n ++++=2)1(+n n 直接计算．第一步：取=5；第二步：计算()21+n n ；第三步：输出运算结果．说明：一个问题的算法可能不唯一 例2．给出求解方程组274511x y x y +=⎧⎨+=⎩的一个算法．分析：解线性方程组的常用方法是加减消元法和代入消元法，这两种方法没有本质的差别，为了适用于解一般的线性方程组，以便于在计算机上实现，我们用高斯消元法（即先将方程组化为一个三角形方程组，在通过回代过程求出方程组的解）解线性方程组．解：用消元法解这个方程组，步骤是：第一步：方程①不动，将方程②中的系数除以方程①中的系数，得到乘数422m ==；第二步：方程②减去乘以方程①，消去方程②中的项，得到2733x y y +=⎧⎨=-⎩； 第三步：将上面的方程组自下而上回代求解，得到1y =-，4x =．所以原方程组的解为41x y =⎧⎨=-⎩2、算法概念算法：在数学中，算法通常是指按照一定规则解决某一个或一类问题的明确和有限的步骤。