算法案例 (共张)

1、13算法案例算法案例第一章第一章 算法初步算法初步栏目栏目导引导引第一章第一章 算法初步算法初步学习导航学习导航栏目栏目导引导引第一章第一章 算法初步算法初步新知初探思维启动新知初探思维启动1辗转相除法辗转相除法所谓辗转相除法，就是对于任意给定的两个正整数，用较大所谓辗转相除法，就是对于任意给定的两个正整数，用较大的数除以较小的数若余数不为零，则将余数和较小的数构的数除以较小的数若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个数的最大公约数时的小数就是原来两个数的最大公约数栏目栏目导引

2、导引第一章第一章 算法初步算法初步想一想想一想1.辗转相除法中的关键步骤可用哪种逻辑结构来实现？辗转相除法中的关键步骤可用哪种逻辑结构来实现？提示：提示：辗转相除法中带余数除法是一个反复执行、直到余数辗转相除法中带余数除法是一个反复执行、直到余数等于等于0停止的步骤，可用循环结构来实现停止的步骤，可用循环结构来实现栏目栏目导引导引第一章第一章 算法初步算法初步2更相减损术更相减损术更相减损术是我国古代数学专著更相减损术是我国古代数学专著九章算术九章算术中介绍的任意中介绍的任意一种求两个正整数最大公约数的方法其基本过程是：对于一种求两个正整数最大公约数的方法其基本过程是：对于给定的两个正整数给定

3、的两个正整数,判断它们是否都是偶数若是判断它们是否都是偶数若是,用用2约简；约简；若不是，则用若不是，则用_ ，接着把所得的，接着把所得的_ 与与_ 比较，并以大数减小数继续这个操作，直到所比较，并以大数减小数继续这个操作，直到所得的数得的数_ 为止，则这个数为止，则这个数(等数等数)或这个数与约简的数的或这个数与约简的数的乘积就是所求的最大公约数乘积就是所求的最大公约数较大数减去较小的数较大数减去较小的数差差较小的数较小的数相等相等栏目栏目导引导引第一章第一章 算法初步算法初步想一想想一想2.实际应用更相减损术时要做的第一步工作是什么？实际应用更相减损术时要做的第一步工作是什么？提示：提示：

4、先判断先判断a，b是否全为偶数，若是，则先都除以是否全为偶数，若是，则先都除以2再再进行进行栏目栏目导引导引第一章第一章 算法初步算法初步3秦九韶算法秦九韶算法(1)算法原理算法原理它是通过一次式的反复计算，逐步得出高次多项式的值的一它是通过一次式的反复计算，逐步得出高次多项式的值的一种求多项式函数值的算法种求多项式函数值的算法设设f(x)anxnan1xn1a1xa0，将其改写为，将其改写为f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0栏目栏目导引导引第一章第一章 算法初步算法初步首先计算最内层括号内一次多项式的值，即首先计算最内层括号内一次多项式的

5、值，即v1anxan1，然后由内向外逐层计算一次多项式的值这样，求然后由内向外逐层计算一次多项式的值这样，求n次多项式次多项式f(x)的值就转化为求的值就转化为求n个一次多项式的值个一次多项式的值栏目栏目导引导引第一章第一章 算法初步算法初步想一想想一想3.怎样设计秦九韶算法，程序框图及程序呢？怎样设计秦九韶算法，程序框图及程序呢？提示：提示：算法步骤如下：算法步骤如下：第一步，输入多项式次数第一步，输入多项式次数n、最高次项的系数、最高次项的系数an和和x的值的值第二步，将第二步，将v的值初始化为的值初始化为an，将，将i的值初始化为的值初始化为n1.第三步，输入第三步，输入i次项的系数次项

6、的系数ai.第四步，第四步，vvxai，ii1.第五步，判断第五步，判断i是否大于或等于是否大于或等于0.若是，则返回第三步；否若是，则返回第三步；否则，输出多项式的值则，输出多项式的值v.栏目栏目导引导引第一章第一章 算法初步算法初步栏目栏目导引导引第一章第一章 算法初步算法初步4进位制进位制(1)进位制的概述进位制的概述进位制是人们为了计数和运算方便而约定的记数系统，约定进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制；等等也一，就是十二进制

7、；满六十进一，就是六十进制；等等也就是说，就是说，“_”就是几进制，几进制的基数就是几进制，几进制的基数(大于大于1的整数的整数)就是几就是几一般地，一般地，k进制数的原理是满进制数的原理是满k进一，进一，k进制数一般在右下角处进制数一般在右下角处标注基数标注基数(k)，以示区别例如，以示区别例如，270(8)表示表示270是一个八进制是一个八进制数十进制数一般不标注基数数十进制数一般不标注基数满几进一满几进一栏目栏目导引导引第一章第一章 算法初步算法初步(2)常见的进位制常见的进位制二进制：二进制：a：只使用：只使用0和和1两个数字；两个数字；b：满二进一，如：满二进一，如1110.八进制：

8、八进制：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进制数转化为十进制数，写成不同位上数字与基数幂

9、的进制数转化为十进制数，写成不同位上数字与基数幂的乘积之和即可乘积之和即可(简称幂积求和简称幂积求和)，即，即anan1a1a0(k)anknan1kn1a1ka0.例如，将二进制数例如，将二进制数11 001(2)化为化为十进制数：十进制数：11 001(2)124123022021120168125.栏目栏目导引导引第一章第一章 算法初步算法初步栏目栏目导引导引第一章第一章 算法初步算法初步典题例证技法归纳典题例证技法归纳例例1栏目栏目导引导引第一章第一章 算法初步算法初步【解解】辗转相除法：辗转相除法：803628,36844,8420.故故80和和36的最大公约数是的最大公约数是4.用

