《高中数学 专题1.5 算法案例课件 新人教A版必修3》由会员分享，可在线阅读，更多相关《高中数学 专题1.5 算法案例课件 新人教A版必修3（31页珍藏版）》请在金锄头文库上搜索。
1、算法案例1.1.辗转相除法辗转相除法 所谓辗转相除法，就是对于给定的两个数，用较大所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数的数除以较小的数. .若余数不为零，则将余数和较小的数若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数尽，则这时较小的数就是原来两个数的最大公约数. .基础回顾基础回顾2 2、作用：辗转相除法是用于求两个正整数、作用：辗转相除法是用于求两个正整数_的一种的一种算法，这种算法是由欧几里得在公元前算法，这种算法是由欧几里得在公元前300
2、300年左右首先提出年左右首先提出的，因此又叫的，因此又叫_最大公约数最大公约数欧几里得算法欧几里得算法【小结】辗转相除法的步骤：【小结】辗转相除法的步骤：第一步，给定两个正整数第一步，给定两个正整数m,nm,n不妨令不妨令mn.mn.第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r r第三步，第三步，_，_第四步，若第四步，若r=0r=0，则，则m,nm,n的最大公约数等于的最大公约数等于_；否则，返回第二步否则，返回第二步m=nm=nn=rn=rm m1 1、算理：、算理： 所谓更相减损术，就是对于给定的两个数，用较大的所谓更相减损术，就是对于给定的两个数，用较大的数减去
3、较小的数，然后将差和较小的数构成新的一对数，数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤，直到差再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的数相等，此时相等的两数便为原来两个数的数和较小的数相等，此时相等的两数便为原来两个数的最大公约数最大公约数. .类型二类型二：更相减损术 2 2、作用：更相减损术是我国古代数学专著、作用：更相减损术是我国古代数学专著_中中 介绍的一种求两个正整数最大公约数的方法介绍的一种求两个正整数最大公约数的方法九章算术九章算术（1 1）算法步）算法步骤第一步第一步,输入两个正整数入两个正整数a,b(ab);第
4、二步第二步,若若a不等于不等于b ,则执行第三步；否行第三步；否则转到第五步；到第五步；第三步第三步,把把a-b的差的差赋予予r;第四步第四步,如果如果br, 那么把那么把b赋给a,把把r赋给b;否否则把把r赋给a，执行第二步；行第二步；第五步第五步,输出最大公出最大公约数数b.3 3、试根据更相减损术设计一个计算机程序，求两个正整数、试根据更相减损术设计一个计算机程序，求两个正整数的最大公约数。的最大公约数。类型三：类型三：秦九韶算法秦九韶算法1 1秦九韶算法：秦九韶算法： 秦九韶算法的是通过一次式的反复计算，逐步求出秦九韶算法的是通过一次式的反复计算，逐步求出n n次次多项式的值因此对于一
5、个多项式的值因此对于一个n n次多项式，利用秦九韶算法次多项式，利用秦九韶算法求多项式的值，只要做求多项式的值，只要做n n次乘法运算和次乘法运算和n n次加法运算即可次加法运算即可2 2、作用：用秦九韶算法求、作用：用秦九韶算法求n n次多项式次多项式f(x)=af(x)=an nx xn n+a+an n1 1x xn n1 1+ +a+a1 1x+ax+a0 0， 当当x=xx=x0 0时的值时的值. .3 3、基本原理：首先将多项式改写成如下形式：、基本原理：首先将多项式改写成如下形式： f(x)=af(x)=an nx xn n+a+an n1 1x xn n1 1+ +a+a1 1
6、x+ax+a0 0=(a=(an nx xn n1 1+a+an n1 1x xn n2 2+ +a+a1 1)x+a)x+a0 0 =(a=(an nx xn n2 2+a+an n1 1x xn n3 3+ +a+a2 2)x+a)x+a1 1)x+a)x+a0 0= = _，=(=(a(an nx+ax+an n1 1)x+a)x+an n2 2)x+)x+a+a1 1)x+a)x+a0 0求多项式的值时，首先计算最内层括号内的一次多项式的值，求多项式的值时，首先计算最内层括号内的一次多项式的值，即即v v1 1= _= _，然后由内向外逐层计算一次多项式的值，即，然后由内向外逐层计算一
7、次多项式的值，即v v2 2=v=v1 1x+ax+an n2 2，v v3 3=v=v2 2x+ax+an n3 3， v vn n= _.= _.这样，求这样，求n n次多项式次多项式f(x)f(x)的值就转化为求的值就转化为求_a an nx+ax+an n1 1v vn n1 1x+ax+a0 0n n个一次多项式的值个一次多项式的值【小【小结】秦九韶算】秦九韶算法的步法的步骤改写改写改写多改写多项式式f(x)=anxn+an-1xn-1+a1x+a0为f(x)=(anx+an-1)x+an-2)x+an-3)x+a1)x+a0计算算结论当当x=x0时，由内到外依次由内到外依次计算算当
8、当x=x0时，f(x)的的值为f(x0)=vn1. 1. 进位制的概念：进位制是人们为计数和运算方便而约定的计数系进位制的概念：进位制是人们为计数和运算方便而约定的计数系统，约定满二进一，就是统，约定满二进一，就是_进制；满十进一，就是进制；满十进一，就是_进制；进制；, ,也也就是说，就是说，“满几进一满几进一”就是就是_进制，几进制的基数就是进制，几进制的基数就是_._.二二十十几几几几类型四：类型四：二进制2 2、表示：一般地，若、表示：一般地，若k k是一个大于是一个大于1 1的整数，那么以的整数，那么以k k为基数的为基数的k k进进制数可以表示为一串数字连写在一起的形式：制数可以表
9、示为一串数字连写在一起的形式：a an na an-1n-1a a1 1a a0(k)0(k)(a(an n,a,an-n-1 1, ,a,a1 1,a,a0 0N,0N,0a an n_,0_a_,0_an-1n-1, ,a,a1 1,a,a0 0k)k)k k3.3.进位制之间的转化进位制之间的转化(1)k(1)k进制的数转化为十进制：若进制的数转化为十进制：若a an na an-1n-1a a1 1a a0(k)0(k)表示一个表示一个k k进进 制的数，则转化为十进制数为制的数，则转化为十进制数为: : a an na an-1n-1a a1 1a a0(k)0(k)=_.=_.(2
10、)(2)将十进制化为将十进制化为k k进制进制: :用除用除k k取余法，用取余法，用k k连续去除连续去除_，直到，直到_为止，然后将所得的余数为止，然后将所得的余数_，即为相应的，即为相应的k k进制数进制数. .a an nk kn n+a+an-1n-1k kn-1n-1+ +a+a1 1k k1 1+a+a0 0十进制数所得的商十进制数所得的商商为零商为零倒序写出倒序写出类型一、类型一、 求最大公约数求最大公约数问题探讨与解题研究问题探讨与解题研究例例1.1.分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求779779与与209209的最大公约数的最大公约数. .【分析】
11、【分析】(1)(1)辗转相除法的操作是相除法的操作是较大的数除以大的数除以较小的数，直小的数，直到余数到余数为零零(2)(2)更相减更相减损术的操作是以大数减小数，直到减数和差相等的操作是以大数减小数，直到减数和差相等【解析】方法一：【解析】方法一：辗转相除法相除法779=2093+152,209=1521+57,152=572+38,57=381+19,38=192.所以，所以，779与与209的最大公的最大公约数数为19.方法二：更相减方法二：更相减损术779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,95-57=38,57-
12、38=19,38-19=19.所以所以779和和209的最大公的最大公约数数为19. 【练习】【练习】(1)(1)用更相减损术求用更相减损术求7878与与3636的最大公约数；的最大公约数； (2) (2)用辗转相除法求用辗转相除法求7878与与3636的最大公约数的最大公约数【解析】【解析】(1)78(1)7836364242，424236366 6，36366 63030，30306 62424，24246 61818， 18 186 61212，12126 66 6(2)(2)由辗转相除法得，由辗转相除法得，787836362 26 6，36366 66 6，故故7878与与3636的最
13、大公约数是的最大公约数是6 6【小结】辗转相除法与更相减损术的比较【小结】辗转相除法与更相减损术的比较: : （1 1）都是求最大公约数的方法，计算上辗转相）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主除法以除法为主，更相减损术以减法为主; ;计算次数上计算次数上辗转相除法计算次数相对较少，特别当两个数字大小辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结）从结果体现形式来看，辗转相除法体现结果是以相除余数为果是以相除余数为0 0则得到，而更相减损术则以减数与
14、则得到，而更相减损术则以减数与差相等而得到差相等而得到. .例例2 2、已知、已知f(x)=5xf(x)=5x4 4+10x+10x3 3+10x+10x2 2+5x+1+5x+1，用秦九韶算法求，用秦九韶算法求x=2x=2时时f(x)f(x)的值的值类型二、类型二、 利用秦九韶算法求多项式的值利用秦九韶算法求多项式的值【分析】根据秦九韶算法的运算法【分析】根据秦九韶算法的运算法则，将函数，将函数f(x)f(x)化化为下面的形下面的形式：式：f(x)=(5x+10)x+10)x+5)x+1f(x)=(5x+10)x+10)x+5)x+1，然后从里向外逐步，然后从里向外逐步计算，共算，共进行行4
15、 4次乘法，次乘法，5 5次加法运算，就得到次加法运算，就得到x=x=2 2时f(x)f(x)的的值【解析】因【解析】因为f(x)=5xf(x)=5x4 4+10x+10x3 3+10x+10x2 2+5x+1+5x+1所以所以f(x)=(5x+10)x+10)x+5)x+1v v0 0=5=5，v v1 1=5(=5(2)+10=02)+10=0，v v2 2=0(=0(2)+10=102)+10=10，v v3 3=10(=10(2)+5=-152)+5=-15，v v4 4= =（-15-15）(2)+1=-292)+1=-29，所以，当所以，当x=x=2 2时，f(x)=f(x)=29
16、29 【小结】秦九韶算法是求一元多项式的值的一种方法【小结】秦九韶算法是求一元多项式的值的一种方法. .它的特点是它的特点是: :把求一个把求一个n n次多项式的值转化为求次多项式的值转化为求n n个一次个一次多项式的值多项式的值, ,通过这种转化通过这种转化, ,把运算的次数由至多把运算的次数由至多n(n+1)/2n(n+1)/2次乘次乘法运算和法运算和n n次加法运算次加法运算, ,减少为减少为n n次乘法运算和次乘法运算和n n次加法运算次加法运算, ,大大大提高了运算效率大提高了运算效率. .例例1.1.已知一个已知一个k k进制数进制数132132与十进制数与十进制数3030相等相等
17、, ,那么那么k k等于等于( )( ) (A)-7 (A)-7或或4 (B)-7 (C)4 (D)4 (B)-7 (C)4 (D)都不对都不对类型三、类型三、 利用秦九韶算法求多项式的值利用秦九韶算法求多项式的值【分析】【分析】1.1.根据根据k k进制数化十制数化十进制数的制数的规则列出列出k k的方程即可的方程即可. .【解析】【解析】选C.C.由由1k1k2 2+3k+3k1 1+2k+2k0 0=30,=30,得得k k2 2+3k-28=0+3k-28=0即即k=4k=4或或k=-7(k=-7(舍舍).).例例2.2.把十进制数把十进制数111111化为五进制数是化为五进制数是(
18、)( ) (A)421 (A)421(5)(5) (B)521 (B)521(5) (5) (C)423(C)423(5)(5) (D)332 (D)332(5)(5)【分析】用【分析】用5 5连续去除去除111111，直到商，直到商为0 0为止，然后将各步所得止，然后将各步所得的余数倒序写出，即的余数倒序写出，即为相相应的五的五进制数制数. .【解析】【解析】选A.B 课堂检测2.4902.490和和910910的最大公约数为的最大公约数为( () )A A2 2B B1010C C3030 D D7070【解析】【解析】D. 【解析】【解析】B. 3.3.利用秦九韶算法求当利用秦九韶算法求
19、当x=2x=2时，时， 的值时，下列说法正确的是的值时，下列说法正确的是( )( )A.A.先求先求B.B.先求先求 ， 第二步求第二步求C.C.直接运算求解直接运算求解D. D. 以上皆错以上皆错课堂小结1.1.比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除法以除法）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时，计算次数次数相对较少，特别当两个数字大小区别较大时，计算次数的区别较明显的区别较明显. .（2 2）从结果体现形式来看，辗转相除法体现结果是以相除）从结果体现形式来看，辗转相除法体现结果是以相除余数为余数为0 0而得到，而更相减损术则以减数与差相等而得到而得到，而更相减损术则以减数与差相等而得到. .2 2、十进制数转化为、十进制数转化为k k进制数的方法：（除进制数的方法：（除k k取余法）取余法） 用用k k连续去除该十进制数或所得的商，直到商为零为连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应止，然后把每次所得的余数倒着排成一个数，就是相应的的k k进制数进制数. .课本51页复习参考题题 B组第1题课后作业
