新课标高中数学课件A版必修三第一章-1.3算法案例.ppt

1、 案例案例1 辗转相除法与更相减损术辗转相除法与更相减损术 3 5 9 15 问题问题11：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数 的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？ 创设情景，揭示课题创设情景，揭示课题 18 30 2 3 1818和和3030的最大公约的最大公约 数是数是2 23=6.3=6. 先用两个数公有的先用两个数公有的质因数质因数 连续去除连续去除,一直除到所得一直除到所得 的商是互质数为止的商是互质数为止,然后然后 把所有的除数连乘起来把所有的除数连乘起来. 问题问题2:2:我们都是利用找公约数的方法来

2、求最大我们都是利用找公约数的方法来求最大 公约数，如果公约数比较大而且根据我们的观察公约数，如果公约数比较大而且根据我们的观察 又不能得到一些公约数，我们又应该怎样求它们又不能得到一些公约数，我们又应该怎样求它们 的最大公约数？比如求的最大公约数？比如求82518251与与61056105的最大公约数的最大公约数? ? 研探新知研探新知 1.1.辗转相除法辗转相除法: : 例例1 1 求两个正数求两个正数82518251和和61056105的最大公约数。的最大公约数。 分析：分析：82518251与与61056105两数都比较大，而且没两数都比较大，而且没 有明显的公约数，如能把它们都变小一点

3、，根有明显的公约数，如能把它们都变小一点，根 据已有的知识即可求出最大公约数据已有的知识即可求出最大公约数. . 解：解：82518251610561051 121462146 显然显然82518251与与61056105的最大公约数也必是的最大公约数也必是21462146 的约数，同样的约数，同样61056105与与21462146的公约数也必是的公约数也必是82518251 的约数，所以的约数，所以82518251与与61056105的最大公约数也是的最大公约数也是 61056105与与21462146的最大公约数。的最大公约数。 研探新知研探新知 1.1.辗转相除法辗转相除法: : 例例

4、1 1 求两个正数求两个正数82518251和和61056105的最大公约数。的最大公约数。 解：解：82518251610561051 12146;2146; 6105214621813; 214618131333; 18133335148; 333148237; 1483740. 则则3737为为82518251与与61056105的最大公约数。的最大公约数。 以上我们求最大公约数的方法就是辗转相以上我们求最大公约数的方法就是辗转相 除法。也叫欧几里德算法，它是由欧几里德在除法。也叫欧几里德算法，它是由欧几里德在 公元前公元前300300年左右首先提出的。年左右首先提出的。 利用辗转相除法

5、求最大公约数的步骤如下：利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数第一步：用较大的数m m除以较小的数除以较小的数n n得到得到 一个商一个商q q0 0和一个余数和一个余数r r0 0；(m=n(m=nq q0 0+r+r0 0) ) 第二步：若第二步：若r r0 00 0，则，则n n为为m m，n n的最大公约的最大公约 数；若数；若r r0 000，则用除数，则用除数n n除以余数除以余数r r0 0得到一个得到一个 商商q q1 1和一个余数和一个余数r r1 1；(n=r(n=r0 0q q1 1+r+r1 1) ) 第三步：若第三步：若r r1 10 0，则，则r

6、 r0 0为为m m，n n的最大公约的最大公约 数；若数；若r r1 100，则用除数，则用除数r r0 0除以余数除以余数r r1 1得到一个得到一个 商商q q2 2和一个余数和一个余数r r2 2；(r(r0 0=r=r1 1q q2 2+r+r2 2) ) 依次计算直至依次计算直至r rn n0 0，此时所得到的，此时所得到的r rn n- -1 1 即为所求的最大公约数。即为所求的最大公约数。 第一步第一步,给定两个正数给定两个正数m,n 第二步第二步,计算计算m除以除以n所得到余数所得到余数r 第三步第三步,m=n,n=r 第四步第四步,若若r=0,则则m,n的最大公约数等于的最

