《高中数学(新课标人教A版)必修三《1.3 算法案例》课件》由会员分享,可在线阅读,更多相关《高中数学(新课标人教A版)必修三《1.3 算法案例》课件(26页珍藏版)》请在金锄头文库上搜索。
1、课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练【课标要求要求】1理解理解辗转相除法与更相减相除法与更相减损术的含的含义,了解其,了解其执行行过程程2理解秦九韶算法的理解秦九韶算法的计算算过程,并了解它提高程,并了解它提高计算效率的算效率的实质3理解理解进位制的概念,能位制的概念,能进行不同行不同进位制位制间的的转化化4了解了解进位制的程序框位制的程序框图和程序和程序【核心核心扫描描】1三种算法的原理及三种算法的原理及应用用(重重难点点)2三种算法的框三种算法的框图表示及程序表示及程序(难点点)3不
2、同不同进位制之位制之间的相互的相互转化化(重点重点)4秦九韶算法中多秦九韶算法中多项式的改写式的改写(易易错点点)1.3算法案例算法案例课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练辗转相除法相除法(1)辗转相除法,又叫欧几里得算法,是一种求两个正整数相除法,又叫欧几里得算法,是一种求两个正整数的的_的古老而有效的算法的古老而有效的算法(2)辗转相除法的算法步相除法的算法步骤第一步,第一步,给定定_.第二步,第二步,计算算_.第三步,第三步, _.第四步,若第四步,若r0,则m、n的最大公的最大公约数等于数等于_;否;否则,返回返回_.自学导引自学导引1最大公最大公约
3、数数两个正整数两个正整数m,nm除以除以n所得的余数所得的余数rmn,nrm第二步第二步课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练更相减更相减损术第一步,任意第一步,任意给定两个正整数,判断它定两个正整数,判断它们是否都是是否都是_若若是,用是,用_;若不是,;若不是,执行行_ 第二步,以第二步,以_的数减去的数减去_的数,接着把所得的差与的数,接着把所得的差与_的数比的数比较,并以大数减小数,并以大数减小数,继续这个操作,直到所得个操作,直到所得的数的数_为止,止,则这个数个数(等数等数)或或这个数与个数与约简的数的乘的数的乘积就是所求的最大公就是所求的最大公约
4、数数 任意给定两个正整数,用辗转相除法和更相减损术是否任意给定两个正整数,用辗转相除法和更相减损术是否都可以求它们的最大公约数?都可以求它们的最大公约数?提示提示是更相减是更相减损术与与辗转相除法都能在有限步内相除法都能在有限步内结束,故束,故均可以用来求两个正整数的最大公均可以用来求两个正整数的最大公约数数2偶数偶数2约简第二步第二步较小小较小小相等相等较大大课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练秦九韶算法秦九韶算法把一个把一个n次多次多项式式f(x)anxnan1xn1a1xa0改写成如改写成如下形式:下形式:(anxan1)xan2)xa1)xa0,求多
5、求多项式的式的值时,首先,首先计算算_一次多一次多项式的式的值,即即v1_,然后由内向外逐,然后由内向外逐层计算一次多算一次多项式的式的值,即即v2_,v3_,vn_.这样,求,求n次多次多项式式f(x)的的值就就转化化为求求_的的值3最内最内层括号内括号内anxan1v1xan2v2xan3vn1xa0n个一次多个一次多项式式课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练进位制位制进位制是人位制是人们为了了_和和_而而约定的定的记数系数系统,“满k进一一”就是就是k进制,制,k进制的基数是制的基数是k.把十把十进制制转化化为k进制数制数时,通常用除,通常用除k取余法
6、取余法 不同进制间的数不能比较大小,对吗?不同进制间的数不能比较大小,对吗?提示提示不不对不同的不同的进位制是人位制是人们为了了计数和运算方便而数和运算方便而约定的定的记数系数系统,不同,不同进位制的数照位制的数照样可比可比较大小,不大小,不过一般要一般要转化到十化到十进制下比制下比较大小更方便一些大小更方便一些4计数数运算方便运算方便课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练1辗转相除法与更相减相除法与更相减损术的区的区别和和联系系名师点睛名师点睛名称名称辗转相除法相除法更相减更相减损术区区别以除法以除法为主主两两个个整整数数差差值较大大时运算次数运算次数较少少
7、相相除除余余数数为零零时得得结果果以减法以减法为主主两两个个整整数数的的差差值较大大时,运算次数运算次数较多多相相减减,两两数数相相等等得得结果果相相减减前前要要做做是是否否都都是是偶偶数的判断数的判断联系系都是求两个正整数的最大公都是求两个正整数的最大公约数的方法数的方法二者的二者的实质都是都是递推的推的过程程二者都要用循二者都要用循环结构来构来实现课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练秦九韶算法秦九韶算法(1)特点:通特点:通过一次式的反复一次式的反复计算,逐步得出高次多算,逐步得出高次多项式的式的值,对于一个于一个n次多次多项式,只需做式,只需做n次乘法
8、和次乘法和n次加法即可次加法即可(2)算法步算法步骤:设Pn(x)anxnan1xn1a1xa0,将其改写,将其改写为Pn(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0.第一步:第一步:计算最内算最内层anxan1的的值,将,将anxan1的的值赋给一个一个变量量v1(为方便将方便将an赋予予变量量v0);第二步:第二步:计算算(anxan1)xan2的的值,可以改写,可以改写为v1xan2,将,将v1xan2的的值赋给一个一个变量量v2;2.课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练
9、依次依次类推,即每一步的推,即每一步的计算之后都算之后都赋予一个新予一个新值vk,即从,即从最内最内层的括号到最外的括号到最外层括号的括号的值依次依次赋予予变量量v1,v2,vk,vn,第,第n步所步所求求值vnvn1xa0即即为所求多所求多项式的式的值(3)秦九韶算法有以下几个秦九韶算法有以下几个优点:点:大大减少了乘法的次数,使大大减少了乘法的次数,使计算量减小在算量减小在计算机上做算机上做一次乘法所需要的一次乘法所需要的时间是做加法、减法的几倍到十几倍,是做加法、减法的几倍到十几倍,减少做乘法的次数也就加快了减少做乘法的次数也就加快了计算的速度;算的速度;规律性律性强强,便于利用循,便于
10、利用循环语句来句来实现算法;算法;避免了避免了对自自变量量x单独做独做幂的的计算,每次都是算,每次都是计算一个算一个一次多一次多项式的式的值,从而可以提高,从而可以提高计算的精度算的精度课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练关于关于进位制位制应注意的注意的问题(1)十十进制的原理是制的原理是满十十进一一个十一一个十进制正整数制正整数N可以写可以写成成an10nan110n1a1101a0100的形式,其中的形式,其中an,an1,a1,a0都是都是0至至9中的数字,且中的数字,且an0.例如例如36531026105.(2)一般地,一般地,k进制数的原理是制数
11、的原理是满k进一,一,k进制数一般在右制数一般在右下角下角处标注注(k),以示区,以示区别例如例如270(8)表示表示270是一个是一个8进制数但十制数但十进制一般省略不写制一般省略不写(3)在在k进制中,有:制中,有:有有k个不同的数字符号,即个不同的数字符号,即0,1,2,3,(k1);“逢逢k进一一”,即每位数,即每位数计满k后向高位后向高位进一一一个一个k进位制的正整数就是各位数位制的正整数就是各位数码与与k的方的方幂的乘的乘积的和,的和,其中其中幂指数等于相指数等于相应数数码所在位数所在位数(从右往左数从右往左数)减减1.例如例如230 451(k)2k53k40k34k25k1.3
12、课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练题型一题型一求两个正整数的最大公约数求两个正整数的最大公约数 分分别用用辗转相除法和更相减相除法和更相减损术求求261和和319的最大公的最大公约数数思路探索思路探索 使用使用辗转相除法可依据相除法可依据mnqr,反复,反复执行直行直到余数到余数为0;更相减;更相减损术则是根据是根据mnr,反复,反复执行,直行,直到到nr为止止解解法一法一(辗转相除法相除法)3192611(余余58),261584(余余29),58292(余余0),所以所以319与与261的最大公的最大公约数数为29.【例例1】课前探究学习课前探究学习课
13、堂讲练互动课堂讲练互动活页规范训练活页规范训练法二法二(更相减更相减损术)31926158,26158203,20358145,1455887,875829,582929,29290,所以所以319与与261的最大公的最大公约数是数是29.课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练规律方法规律方法(1)利用利用辗转相除法求相除法求给定的两个数的最大公定的两个数的最大公约数,即利用数,即利用带余除法,用数余除法,用数对中中较大的数除以大的数除以较小的数,小的数,若余数不若余数不为零,零,则将余数和将余数和较小的数构成新的数小的数构成新的数对,再利,再利用用带余除法,
14、直到大数被小数除尽,余除法,直到大数被小数除尽,则这时的的较小数就是小数就是原来两个数的最大公原来两个数的最大公约数数(2)利用更相减利用更相减损术求两个正整数的最大公求两个正整数的最大公约数的一般步数的一般步骤是:首先判断两个正整数是否都是偶数若是,用是:首先判断两个正整数是否都是偶数若是,用2约简也可以不除以也可以不除以2,直接求最大公,直接求最大公约数,数,这样不影响最后不影响最后结果果课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 用用辗转相除法求相除法求80与与36的最大公的最大公约数,并用更相减数,并用更相减损术检验你的你的结果果解解803628,3684
15、4,8420,即即80与与36的最大公的最大公约数是数是4.验证:80240362184022018292091111929277255233212111224所以所以80与与36的最大公的最大公约数数为4.【变式变式1】课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 将七将七进制数制数235(7)转化化为八八进制制解解235(7)2723715124,利用除,利用除8取取余法余法(如如图所示所示),所以,所以124174(8)所以所以235(7)转化化为八八进制数制数为174(8)题型题型二二进位制之间的转化进位制之间的转化【例例2】规律方法规律方法对于非十进制数之
16、间的互化,通常是把这个数对于非十进制数之间的互化,通常是把这个数先转化为十进制数,然后再利用除先转化为十进制数,然后再利用除k取余法,把十进制数取余法,把十进制数转化为转化为k进制数而在使用除进制数而在使用除k取余法时要注意以下几点:取余法时要注意以下几点:(1)必须除到所得的商是必须除到所得的商是0为止;为止;(2)各步所得的余数必须从各步所得的余数必须从下到上排列;下到上排列;(3)切记在所求数的右下角标明基数切记在所求数的右下角标明基数课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 把下列各数把下列各数转换成十成十进制数制数(1)101 101(2);(2)2
17、102(3);(3)4 301(6)解解(1)101 101(2)12502412312202145.(2)2 102(3)233132265.(3)4 301(6)4633621973.【变式变式2】课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 用秦九韶算法求用秦九韶算法求f(x)3x58x43x35x212x6,当,当x2的的值题型题型三三秦九韶算法在多项式中的应用秦九韶算法在多项式中的应用【例例3】课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练规范解答规范解答 根据秦九韶算法,把多根据秦九韶算法,把多项式改写成如下形式:式改写成如下形
18、式:f(x)(3x8)x3)x5)x12)x6,按照从内到外的,按照从内到外的顺序,依次序,依次计算一次多算一次多项式当式当x2时的的值 (2分分)v03,v1v02832814, (4分分)v2v123142325, (6分分)v3v225252555, (8分分)v4v321255212122,v5v42612226238, (10分分)所以当所以当x2时,多,多项式的式的值为238. (12分分)课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练【题后反思题后反思】 (1)先将多先将多项式写成一次多式写成一次多项式的形式,然式的形式,然后运算后运算时从里到外,一步一
19、步地做乘法和加法即可从里到外,一步一步地做乘法和加法即可这样比直接将比直接将x2代入原式大大减少了代入原式大大减少了计算量若用算量若用计算机算机计算,算,则可提高运算效率可提高运算效率(2)注意:当多注意:当多项式中式中n次次项不存在不存在时,可将第,可将第n次次项看作看作0xn.课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 用秦九韶算法用秦九韶算法计算算f(x)6x54x4x32x29x,需,需要加法要加法(或减法或减法)与乘法运算的次数分与乘法运算的次数分别为 ()A5,4 B5,5 C4,4 D4,5解析解析n次多次多项式需式需进行行n次乘法;若各次乘法;若各
20、项均不均不为零,零,则需需进行行n次加法,缺一次加法,缺一项就减少一次加法运算就减少一次加法运算f(x)中无常数中无常数项,故加法次数要减少一次,故加法次数要减少一次,为514.故故选D.答案答案D【变式变式3】课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 已知已知f(x)x52x43x34x25x6,用秦九韶算法,用秦九韶算法求求这个多个多项式当式当x2时的的值时,做了几次乘法?几次加法,做了几次乘法?几次加法? 错解错解 根据秦九韶算法,把多根据秦九韶算法,把多项式改写成如下形式式改写成如下形式f(x)(x2)x3)x4)x5)x6.按照从内到外的按照从内到外的
21、顺序,依次序,依次计算一次多算一次多项式当式当x2时的的值:v1224;v22v1311;v32v2426;v42v3557;v52v46120.显然,在然,在v1中未做乘法,只做了中未做乘法,只做了1次加法;在次加法;在v2,v3,v4,v5中各做了中各做了1次加法,次加法,1次乘法因此,共做了次乘法因此,共做了4次乘法,次乘法,5次加法次加法误区警示误区警示对秦九韶算法中的运算次数理解错误对秦九韶算法中的运算次数理解错误【示示例例】课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练 在在v1中中虽然然“v1224”,而,而计算机算机还是做了是做了1次次乘法乘法“v12
22、124”因因为用秦九韶算法用秦九韶算法计算多算多项式式f(x)anxnan1xn1a1xa0当当xx0时的的值时,首先将多,首先将多项式改写成式改写成f(x)(anxan1)xa1)xa0,然后再,然后再计算算v1anxan1,v2v1xan2,v3v2xan3,vnvn1xa0.无无论an是不是是不是1,这次的乘法都是要次的乘法都是要进行的行的 正解正解 由上分析可知,共做了由上分析可知,共做了5次乘法,次乘法,5次加法次加法课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练单击此处进入单击此处进入 活页规范训练活页规范训练课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练同学们来学校和回家的路上要注意安全课前探究学习课前探究学习课堂讲练互动课堂讲练互动活页规范训练活页规范训练同学们来学校和回家的路上要注意安全