《高中数学第一章算法初步1.3算法案例课件新人教A版必修3》由会员分享，可在线阅读，更多相关《高中数学第一章算法初步1.3算法案例课件新人教A版必修3（35页珍藏版）》请在金锄头文库上搜索。
1、第一章算法初步,1.3算法案例,学习目标,1.理解辗转相除法与更相减损术的含义，了解其执行过程. 2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质. 3.理解进位制的概念，能进行不同进位制间的转化. 4.了解进位制的程序框图和程序.,知识梳理 自主学习,题型探究 重点突破,当堂检测 自查自纠,栏目索引,知识梳理 自主学习,知识点一辗转相除法与更相减损术,1.辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法. (2)辗转相除法的算法步骤 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r0，则m，n的最大公约数等于 ；否则，返回 .,最
2、大公约数,两个正整数m，n,m除以n所得的余数r,mn，nr,m,第二步,答案,2.更相减损术 第一步，任意给定两个正整数，判断它们是否都是 .若是，用 约简；若不是，执行 . 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数.继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.,偶数,2,第二步,较大,较小,较小,相等,答案,3.辗转相除法和更相减损术的区别与联系：,思考实际应用更相减损术时要做的第一步工作是什么？,答先判断a，b是否为偶数，若是，都除以2再进行.,答案,知识点二秦九韶算法,1.秦九韶算法简介 (1)秦九韶算法
3、要解决的问题是求多项式的值. (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. 第三步
4、，输入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) (3)十六进制： 使用09十个数字和AF表示1015； F110(16),思考任何进位制中都要
5、用到的数字是什么？,答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)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数
6、除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. (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的
7、最大公约数为4.,解析答案,题型二秦九韶算法的应用,例2用秦九韶算法求多项式f(x)x55x410 x310 x25x1当x2时的值.,解f(x)x55x410 x310 x25x1(x5)x10)x10)x5)x1. 当x2时，有v01； v1v0 xa41(2)53； v2v1xa33(2)104； v3v2xa24(2)102； v4v3xa12(2)51； v5v4xa01(2)11. 故f(2)1.,解析答案,反思与感悟,反思与感悟,(1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可.这样比直接将x2代入原式大大减少了计算量.若用计算机计算，则可提高
8、运算效率. (2)注意：当多项式中n次项不存在时，可将第n次项看作0 xn.,跟踪训练2用秦九韶算法计算多项式f(x)x612x560 x4160 x3240 x2192x64当x2时的值.,解根据秦九韶算法，把多项式改写成如下形式： f(x)(x12)x60)x160)x240)x192)x64. 由内向外依次计算一次多项式当x2时的值； v01；v1121210； v21026040；v340216080； v480224080；v580219232； v6322640. 所以当x2时，多项式的值为0.,解析答案,题型三进位制之间的互化,例3(1)把二进制数1110011(2)化为十进制数
9、.,解1110011(2)1261251240230221211115.,(2)将8进制数314706(8)化为十进制数.,解314706(8)385184483782081680104 902. 所以，化为十进制数是104 902.,解析答案,反思与感悟,反思与感悟,(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果. (2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余.,跟踪训练3将53(8)转化为二进制数.,解先将八进制数53(8)转化为十进制数： 53(8)58138043； 再将十进制数43转
10、化为二进制数：,所以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化为
11、二进制数.,分析对进位制间的换算，要弄清解题的办法，将十进制数转化为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,解析采用“除
12、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秦九韶是我国南宋时期的数学家，普州(现四川省安岳县)人，他在所著的数书九章中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法如图所示的程序框图给出了利用秦九韶算法求某
13、多项式值的一个实例，若输入n，x的值分别为3,2，则输出v的值为() A9 B18 C20 D35,1,2,3,4,5,解析初始值n3，x2，程序运行过程如下 v1 i2v1224 i1v4219 i0v92018 i1跳出循环，输出v18，选B. 答案B,解析答案,1,2,3,4,5,5.用更相减损术求36与134的最大公约数，第一步应为_ _.,解析36与134都是偶数， 第一步应为：先除以2，得到18与67.,先除以2，得到,18与67,解析答案,课堂小结,返回,1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术.用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止. 2.秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行. 3.把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数.而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数.,本课结束,
