高中数学第1章算法初步1.3算法案例课件新人教版.pptx

第一章 算法初步,1.3 算法案例,学习目标,1.理解辗转相除法与更相减损术的含义，了解其执行过程. 2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质. 3.理解进位制的概念，能进行不同进位制间的转化. 4.了解进位制的程序框图和程序.,知识梳理 自主学习,题型探究 重点突破,当堂检测 自查自纠,栏目索引,知识梳理 自主学习,知识点一 辗转相除法与更相减损术,1.辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法. (2)辗转相除法的算法步骤 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r0，则m，n的最大公约数等于 ；否则，返回 .,最大公约数,两个正整数m，n,m除以n所得的余数r,mn，nr,m,第二步,答案,2.更相减损术 第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数.继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,偶数,2,第二步,较大,较小,较小,相等,答案,3.辗转相除法和更相减损术的区别与联系：,思考 实际应用更相减损术时要做的第一步工作是什么？,答 先判断a，b是否为偶数，若是，都除以2再进行.,答案,知识点二 秦九韶算法,1.秦九韶算法简介 (1)秦九韶算法要解决的问题是求多项式的值. (2)秦九韶算法的特点： 通过一次式的反复计算，逐步得到高次多项式的值，即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题.,(3)秦九韶算法的原理： 将f(x)anxnan1xn1a1xa0改写为： f(x)(anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 ,先计算最内层括号内一次多项式的值，即v1anxan1，再由内向外逐层计算一次多项式vk的值.,2.秦九韶算法的操作方法 (1)算法步骤如下： 第一步，输入多项式次数n、最高次项的系数an和x的值. 第二步，将v的值初始化为an，将i的值初始化为n1. 第三步，输入i次项的系数ai. 第四步，vvxai，ii1. 第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.,(2)程序框图如图所示.,(3)程序如下：,知识点三 进位制,1.进位制的概念 进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数(大于1的整数)就是几. 2.常见的进位制 (1)二进制： 只使用0和1两个数学； 满二进一，即1110(2). (2)八进制； 使用0,1,2,3,4,5,6,7这八个不同数学； 满八进一，即7110(8).,思考 任何进位制中都要用到的数字是什么？,答 0和1.,返回,答案,题型探究 重点突破,题型一 求两个正整数的最大公约数,例1 分别用辗转相除法和更相减损术求261和319的最大公约数.,解 方法一 (辗转相除法) 3192611(余58)， 261584(余29)， 58292(余0)， 所以319与261的最大公约数为29.,方法二 (更相减损术) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319与261的最大公约数是29.,解析答案,反思与感悟,反思与感悟,(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. (2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数.若是，用2约简.也可以不除以2，直接求最大公约数，这样不影响最后结果.,跟踪训练1 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果.,解 803628，36844,8420， 即80与36的最大公约数是4. 验证： 80240,36218；40220,1829； 20911,1192；927,725； 523,321；211,1224； 所以80与36的最大公约数为4.,解析答案,题型二 秦九韶算法的应用,例2 用秦九韶算法求多项式f(x)x55x410x310x25x1当x2时的值.,解 f(x)x55x410x310x25x1(x5)x10)x10)x5)x1. 当x2时，有v01； v1v0xa41(2)53； v2v1xa33(2)104； v3v2xa24(2)102； v4v3xa12(2)51； v5v4xa01(2)11. 故f(2)1.,解析答案,反思与感悟,反思与感悟,(1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可.这样比直接将x2代入原式大大减少了计算量.若用计算机计算，则可提高运算效率. (2)注意：当多项式中n次项不存在时，可将第n次项看作0xn.,跟踪训练2 用秦九韶算法计算多项式f(x)x612x560x4160x3240x2192x64当x2时的值.,解 根据秦九韶算法，把多项式改写成如下形式： f(x)(x12)x60)x160)x240)x192)x64. 由内向外依次计算一次多项式当x2时的值； v01； v1121210； v21026040； v340216080； v480224080； v580219232； v6322640. 所以当x2时，多项式的值为0.,解析答案,题型三 进位制之间的互化,例3 (1)把二进制数1110011(2)化为十进制数.,解 1110011(2)1261251240230221211115.,(2)将8进制数314706(8)化为十进制数.,解 314706(8)385184483782081680104902. 所以，化为十进制数是104902.,解析答案,反思与感悟,反思与感悟,(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果. (2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余.,跟踪训练3 将53(8)转化为二进制数.,解 先将八进制数53(8)转化为十进制数： 53(8)58138043； 再将十进制数43转化为二进制数：,所以53(8)101011(2).,解析答案,转化与化归思想,思想方法,例4 下列各数中，最小的数是( ) A.85(9) B.210(6) C.1000(4) D.111111(2),分析 先将它们转化为十进制数，再进行比较.,解析 85(9)89577, 210(6)26216078, 1000(4)14364, 111111(2)12512412312212163. 故最小的是63.,D,解析答案,解后反思,分析,解后反思 合理的转化是解题的关键.对于进位制之间的转化问题，一般要先把k进制数转化为十进制数，再转化为其他进制数.,数制转化方法掌握不牢致错,易错点,例5 把十字进制数49化为二进制数.,分析 对进位制间的换算，要弄清解题的办法，将十进制数转化为k进制数用“除k取余法”.,解,所以49110 001(2).,解后反思 本例常出现的错误是把上式中各步所得的余数从上到下排列，这是基本方法掌握不牢造成的，应加以注意.,分析,解析答案,解后反思,返回,当堂检测,1,2,3,4,5,1.1 337与382的最大公约数是( ) A.3 B.382 C.191 D.201,解析 利用辗转相除法，1 3373823191,3821912， 故两数的最大公约数为191.,C,解析答案,1,2,3,4,5,2.把189化为三进制数，则末位数字是( ) A.0 B.1 C.2 D.3,解析 采用“除k取余法”，得,即18921 000(3),A,解析答案,1,2,3,4,5,3.用秦九韶算法求n次多项式f(x)anxnan1xn1a1xa0当xx0时的值，求f(x0)需要乘方、乘法、加法的次数分别为( ),A. ，n，n B.n,2n，n C.0,2n，n D.0，n，n,解析 因为f(x)(anxan1)xan2)xa1)xa0， 所以乘方、乘法、加法的次数分别为0，n，n.,D,解析答案,1,2,3,4,5,4.用秦九韶算法求多项式f(x)7x66x53x22，当x4时的值时，先算的是( ) A.4416 B.7428 C.44464 D.74634,解析 因为f(x)anxnan1xn1a1xa0 (anxan1)xan2)xa1)xa0， 所以用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先算的是74634.,D,解析答案,1,2,3,4,5,5.用更相减损术求36与134的最大公约数，第一步应为_ _.,解析 36与134都是偶数， 第一步应为：先除以2，得到18与67.,先除以2，得到,18与67,解析答案,课堂小结,返回,1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术.用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复