《辽宁庄河市高级中学人教b版高一数学必修三导学案13算法案例》由会员分享，可在线阅读，更多相关《辽宁庄河市高级中学人教b版高一数学必修三导学案13算法案例（11页珍藏版）》请在金锄头文库上搜索。
1、1. 3算法案例 【教学目的】：1理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。2基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。【教学重难点】：重点：理解辗转相除法与更相减损术求最大公约数的措施。难点:把辗转相除法与更相减损术的措施转换成程序框图与程序语言。 【教学过程】：情境导入：1教师一方面提出问题：在初中,我们已经学过求最大公约数的知识，你能求出18与30的公约数吗?2.接着教师进一步提出问题，我们都是运用找公约数的措施来求最大公约数,如果公约数比较大并且根据我们的观测又不能得到某些公约数,我们又应当如何求它们的最大公约数?例如求8251
2、与1的最大公约数？这就是我们这一堂课所要探讨的内容。新知探究:1.辗转相除法例1 求两个正数851和6105的最大公约数。(分析：251与60两数都比较大，并且没有明显的公约数，如能把它们都变小一点,根据已有的知识即可求出最大公约数)解：81601246显然51的最大公约数也必是2146的约数,同样6105与46的公约数也必是8251的约数，因此8251与65的最大公约数也是6105与216的最大公约数。1=2462+11321468131+3181=333514833=47148=374+则37为8251与61的最大公约数。以上我们求最大公约数的措施就是辗转相除法。也叫欧几里德算法，它是由欧
3、几里德在公元前3左右一方面提出的。运用辗转相除法求最大公约数的环节如下:第一步：用较大的数除以较小的数n得到一种商q0和一种余数;第二步：若r0=0,则n为m，n的最大公约数;若00，则用除数除以余数r0得到一种商q1和一种余数r1；第三步:若r1=0,则r1为,n的最大公约数；若r10，则用除数r0除以余数r1得到一种商q2和一种余数r2;依次计算直至rn0，此时所得到的rn-1即为所求的最大公约数。练习：运用辗转相除法求两数401与207的最大公约数（答案:53)2.更相减损术国内初期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的环节如下：可半者半之，不可半者，副
4、置分母子之数，以少减多，更相减损，求其等也,以等数约之。翻译出来为:第一步:任意给出两个正数;判断它们与否都是偶数。若是，用2约简；若不是,执行第二步。第二步:以较大的数减去较小的数，接着把较小的数与所得的差比较,并以大数减小数。继续这个操作，直到所得的数相等为止,则这个数（等数）就是所求的最大公约数。例2 用更相减损术求98与3的最大公约数.解:由于63不是偶数，把8和63以大数减小数,并辗转相减,即:863=65=35878-72121-7414=7因此，9与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。（答案:12）比较辗转相除法与更相减损术的区别：（)都是求
5、最大公约数的措施，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少,特别当两个数字大社区别较大时计算次数的区别较明显。（2)从成果体现形式来看,辗转相除法体现成果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到3. 秦九韶算法 秦九韶计算多项式的措施 令，则有， 其中这样,我们便可由依次求出; 显然，用秦九韶算法求次多项式的值时只需要做次乘法和n次加法运算 4进位制 进位制是一种记数方式,用有限的数字在不同的位置表达不同的数值可使用数字符号的个数称为基数，基数为,即可称n进位制，简称进制.目前最常用的是十进制，一般使用10个阿拉伯数字09进行记数
6、. 对于任何一种数,我们可以用不同的进位制来表达.例如:十进数5，可以用二进制表达为111,也可以用八进制表达为71、用十六进制表达为,它们所代表的数值都是同样的.表达多种进位制数一般在数字右下脚加注来表达,如1101()表达二进制数,34(5）表达5进制数.(1).k进制转换为十进制的措施： ， (2).十进制转化为进制数b的环节为： 第一步,将给定的十进制整数除以基数k,余数便是等值的k进制的最低位; 第二步,将上一步的商再除以基数，余数便是等值的进制数的次低位； 第三步,反复第二步,直到最后所得的商等于0为止，各次所得的余数,便是k进制各位的数，最后一次余数是最高位,即除k取余法. 要点
7、诠释:1、在进制中,具有个数字符号.如二进制有0,1两个数字. 2、在k进制中，由低位向高位是按“逢进一”的规则进行计数. 3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以互相转化.【反馈测评】：1求24、24、1这三个数的最大公约数。求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。2.用更相减损术求9与63的最大公约数解:由于63不是偶数，把98和3以大数减小数，并辗转相减98633635=28328287=211-=214-7因此，98和3的最大公约数等于7 .已知一种五次多项式为用秦九韶算
8、法求这个多项式当x=5的值。解:将多项式变形：按由里到外的顺序，依此计算一次多项式当x 5时的值:,，因此，当 =5时,多项式的值等于17.2将二进制数110011(2）化成十进制数解:根据进位制的定义可知 因此，1101（2）51。 【板书设计】：1.3算法案例一、辗转相除法例1二、更相减损术例2三、秦九韶算法四、进位制五、反馈测评：小结作业1.3算法案例 课前预习学案一、预习目的、理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。2、理解秦九韶算法的思想。二、预习内容什么是进位制?最常用的进位制是什么？除此之外尚有哪些常用的进位制？请举例阐明.三、提出疑惑思考:辗转
9、相除法中的核心环节是哪种逻辑构造？课内探究学案一、 学习目的1. 会用辗转相除法与更相减损术求最大公约数的措施。2.会运用秦九韶算法求多项式的值。3各进位制之间能灵活转化。二、学习重难点：重点：辗转相除法与更相减损术求最大公约数的措施和秦九韶算法求多项式的值。难点:把辗转相除法与更相减损术的措施转换成程序框图与程序语言。三、 学习过程辗转相除法思路:可以运用除法将大数化小，找两数的最大公约数.(适于两数较大时)(1）用较大的数除以较小的数得到一种商和一种余数；(2）若=0,则为m，n的最大公约数；若0,则用除数n除以余数得到一种 和一种余数；（3)若0,则为m,n的最大公约数；若0，则用除数除
10、以余数得到一种商和一种余数；依次计算直至=0，此时所得到的即为所求的最大公约数.例题1：求两个正数42和0的最大公约数以上我们求最大公约数的措施就是辗转相除法，也叫欧几里德算法.由上述环节可以看出，辗转相除法中的除法是一种反复执行的环节，且执行次数由余数 与否等于0来决定,因此可把它当作一循环体，写出辗转相除法完整的程序框图和程序语言.教学更相减损术:国内初期也有求最大公约数问题的算法，就是更相减损术 在九章算 术中有更相减损术求最大公约数的环节：可半者半之,不可半者,副置 分母子之数,以少减多，更相减损，求其等也，以等数约之 翻译为：(1） 任意给出两个正数;判断它们与否都是偶数. 若是，用
11、2约简;若不是，执 行第二步(） 以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小 数. 继续这个操作，直到所得的数相等为止，则这个数(等数）就是所求的最 大公约数.例题2. 用更相减损术求91和49的最大公约数.秦九韶算法:（1)设计求多项式当x=5时的值的算法,并写出程序。（2)有无更高效的算法？能否探求更好的算法,来解决任意多项式的求解问题?引导学生把多项式变形为：并提问:从内到外，如果把每一种括号都当作一种常数,那么变形后的式子中有哪些“一次式”?的系数依次是什么?用秦九韶算法求多项式的值,与多项式构成有直接关系吗?用秦九韶算法计算上述多项式的值,需要多少次乘法运算和
12、多少次加法运算?秦九韶算法合用于一般的多项式的求值问题吗？如何用程序框图表达秦九韶算法？观测秦九韶算法的数学模型，计算时要用到的值,若令,我们可以得到下面的递推公式：这是一种在秦九韶算法中反复执行的环节，可以用循环构造来实现。请画出程序框图。例题3.已知一种五次多项式为用秦九韶算法求这个多项式当x 5的值。进位制：我们理解十进制吗？所谓的十进制，它是如何构成的?其他进位制的数又是如何的呢?进位制是人们为了计数和运算以便而商定的记数系统。进位制是一种记数方式,用有限的数字在不同的位置表达不同的数值。可使用数字符号的个数称为基数，基数为,即可称n进位制，简称n进制。例题.将二进制数110011(2
13、)化成十进制数 精讲点拨： 1.求两个正数8和14;228和1995;520和125的最大公约数.2 求两个正数81和2146的最大公约数. 3.用秦九韶算法计算多项式在x=-4时的值时，V3的值为 :反思总结:比较辗转相除法与更相减损术的区别（)都是求 的措施，计算上辗转相除法以 法为主,更相减损术以 法为主，计算次数上 法计算次数相对较少,特别当两个数字 时计算次数的区别较明显()从成果体现形式来看，辗转相除法体现成果是以 则得到，而更相减损术 则以 而得到（3)通过对秦九韶算法的学习，你对算法自身有哪些进一步结识?()秦九韶算法在计算一种次多项式的值时，只要做_次乘法运算和_次加法运算。课后练习与提高1、用“辗转相除法”求得459和357的最大公约数是: A.3 B9 C.7 D512、将数转化为十进制数为:A54 B 774 C. 256 D. 2603、用秦九韶算法计算多项式当时的值时，需要做乘法和加法的次数分别是: A. 6