7、大公约数等于m; 否则返回第二步否则返回第二步 辗转相除法求最大辗转相除法求最大 公约数算法：公约数算法： 否否 4. 4. 辗转相除法的程序框图及程序辗转相除法的程序框图及程序: : 开始开始 输入两个正数输入两个正数m,n mn, 第二步第二步,若若m,n都是偶数都是偶数,则不断用则不断用2约简约简,使他使他 们不同时是偶数们不同时是偶数,约简后的两个数仍记为约简后的两个数仍记为 m,n 第三步第三步,d=m-n 第四步第四步,判断”判断”d0”是否成立是否成立,若是若是,则将则将n,d 中较大者记为中较大者记为m,较小的记为较小的记为n,返回第三步返回第三步; 否则否则,2k *d(k是

8、约简整数的是约简整数的2的个数的个数)为所为所 求的最大公约数求的最大公约数. 更相减损术算法更相减损术算法 开始开始 输输m,n(mn) K=0 M,n为偶数为偶数? K=k+1 M=m/2 N=n/2 D=m-n Dn? Dn? 是是 否否 M=n N=d D=m-n M=d 是是 输出输出2k d 结束结束 是是 否否 INPUT “m,n=“;m,n IF mn then m=d ELSE m=n n=d End if d=m-n Wend d=2k*d PRINT d End 3.3.辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较: : （1 1）都是求最大公约数的方法，计

9、算上）都是求最大公约数的方法，计算上 辗转相除法以除法为主，更相减损术以减法为辗转相除法以除法为主，更相减损术以减法为 主主; ;计算次数上辗转相除法计算次数相对较少，计算次数上辗转相除法计算次数相对较少， 特别当两个数字大小区别较大时计算次数的区特别当两个数字大小区别较大时计算次数的区 别较明显。别较明显。 （2 2）从结果体现形式来看，辗转相除法）从结果体现形式来看，辗转相除法 体现结果是以相除余数为体现结果是以相除余数为0 0则得到，而更相减损则得到，而更相减损 术则以减数与差相等而得到术则以减数与差相等而得到. . 作业作业: 课本课本P45页练习页练习T1; P48页页A组组T1.

10、案例案例2 秦九韶算法秦九韶算法 教学设计教学设计 问题问题1设计求多项式设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7 当当x=5时的值的算法时的值的算法,并写出程序并写出程序. x=5 f=2x5-5x4-4x3+3x2-6x+7 PRINT f END 程序程序 点评点评:上述算法一共做了上述算法一共做了15次乘法运算次乘法运算,5次次 加法运算加法运算.优点是简单优点是简单,易懂易懂;缺点是不通用缺点是不通用,不能不能 解决任意多项多求值问题解决任意多项多求值问题,而且计算效率不高而且计算效率不高. 这析计算上述多项式的值这析计算上述多项式的值,一共需要一共需要9次乘次

11、乘 法运算法运算,5次加法运算次加法运算. 问题问题2有没有更高效的算法有没有更高效的算法? 分析分析:计算计算x的幂时的幂时,可以利用前面的计算结可以利用前面的计算结 果果,以减少计算量以减少计算量, 即先计算即先计算x2,然后依次计算然后依次计算 222 ,(),()xx xxxxxxx 的值的值. 第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运乘法的运 算次数减少了算次数减少了,因而能提高运算效率因而能提高运算效率.而且对于而且对于 计算机来说计算机来说,做一次乘法所需的运算时间比做一做一次乘法所需的运算时间比做一 次加法要长得多次加法要长得多,因此第二种做法能更快地得到

