067辗转相除法更相减损术和秦九韶算法

高一数学学案序号___067__高一年级_1、6___班教师张杰学生_____课题1.3算法案例————辗转相除法、更相减损术与秦九韶算法一、学习目的1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。2．了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。3.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。二、学习重点、难点重点：理解辗转相除法与更相减损术求最大公约数的方法。理解秦九韶算法的思想。难点：把辗转相除法与更相减损术、秦九韶算法的方法转换成程序框图与程序语言。三、学习过程复习回顾直到型循环与当型循环的程序语言分别是什么？知识探究（一）:辗转相除法思考1:18与30的最大公约数是多少？你是怎样得到的？思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？例1：用辗转相除法求225和135的最大公约数练习：利用辗转相除法求两数4081与20723的最大公约数.思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，第三步，第四步，第五步，思考5:该算法的程序框图如何表示？思考6:该程序框图对应的程序如何表述？思考7：如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？知识探究（二）:更相减损术思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？练习：用更相减损术求两个正数84与72的最大公约数思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(mn).第二步，第三步，第四步，第五步，思考3:该算法的程序框图如何表示？思考4:该程序框图对应的程序如何表述？知识探究（三）:辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以为主，更相减损术以为主，计算次数上辗转相除法计算次数相对，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是则得到，而更相减损术则以相等而得到例2分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：更相减损术:例3求325，130，270三个数的最大公约数.知识探究(四):秦九韶算法的基本思想思考1:对于多项式1)(2345xxxxxxf，求)5(f的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？思考2:在上述问题中，若先计算2x的值，然后依次计算xx2，xxx)(2，xxxx))((2的值，这样每次都可以利用上一次计算的结果，那么一共做了多少次乘法运算和多少次加法运算？小结：第二种做法和第一种做法相比，乘法的运算次数减少了，因而能提高运算效率。而且对于计算机来说，做一次乘法运算所需的时间比做一次加法运算需要的时间要长得多，因此第二种算法能更快的得到结果。思考3:对于多项式763452)(2345xxxxxxf表示为01210111))))(axaxaxaxaaxaxaxaxfnnnnnnn（（的形式，则由内向外逐层计算一次多项式的值，其算法步骤如何？一共做多少次乘法运算和多少次加法运算？思考4:上述求多项式0111)(axaxaxaxfnnnn的值的方法称为秦九韶算法，利用该算法求)(0xf的值，一共需要多少次乘法运算，多少次加法运算？思考5:在秦九韶算法中，记nav0那么第k步的算式是什么？高一数学学案序号___067__高一年级_1、6___班教师张杰学生_____课题1.3算法案例————辗转相除法、更相减损术与秦九韶算法知识探究(五):秦九韶算法的程序设计思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，第二步，第三步，第四步，第五步，思考2:该算法的程序框图如何表示？思考3:该程序框图对应的程序如何表述？例4已知一个5次多项式为102345)(2345xxxxxxf用秦九韶算法求)5(f的值.练习：阅读下列程序，说明它解决的实际问题是什么？INPUT“x=”；an=0y=0WHLEn5y=y+(n+1)*a∧nn=n+1WENDPRINTyEND四、小结小结：1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.3、资料：秦九韶的生平秦九韶(1202～1261年)，字道古，南宋普州安岳(今四川省安岳县)人。秦九韶的突出数学成就表现为四个方面：（1）“大衍求一术”。即为一次同余式组解法。西方解决同类问题的理论是高斯于1801年建立的，比秦九韶晚了554年。他还把这种理论用于解决商功、利息、粟米、建筑等问题。(2)线性方程组解法。他在《数书九章》中解决了许多相当于线性方程组的问题，其中数字相当大，计算也很复杂。他在“均货推本”题草中，井然有序地写出厂解题过程，这种解法与高斯消元法本质相当，但比高斯早约600年。(3)高次方程数值解法。他集秦汉以来“开方术”之大成，运用贾宪的“增乘开方法”，解决于数字高次方程有理数根和无理数根的近似值计算问题。他所设计的演算程序被称为“秦九韶方法”。西方同类问题的探究始于19世纪，他比意大利的鲁菲尼、英国的霍纳要早五、六百年。(4)“三斜求积”。他在《数书九章》中，依据分别为12、14、15的三边求出了相应的三角形面积，其方法具有一般性。这与西方的海伦公式是等价的。五、课后巩固1、在对16和12求最大公约数时，整个操作如下：（16，12）→（4，12）→（4，8）→（4，4），由此可以看出12和16的最大公约数是（）A.4B.12C.16D.82、下列各组关于最大公约数的说法中不正确的是（）A.16和12的最大公约数是4B.78和36的最大公约数是6C.85和357的最大公约数是34D.105和315的最大公约数是1053、算法Ｓ１输入，ｘ，ｙＳ２ｍ＝ｍａｘ{ｘ，ｙ}Ｓ３ｎ＝ｍｉｎ{ｘ，ｙ}Ｓ４若ｍ／ｎ＝[ｍ／ｎ]（[ｘ]表示ｘ的整数部分）则输出ｎ，否则执行Ｓ５Ｓ５ｒ＝ｍ－[ｍ／ｎ]＊ｎＳ６ｍ＝ｎＳ７ｎ＝ｒＳ８执行Ｓ４Ｓ９输出ｎ上述算法的含义是。4、用辗转相除法求840与1785的最大公约数.5、用更相减损术求612与468的最大公约数6、利用秦九韶算法求多项式1153723xxx在23x的值时，在运算中下列哪个值用不到（）A.164B.3767C.86652D.851697、利用秦九韶算法计算多项式)(xf1876543x23456xxxxx＝当x=4的值的时候，需要做乘法和加法的次数分别为（）A.6，6B.5，6C.5，5D.6，58、利用秦九韶算法求多项式1352.75.3812323456xxxxxx在6x的值，写出详细步骤。9、下图的框图是一古代数学家的一个算法的程序框图，它输出的结果s表示（）A.3210aaaa的值B.300201032xaxaxaa的值C.303202010xaxaxaa的值D.以上都不对10、已知n次多项式1011()nnnnnPxaxaxaxa如果在一种算法中，计算0kx（k＝2，3，4，…，n）的值需要k－1次乘法，（1）计算30()Px的值需要9次运算（6次乘法，3次加法），那么计算0()nPx的值需要多少次运算？（2）若采取秦九韶算法：0011(),()()kkkPxaPxxPxa（k＝0，1，2，…，n－1），计算30()Px的值只需6次运算，那么计算0()nPx的值共需要多少次运算？（3）若采取秦九韶算法，设ai=i+1，i=0，1，…，n，求P5（2）（写出采取秦九韶算法的计算过程）预习指导：预习课本40-45页，什么是进位制？3k1aS?0k1kk0xsask输入03210,,,,xaaaa输出S结束开始