1.3 算法案例

[学习目标] 1.理解辗转相除法与更相减损术的含义，了解其执行过程.2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质.3.理解进位制的概念，能进行不同进位制间的转化.4.了解进位制的程序框图和程序．知识点一辗转相除法与更相减损术1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．2．更相减损术第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．辗转相除法和更相减损术的区别与联系：答 先判断a ，b 是否为偶数，若是，都除以2再进行． 知识点二 秦九韶算法 1．秦九韶算法简介(1)秦九韶算法要解决的问题是求多项式的值． (2)秦九韶算法的特点：通过一次式的反复计算，逐步得到高次多项式的值，即将一个n 次多项式的求值问题归结为重复计算n 个一次多项式的值的问题． (3)秦九韶算法的原理：将f (x )＝a n x n ＋a n －1x n －1＋…＋a 1x ＋a 0改写为：f (x )＝(a n x n －1＋a n －1x n －2＋…＋a 1)x ＋a 0＝((a n x n－2＋a n －1x n －3＋…＋a 2)x ＋a 1)x ＋a 0＝…先计算最内层括号内一次多项式的值，即v 1＝a n x ＋a n －1，再由内向外逐层计算一次多项式v k 的值．2．秦九韶算法的操作方法 (1)算法步骤如下：第一步，输入多项式次数n 、最高次项的系数a n 和x 的值． 第二步，将v 的值初始化为a n ，将i 的值初始化为n －1. 第三步，输入i 次项的系数a i . 第四步，v ＝v x ＋a i ，i ＝i －1.第五步，判断i 是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v . (2)程序框图如图所示．(3)程序如下：知识点三进位制1．进位制的概念进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数(大于1的整数)就是几．2．常见的进位制(1)二进制：①只使用0和1两个数学；②满二进一，即1＋1＝10(2)．(2)八进制：①使用0,1,2,3,4,5,6,7这八个不同数学；②满八进一，即7＋1＝10(8)．(3)十六进制：①使用0～9十个数字和A～F表示10～15；②F＋1＝10(16)思考任何进位制中都要用到的数字是什么？答0和1.题型一求两个正整数的最大公约数例1分别用辗转相除法和更相减损术求261和319的最大公约数．解方法一(辗转相除法)319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.方法二(更相减损术)319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，29－29＝0，所以319与261的最大公约数是29.反思与感悟(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．跟踪训练1用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．解80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝40,36÷2＝18；40÷2＝20,18÷2＝9；20—9＝11,11－9＝2；9－2＝7,7－2＝5；5－2＝3,3－2＝1；2－1＝1,1×2×2＝4；所以80与36的最大公约数为4.题型二秦九韶算法的应用例2用秦九韶算法求多项式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1当x＝－2时的值．解f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1＝((((x＋5)x＋10)x＋10)x＋5)x＋1.当x＝－2时，有v0＝1；v1＝v0x＋a4＝1×(－2)＋5＝3；v2＝v1x＋a3＝3×(－2)＋10＝4；v3＝v2x＋a2＝4×(－2)＋10＝2；v4＝v3x＋a1＝2×(－2)＋5＝1；v5＝v4x＋a0＝1×(－2)＋1＝－1.故f(－2)＝－1.反思与感悟(1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝－2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．(2)注意：当多项式中n次项不存在时，可将第n次项看作0·x n.跟踪训练2用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值．解根据秦九韶算法，把多项式改写成如下形式：f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64.由内向外依次计算一次多项式当x＝2时的值；v0＝1；v1＝1×2－12＝－10；v2＝－10×2＋60＝40；v3＝40×2－160＝－80；v4＝－80×2＋240＝80；v5＝80×2－192＝－32；v6＝－32×2＋64＝0.所以当x＝2时，多项式的值为0.题型三进位制之间的互化例3(1)把二进制数1110011(2)化为十进制数．(2)将8进制数314706(8)化为十进制数．解(1)1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.(2)314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化为十进制数是104902.反思与感悟(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果．(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．跟踪训练3将53(8)转化为二进制数．解先将八进制数53(8)转化为十进制数：53(8)＝5×81＋3×80＝43；再将十进制数43转化为二进制数：所以53(8)＝101011(2)．转化与化归思想例4下列各数中，最小的数是()A．85(9)B．210(6)C．1000(4)D．111111(2)分析先将它们转化为十进制数，再进行比较．解析85(9)＝8×9＋5＝77,210(6)＝2×62＋1×6＋0＝78,1000(4)＝1×43＝64,111111(2)＝1×25＋1×24＋1×23＋1×22＋1×2＋1＝63.故最小的是63.答案 D解后反思合理的转化是解题的关键．对于进位制之间的转化问题，一般要先把k进制数转化为十进制数，再转化为其他进制数．数制转化方法掌握不牢致错例5 把十字进制数49化为二进制数．分析 对进位制间的换算，要弄清解题的办法，将十进制数转化为k 进制数用“除k 取余法”． 解所以49＝110001(2)．解后反思 本例常出现的错误是把上式中各步所得的余数从上到下排列，这是基本方法掌握不牢造成的，应加以注意．1．1337与382的最大公约数是( ) A ．3B ．382C ．191D ．201 答案 C解析 利用辗转相除法，1337＝382×3＋191,382＝191×2，故两数的最大公约数为191. 2．把189化为三进制数，则末位数字是( ) A ．0B ．1C ．2D ．3 答案 A解析 采用“除k 取余法”，得即189＝21000(3)3．用秦九韶算法求n 次多项式f (x )＝a n x n ＋a n －1x n －1＋…＋a 1x ＋a 0当x ＝x 0时的值，求f (x 0)需要乘方、乘法、加法的次数分别为( ) A.n (n ＋1)2，n ，nB ．n,2n ，nC ．0,2n ，nD ．0，n ，n答案 D解析 因为f (x )＝(…((a n x ＋a n －1)x ＋a n －2)x ＋…＋a 1)x ＋a 0，所以乘方、乘法、加法的次数分别为0，n ，n .4．秦九韶是我国南宋时期的数学家，普州(现四川省安岳县)人，他在所著的《数书九章》中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法．如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例，若输入n，x的值分别为3,2，则输出v的值为()A．9B．18C．20D．35答案 B解析初始值n＝3，x＝2，程序运行过程如下v＝1i＝2v＝1×2＋2＝4i＝1v＝4×2＋1＝9i＝0v＝9×2＋0＝18i＝－1跳出循环，输出v＝18，选B.5．用更相减损术求36与134的最大公约数，第一步应为________．答案先除以2，得到18与67解析∵36与134都是偶数，∴第一步应为：先除以2，得到18与67.1.求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a －b|这个式子，反复相减，直到r＝0为止．2．秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．3．把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．。