1.3 算法案例ppt课件

13算法案例,第一章算法初步,学习导航,1辗转相除法所谓辗转相除法，就是对于任意给定的两个正整数，用较大的数除以较小的数若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个数的最大公约数,想一想1.辗转相除法中的关键步骤可用哪种逻辑结构来实现？提示：辗转相除法中带余数除法是一个反复执行、直到余数等于0停止的步骤，可用循环结构来实现,2更相减损术更相减损术是我国古代数学专著九章算术中介绍的任意一种求两个正整数最大公约数的方法其基本过程是：对于给定的两个正整数,判断它们是否都是偶数若是,用2约简；若不是，则用_，接着把所得的_与_比较，并以大数减小数继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数,较大数减去较小的数,差,较小的数,相等,想一想2.实际应用更相减损术时要做的第一步工作是什么？提示：先判断a，b是否全为偶数，若是，则先都除以2再进行,3秦九韶算法(1)算法原理它是通过一次式的反复计算，逐步得出高次多项式的值的一种求多项式函数值的算法设f(x)anxnan1xn1a1xa0，将其改写为f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0,首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值这样，求n次多项式f(x)的值就转化为求n个一次多项式的值,想一想3.怎样设计秦九韶算法，程序框图及程序呢？提示：算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值第二步，将v的值初始化为an，将i的值初始化为n1.第三步，输入i次项的系数ai.第四步，vvxai，ii1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.,4进位制(1)进位制的概述进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制；等等也就是说，“_”就是几进制，几进制的基数(大于1的整数)就是几一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注基数(k)，以示区别例如，270(8)表示270是一个八进制数十进制数一般不标注基数,满几进一,(2)常见的进位制二进制：a：只使用0和1两个数字；b：满二进一，如1110.八进制：a：使用0,1,2,3,4,5,6,7八个不同的数字；b：满八进一，如7110.十六进制：a：使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10,11,12,13,14,15；b：满十六进一，如F12E10.,(3)不同进位制数之间的转化k进制数转化为十进制数把k进制数转化为十进制数，写成不同位上数字与基数幂的乘积之和即可(简称幂积求和)，即anan1a1a0(k)anknan1kn1a1ka0.例如，将二进制数11001(2)化为十进制数：11001(2)124123022021120168125.,【解】辗转相除法：803628,36844,8420.故80和36的最大公约数是4.用更相减损术检验：803644，44368，36828，28820，20812，1284，844，80和36的最大公约数是4.【名师点评】解决此类问题要弄清它们的理论依据，根据理论依据一步一步计算出80和36的最大公约数,跟踪训练1求108与45的最大公约数解：法一：由辗转相除法，得10845218，451829，1892，故108与45的最大公约数是9.,法二：由更相减损术，得1084563，634518，451827，27189，1899，故108与45的最大公约数是9.,题型二秦九韶算法及应用(2013福州高一检测)用秦九韶算法写出当x3时f(x)2x54x33x25x1的值,【解】f(x)(2x0)x4)x3)x5)x1，v02，v12306，v263414，v3143345，v44535130，v513031391，所以f(3)391.【名师点评】利用秦九韶算法计算多项式值的关键是能准确地将多项式改写,然后由内向外逐次计算.由于后项计算用到前项的结果,故应认真、细心，确保每项计算结果的准确性,跟踪训练2利用秦九韶算法求多项式f(x)3x612x58x43.5x37.2x25x13当x6时的值，写出详细步骤解：f(x)(3x12)x8)x3.5)x7.2)x5)x13.v03，v1v061230，v2v168188，v3v263.51124.5，v4v367.26754.2，v5v46540530.2，v6v5613243168.2.f(6)243168.2.,题型三进位制(1)把二进制数101101(2)化为十进制数(2)把十进制数458转化为四进制数,【解】(1)101101(2)1250241231220211203284145，所以二进制数101101(2)转化为十进制数为45.(2)45813022(4),【名师点评】(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式,再按照十进制的运算规则计算出结果(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余,互动探究3将本例(1)中的二进制数101101(2)转化为三进制数解：101101(2)12502412312202112045，451200(3),1求两个正数的最大公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快2两种非十进制的不同进制之间相互转化时，可以把十进制作为转化的中间桥梁,利用秦九韶算法求多项式f(x)x65x56x4x23x2，当x2时的值为()A320B160C320D300【常见错误】(1)考虑x2而认为多项式的值为负值(2)易忽略多项式中系数为0的项，致使多项式改写不正确,易错警示利用秦九韶算法求值的易错点,【解析】将多项式变式为f(x)(x5)x6)x0)x1)x3)x2，v01，v12(5)7，v27(2)620，v320(2)040，v440(2)181，v581(2)3159，v6159(2)2320.【答案】A【失误防范】(1)解题时注意多项式变形后有几次乘法和几次加法(2)要注意所给多项式的项数，特别是系数为0的项,跟踪训练4已知多项式f(x)3x58x43x35x212x6，则f(2)_.解析：根据秦九韶算法，把多项式改写成如下形式：f(