高中数学 第一章 算法初步 1_3 算法案例学案 新人教a版必修3

1.3 算法案例学习目标1.理解辗转相除法与更相减损术的含义，了解其执行过程.2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质.3.理解进位制的概念，能进行不同进位制间的转化.4.了解进位制的程序框图和程序知识点一辗转相除法与更相减损术1辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法(2)辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步2更相减损术第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数3辗转相除法和更相减损术的区别与联系：名称辗转相除法更相减损术区别(1)以除法为主；(2)两个整数的差值较大时，运算次数较少；(3)相除，余数为0时得结果(1)以减法为主；(2)两个整数的差值较大时，运算次数较多；(3)相减，减数与差相等时得结果；(4)相减前要进行是否都是偶数的判断联系(1)都是求两个正整数最大公约数的方法；(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)程序如下：INPUT“n”；nINPUT“an”；aINPUT“x”；xvain1WHILEi0PRINT“i”；iINPUT“ai”；avv*xaii1WENDPRINTvEND知识点三进位制1进位制的概念进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数(大于1的整数)就是几2常见的进位制(1)二进制：只使用0和1两个数学；满二进一，即1110(2)(2)八进制：使用0,1,2,3,4,5,6,7这八个不同数学；满八进一，即7110(8)(3)十六进制：使用09十个数字和AF表示1015；F110(16)思考任何进位制中都要用到的数字是什么？答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)化为十进制数(2)将8进制数314706(8)化为十进制数解(1)1110011(2)1261251240230221211115.(2)314706(8)385184483782081680104 902.所以，化为十进制数是104 902.反思与感悟(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余跟踪训练3将53(8)转化为二进制数解先将八进制数53(8)转化为十进制数：53(8)58138043；再将十进制数43转化为二进制数：所以53(8)101011(2)转化与化归思想例4下列各数中，最小的数是()A85(9)B210(6)C1000(4)D111111(2)分析先将它们转化为十进制数，再进行比较解析85(9)89577,210(6)26216078,1000(4)14364,111111(2)12512412312212163.故最小的是63.答案D解后反思合理的转化是解题的关键对于进位制之间的转化问题，一般要先把k进制数转化为十进制数，再转化为其他进制数数制转化方法掌握不牢致错例5把十字进制数49化为二进制数分析对进位制间的换算，要弄清解题的办法，将十进制数转化为k进制数用“除k取余法”解所以49110001(2)解后反思本例常出现的错误是把上式中各步所得的余数从上到下排列，这是基本方法掌握不牢造成的，应加以注意11337与382的最大公约数是()A3B382C191D201答案C解析利用辗转相除法3821912，故两数的最大公约数为191.2把189化为三进制数，则末位数字是()A0B1C2D3答案A解析采用“除k取余法”，得即18921000(3)3用秦九韶算法求n次多项式f(x)anxnan1xn1a1xa0当xx0时的值，求f(x0)需要乘方、乘法、加法的次数分别为()A.，n，nBn,2n，nC0,2n，nD0，n，n答案D解析因为f(x)(anxan1)xan2)xa1)xa0，所以乘方、乘法、加法的次数分别为0，n，n.4秦九韶是我国南宋时期的数学家，普州(现四川省安岳县)人，他在所著的数书九章中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例，若输入n，x的值分别为3,2，则输出v的值为()A9 B18 C20 D35答案B解析初始值n3，x2，程序运行过程如下v1i2v1224i1v4219i0v92018i1跳出循环，输出v18，选B.5用更相减损术求36与134的最大公约数，第一步应为_答案先除以2，得到18与67解析36与134都是偶数，第一步应为：先除以2，得到18与67.1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止2秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行3把一个非十进制数转化