12、因此第二种做法能更快地得到 结果结果. 问题问题3能否探索更好的算法能否探索更好的算法,来解决任意多来解决任意多 项式的求值问题项式的求值问题? f(x)=2x5-5x4-4x3+3x2-6x+7 =(2x4-5x3-4x2+3x-6)x+7 =(2x3-5x2-4x+3)x-6)x+7 =(2x2-5x-4)x+3)x-6)x+7 =(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以所以,当当x=5时

13、时,多项式的值是多项式的值是2677. 这种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法. 例例1:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值. 解法一解法一:首先将原多项式改写成如下形式首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以所以,当当x=5时时,多多 项式

14、的值是项式的值是2677. 然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即 2 -5 -4 3 -6 7 x=5 10 5 25 21 105 108 540 534 2670 2677 所以所以,当当x=5时时,多项式的值是多项式的值是2677. 原多项式原多项式 的系数的系数 多项式多项式 的值的值. 例例1:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值时的值. 解法二解法二:列表列表 2 2 -5 0 -4 3 -6 0 x=5 10 5 25 25 125 121 605 608 3040 30

15、34 所以所以,当当x=5时时,多项式的值是多项式的值是15170. 练一练练一练:用秦九韶算法求多项式用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当当x=5时的值时的值. 解解:原多项式先化为原多项式先化为: f(x)=2x6-5x5 +0x4-4x3+3x2-6x+0 列表列表 2 15170 15170 注意注意:n次多项式有次多项式有n+1项项,因此缺少哪一项因此缺少哪一项 应将其系数补应将其系数补0. f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0. 我们可以改写成如下形式我们可以改写成如下形式: f(x)=(anx+an-1)x+an-

16、2)x+a1)x+a0. 求多项式的值时求多项式的值时,首先计算最内层括号内一首先计算最内层括号内一 次多项式的值次多项式的值,即即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即 一般地一般地,对于一个对于一个n次多项式次多项式 v2=v1x+an-2 , v 3=v2x+an-3, , vn=vn-1x+a0. 这样这样,求求n次多项式次多项式f(x)的值就转化为求的值就转化为求n个个 一次多项式的值一次多项式的值.这种算法称为这种算法称为秦九韶算法秦九韶算法. 点评点评:秦九韶算法是求一元多项式的秦九韶算法是求一元多项式的 值的一种方

17、法值的一种方法. 它的特点是它的特点是:把求一个把求一个n次多项式的值次多项式的值 转化为求转化为求n个一次多项式的值个一次多项式的值,通过这种转通过这种转 化化,把运算的次数由至多把运算的次数由至多n(n+1)/2次乘法次乘法 运算和运算和n次加法运算次加法运算,减少为减少为n次乘法运算次乘法运算 和和n次加法运算次加法运算,大大提高了运算效率大大提高了运算效率. v1=anx+an-1, v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0. 观察上述秦九韶算法中的观察上述秦九韶算法中的n个一次式个一次式,可见可见 vk的计算要用到的计算要用到vk-1的值的值.