10、更相减损术检验：用更相减损术检验：803644，44368，36828，28820，20812，1284，844，80和和36的最大公约数是的最大公约数是4.【名师点评名师点评】解决此类问题要弄清它们的理论依据，根据解决此类问题要弄清它们的理论依据，根据理论依据一步一步计算出理论依据一步一步计算出80和和36的最大公约数的最大公约数栏目栏目导引导引第一章第一章 算法初步算法初步跟踪训练跟踪训练1求求108与与45的最大公约数的最大公约数解：法一：由辗转相除法，得解：法一：由辗转相除法，得10845218，451829，1892，故故108与与45的最大公约数是的最大公约数是9.栏目栏目导引导引

11、第一章第一章 算法初步算法初步法二：由更相减损术，得法二：由更相减损术，得1084563，634518，451827，27189，1899，故故108与与45的最大公约数是的最大公约数是9.栏目栏目导引导引第一章第一章 算法初步算法初步例例2题型二秦九韶算法及应用题型二秦九韶算法及应用 (2013福州高一检测福州高一检测)用秦九韶算法写出当用秦九韶算法写出当x3时时f(x)2x54x33x25x1的值的值栏目栏目导引导引第一章第一章 算法初步算法初步【解解】f(x)(2x0)x4)x3)x5)x1，v02，v12306，v263414，v3143345，v44535130，v513031391

12、，所以所以f(3)391.【名师点评名师点评】利用秦九韶算法计算多项式值的关键是能准利用秦九韶算法计算多项式值的关键是能准确地将多项式改写确地将多项式改写,然后由内向外逐次计算然后由内向外逐次计算.由于后项计算用到由于后项计算用到前项的结果前项的结果,故应认真、细心，确保每项计算结果的准确性故应认真、细心，确保每项计算结果的准确性栏目栏目导引导引第一章第一章 算法初步算法初步跟踪训练跟踪训练2利用秦九韶算法求多项式利用秦九韶算法求多项式f(x)3x612x58x43.5x37.2x25x13当当x6时的值，写出详细步骤时的值，写出详细步骤解：解：f(x)(3x12)x8)x3.5)x7.2)x

13、5)x13.v03，v1v061230，v2v168188，v3v263.51 124.5，v4v367.26 754.2，v5v46540 530.2，v6v5613243 168.2.f(6)243 168.2.栏目栏目导引导引第一章第一章 算法初步算法初步题型三进位制题型三进位制 (1)把二进制数把二进制数101 101(2)化为十进制数化为十进制数(2)把十进制数把十进制数458转化为四进制数转化为四进制数例例3栏目栏目导引导引第一章第一章 算法初步算法初步【解解】(1)101 101(2)1250241231220211203284145，所以二进制数所以二进制数101 101(2)

14、转化为十进制数为转化为十进制数为45.(2) 45813 022(4)栏目栏目导引导引第一章第一章 算法初步算法初步【名师点评名师点评】(1)将将k进制转化为十进制的方法是：先将进制转化为十进制的方法是：先将这个这个k进制数写成各个数位上的数字与进制数写成各个数位上的数字与k的幂的乘积之和的的幂的乘积之和的形式形式,再按照十进制的运算规则计算出结果再按照十进制的运算规则计算出结果(2)十进制转化十进制转化为为k进制，采用除进制，采用除k取余法，也就是除基数，倒取余取余法，也就是除基数，倒取余栏目栏目导引导引第一章第一章 算法初步算法初步互动探究互动探究3将本例将本例(1)中的二进制数中的二进制

15、数101 101(2)转化为三进制数转化为三进制数解：解：101 101(2)12502412312202112045，451 200(3)栏目栏目导引导引第一章第一章 算法初步算法初步1求两个正数的最大公约数，当两数差别较大时，用辗转求两个正数的最大公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快相除法，当两数差别不大时，用更相减损术较快2两种非十进制的不同进制之间相互转化时，可以把十进两种非十进制的不同进制之间相互转化时，可以把十进制作为转化的中间桥梁制作为转化的中间桥梁栏目栏目导引导引第一章第一章 算法初步算法初步 利用秦九韶算法求多项式利用秦九韶算法求多项式f

16、(x)x65x56x4x23x2，当，当x2时的值为时的值为()A320B160C320 D300【常见错误】【常见错误】(1)考虑考虑x2而认为多项式的值为负值而认为多项式的值为负值(2)易忽略多项式中系数为易忽略多项式中系数为0的项，致使多项式改写不正确的项，致使多项式改写不正确精彩推荐典例展示精彩推荐典例展示易错警示易错警示 利用秦九韶算法求值的易错点利用秦九韶算法求值的易错点例例4栏目栏目导引导引第一章第一章 算法初步算法初步【解析解析】将多项式变式为将多项式变式为f(x)(x5)x6)x0)x1)x3)x2，v01，v12(5)7，v27(2)620，v320(2)040，v440(

17、2)181，v581(2)3159，v6159(2)2320.【答案答案】A【失误防范失误防范】(1)解题时注意多项式变形后有几次乘法和几解题时注意多项式变形后有几次乘法和几次加法次加法(2)要注意所给多项式的项数，特别是系数为要注意所给多项式的项数，特别是系数为0的项的项栏目栏目导引导引第一章第一章 算法初步算法初步跟踪训练跟踪训练4已知多项式已知多项式f(x)3x58x43x35x212x6，则，则f(2)_.解析：根据秦九韶算法，把多项式改写成如下形式：解析：根据秦九韶算法，把多项式改写成如下形式：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式当按照从内