18、若令若令v0=an,得得 v0=an, vK=vK-1x+an-k(k=1,2,n 这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步 骤骤,因此可用循环结构来实现因此可用循环结构来实现. 问题问题画出程序框图画出程序框图,表示用秦九韶算法求表示用秦九韶算法求5次多次多 项式项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当当x=x0 (x0是任意实数是任意实数)时的值的过程时的值的过程,然后写出程序然后写出程序. 否否 程序框图程序框图 开始开始 输入输入a0,a1,a2,a3,a4,a5 输入输入x0 n5? n=1 v=a5 v=vx0+a5-n n=

19、n+1 输出输出v 结束结束 是是 INPUT a0,a1,a2,a3,a4,a5 INPUT x0 n=1 v=a5 WHILE n=5 v=vx0+a5-n n=n+1 WEND PRINT v END 程序程序 课本课本P45页练习页练习T2; P48页页A组组T2. 案例案例3 进位制进位制 一、三维目标一、三维目标 （a a）知识与技能）知识与技能 了解各种进位制与十进制之间转换的规律，会利了解各种进位制与十进制之间转换的规律，会利 用各种进位制与十进制之间的联系进行各种进位制之用各种进位制与十进制之间的联系进行各种进位制之 间的转换。间的转换。 （b b）过程与方法）过程与方法 学

20、习各种进位制转换成十进制的计算方法，研究学习各种进位制转换成十进制的计算方法，研究 十进制转换为各种进位制的除十进制转换为各种进位制的除k k去余法，并理解其中的去余法，并理解其中的 数学规律。数学规律。 （c c）情感态度与价值观）情感态度与价值观 领悟十进制，二进制的特点，了解计算机的电路领悟十进制，二进制的特点，了解计算机的电路 与二进制的联系，进一步认识到计算机与数学的联系与二进制的联系，进一步认识到计算机与数学的联系. . 二、教学重难点二、教学重难点 重点：各进位制表示数的方法及各进位制重点：各进位制表示数的方法及各进位制 之间的转换之间的转换 难点：除难点：除k k去余法的理解以

21、及各进位制之去余法的理解以及各进位制之 间转换的程序框图的设计间转换的程序框图的设计 三、学法三、学法 在学习各种进位制特点的同时探讨进位制在学习各种进位制特点的同时探讨进位制 表示数与十进制表示数的区别与联系，熟悉各表示数与十进制表示数的区别与联系，熟悉各 种进位制表示数的方法，从而理解十进制转换种进位制表示数的方法，从而理解十进制转换 为各种进位制的除为各种进位制的除k k去余法。去余法。 问题问题11我们常见的数字都是十进制的我们常见的数字都是十进制的, , 但是并不是生活中的每一种数字都是十进制的但是并不是生活中的每一种数字都是十进制的. . 比如时间和角度的单位用六十进位制比如时间和

22、角度的单位用六十进位制, ,电子计电子计 算机用的是二进制算机用的是二进制. .那么什么是进位制那么什么是进位制? ?不同的不同的 进位制之间又有什么联系呢进位制之间又有什么联系呢? ? 进位制是人们为了计数和运算的方便而进位制是人们为了计数和运算的方便而 约定的一种记数系统，约定满二进一约定的一种记数系统，约定满二进一, ,就是二就是二 进制进制; ;满十进一满十进一, ,就是十进制就是十进制; ;满十六进一满十六进一, ,就就 是十六进制是十六进制; ;等等等等. . “满几进一”满几进一”,就是几进制就是几进制,几进制的几进制的基数基数就是几就是几. 可使用数字符号的个数称为基数可使用数

23、字符号的个数称为基数. .基数基数 都是大于都是大于1 1的整数的整数. . 如二进制可使用的数字有如二进制可使用的数字有0和和1,基数是基数是2; 十进制可使用的数字有十进制可使用的数字有0,1,2,8,9等十个等十个 数字数字,基数是基数是10; 十六进制可使用的数字或符号有十六进制可使用的数字或符号有09等等10 个数字以及个数字以及AF等等6个字母个字母(规定字母规定字母AF对应对应 1015),十六进制的基数是十六进制的基数是16. 注意注意: :为了区分不同的进位制为了区分不同的进位制, ,常在数字常在数字 的右下脚标明基数的右下脚标明基数,. ,. 如如111001111001(

24、2) (2)表示二进制数 表示二进制数,34,34(5) (5)表示 表示5 5进制数进制数. . 十进制数一般不标注基数十进制数一般不标注基数. 问题问题2十进制数十进制数3721中的中的3表示表示3个千个千,7表示表示7 个百个百,2表示表示2个十个十,1表示表示1个一个一,从而它可以写成从而它可以写成 下面的形式下面的形式: 3721=3103+7102+2101+1100. 想一想二进制数想一想二进制数1011(2)可以类似的写成什可以类似的写成什 么形式么形式? 1011(2)=123+022+121+120. 同理同理: 3421(5)=353+452+251+150. C7A16

25、(16)=12164+7163+10162 +1 161+6160. 一般地一般地,若若k是一个大于是一个大于1的整数的整数,那么以那么以k为为 基数的基数的k进制数可以表示为一串数字连写在一起进制数可以表示为一串数字连写在一起 的形式的形式 anan-1a1a0(k) (0ank,0an-1,a1,a0k) 意思是意思是:(1):(1)第一个数字第一个数字a an n不能等于不能等于0;0; (2)(2)每一个数字每一个数字a an n,a,an n- -1 1, ,a,a1 1,a,a0 0都须小于都须小于k.k. k进制的数也可以表示成不同位上数字与进制的数也可以表示成不同位上数字与 基

26、数基数k的幂的乘积之和的形式的幂的乘积之和的形式,即即 anan-1a1a0(k)=ankn+an-1kn-1 +a1 k1+a0k0 . 注意这是一注意这是一 个个n+1位数位数. 问题问题3二进制只用二进制只用0和和1两个数字两个数字,这这 正好与电路的通和断两种状态相对应正好与电路的通和断两种状态相对应,因因 此此计算机内部都使用二进制计算机内部都使用二进制.计算机在进计算机在进 行数的运算时行数的运算时,先把接受到的数转化成二先把接受到的数转化成二 进制数进行运算进制数进行运算,再把运算结果转化为十再把运算结果转化为十 进制数输出进制数输出. 那么二进制数与十进制数之间是如那么二进制数

27、与十进制数之间是如 何转化的呢何转化的呢? 例例1:把二进制数把二进制数110011(2)化为十进制数化为十进制数. 分析分析:先把二进制数写成不同位上数字与先把二进制数写成不同位上数字与2 的幂的乘积之和的形式的幂的乘积之和的形式,再按照十进制数的运算再按照十进制数的运算 规则计算出结果规则计算出结果. 解解:110011(2) =125+124+023+022+121+120 =132+116+12+1=51. 问题问题4你会把三进制数你会把三进制数10221(3)化为十进制数吗化为十进制数吗? 解解:10221(3)=134+033+232+231+130 =81+18+6+1=106.

28、 k进制数转化为十进制数的方法进制数转化为十进制数的方法 先把先把k进制的数表示成不同位上数字进制的数表示成不同位上数字 与基数与基数k的幂的乘积之和的形式的幂的乘积之和的形式,即即 anan-1a1a0(k) =ankn+an-1kn-1+a1k1+a0k0 . 再按照十进制数的运算规则计算出结果再按照十进制数的运算规则计算出结果. 例例2:把把89化为二进制的数化为二进制的数. 分析分析:把把89化为二进制的数化为二进制的数,需想办法将需想办法将89 先写成如下形式先写成如下形式 89=an2n+an-12n-1+a121+a020 . 89=64+16+8+1=126+025+124 +

29、123+022+021+120 =1011001(2). 但如果数太大但如果数太大,我们是无法这样凑出来的我们是无法这样凑出来的,怎么办怎么办? 89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 2=12+0, 1=02+1, 89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1 =126+02

30、5+124 +123+022+021+120=1011001(2). 可以用可以用2连续去除连续去除89 或所得商或所得商(一直到商为一直到商为 0为止为止),然后取余数然后取余数 -除除2取余法取余法. 2=12+0, 1=02+1, 44 1 例例2:把把89化为二进制的数化为二进制的数. 我们可以用下面的除法算式表示除我们可以用下面的除法算式表示除2取余法取余法: 2 89 余数余数 2 22 0 2 11 0 2 5 1 2 2 1 2 1 0 2 0 1 把算式中各步所得的余数把算式中各步所得的余数 从下到上排列从下到上排列,得到得到 89=1011001(2). 这种方法也可以推广

31、为把这种方法也可以推广为把 十进制数化为十进制数化为k进制数的进制数的 算法算法,称为称为除除k取余法取余法. 例例3:把把89化为五进制的数化为五进制的数. 解解:以以5作为除数作为除数,相应的除法算式为相应的除法算式为: 17 4 5 89 余数余数 5 3 2 5 0 3 89=324(5). 问题问题5你会把三进制数你会把三进制数10221(3)化为二进制数吗化为二进制数吗? 解解:第一步第一步:先把三进制数化为十进制数先把三进制数化为十进制数: 10221(3)=134+033+232+231+130 =81+18+6+1=106. 第二步第二步:再把十进制数化为二进制数再把十进制数化为二进制数: 106=1101010(2). 10221(3)=106= 1101010(2). 小结小结 进位制的概念及表示方法进位制的概念及表示方法; ; 各种进位制之间的相互转化各种进位制之间的相互转化. . anan-1a1a0(k) =ankn+an-1kn-1+a1k1+a0k0 . 作业作业: 1.课本课本P45页页A组组T3.