1、1.3 算 法 案 例 必备知识自主学习 1.辗转相除法与更相减损术(1)_，又叫欧几里得算法，是一种求两个正整数的_的 古老而有效的算法.(2)_是我国古代数学专著九章算术中介绍的一种求两个正整 数的_的算法.辗转相除法 最大公约数 更相减损术 最大公约数【思考】(1)怎样用辗转相除法求两个正整数的最大公约数？提示：辗转相除法的算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.(2)怎样用更相减损术求两个正整数的最大公约数？提示：更相减损术求两个正整数的最大公约数的基本过程是：第一
2、步，任意给定两个正整数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.2.秦九韶算法 把一个n次多项式f(x)=anxn+an-1xn-1+a1x+a0改写成如下形式：f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1=anx+an-1，然后由内向外逐层计算一次多项式的值，即v2=v1x+an-2，v3=v2x+an-3，vn=vn-1x
3、+a0，这种求n次多项式f(x)的值的方法叫秦九韶算法.【思考】(1)利用秦九韶算法将多项式改写为一次多项式时，如果某一项缺少，该怎么处理？提示：当多项式中n次项不存在时，可将第n项看作0 xn.(2)应用秦九韶算法求多项式的值时应怎样操作？提示：求多项式的值时，先计算最内层括号内一次多项式的值，即 v1=anx+an-1，再由内向外逐层计算一次多项式vk(k=2，3，4，n)的值.3.进位制 进位制是人们为了计数和运算方便而约定的记数系统.“满k进一”就是k进制，k进制的基数是 k.【思考】不同的进位制数如何区分？提示：一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示
4、区别.例如270(8)表示270是一个8进制数.但十进制一般省略不写.【基础小测】1.辨析记忆(对的打“”，错的打“”)(1)用辗转相除法与更相减损术都可以求两个正整数的最大公约数.()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率.()(3)不同进位制中，十进制的数比二进制的数大.()2.(教材二次开发：例题改编)在对16和12求最大公约数时，整个操作如下：16-12=4，12-4=8，8-4=4.由此可以看出12和16的最大公约数是()A.4 B.12 C.16 D.8【解析】选A.根据更相减损术的方法判断.3.下列有可能是4进制数的是()A.5 123 B.6 542 C.
5、3 103 D.4 312【解析】选C.4进制中逢4进1，每位上的数字一定小于4.4.设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A.顺序结构 B.条件结构 C.循环结构 D.以上都有【解析】选D.根据秦九韶算法的含义知选D.关键能力合作学习 类型一 求最大公约数(数学运算、逻辑推理)【题组训练】1.用辗转相除法求72与120的最大公约数时，需要做除法的次数为()A.4 B.3 C.5 D.6 2.98，280的最大公约数为()A.7 B.14 C.16 D.8 3.利用辗转相除法求3 869与6 497的最大公约数时，第二步是_.【解题策略】求最大公约数的两种方法步骤(1)利用
6、辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数，若是，用2约简；也可以不除以2，直接求最大公约数，这样不影响最后结果.【补偿训练】1.下列关于利用更相减损术求156和72的最大公约数的说法中正确的是()A.都是偶数必须约简 B.可以约简，也可以不约简 C.第一步作差为156-72=84；第二步作差为72-84=-12 D.以上都不对【解析】选B.约
7、简是为了使运算更加简捷，故不一定要约简，A错.C中第二步应为84-72=12.2.用辗转相除法和更相减损术求1 515与600的最大公约数，需要运算的次数分别为()A.4，15 B.5，14 C.5，13 D.4，12 类型二 秦九韶算法(数学抽象、逻辑推理)【典例】用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1，当x=2时的值.步骤内容理解 题意利用秦九韶算法求多项式在x=2时的值.思路 探求可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算步骤内容书写表达根据秦九韶算法把多项式改写成如下形式：f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+2x
8、+1=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.由内向外依次计算一次多项式，当x=2时的值v0=8，v1=82+5=21，v2=212+0=42，v3=422+3=87，v4=872+0=174，v5=1742+0=348，v6=3482+2=698，v7=6982+1=1 397.所以当x=2时，多项式的值为1 397.题后反思秦九韶算法的关键在于把n次多项式转化为一次多项式【解题策略】将多项式写成一次多项式的形式，从里到外一步一步地做乘法运算和加法运算，这样比直接将自变量的值代入大大减少了计算量，提高了运算效率.【跟踪训练】1.用秦九韶算法计算f(x)=6x5-4x4+x
9、3-2x2-9x，需要加法(或减法)与乘法运算的次数分别为()A.5，4 B.5，5 C.4，4 D.4，5【解析】选D.n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算.f(x)中无常数项，故加法次数要减少一次，为5-1=4.2.用秦九韶算法计算f(x)=3x4+2x2+x+4当x=10时的值的过程中，v1的值为_.【解析】改写多项式为f(x)=(3x+0)x+2)x+1)x+4，则v0=3，v1=310+0=30.答案：30 3.用秦九韶算法求多项式f(x)=7x5+5x4+10 x3+10 x2+5x+1当x=-2时的值：第一步，x=-2.第二步，f(
10、x)=7x5+5x4+10 x3+10 x2+5x+1.第三步，输出f(x).第一步，x=-2.第二步，f(x)=(7x+5)x+10)x+10)x+5)x+1.第三步，输出f(x).需要计算5次乘法，5次加法.需要计算9次乘法，5次加法.以上说法中正确的是_(填序号).类型三 进位制及其转化(数学运算、逻辑推理)角度1 十进制数转化为k进制数 【典例】85化成七进制数为_.【思路导引】用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出.角度2 k进制数转化为十进制数 【典例】把“五进制”数1234(5)转化为“十进制”数，再把它转化为“八进制”数.【思路导引】k进制化
11、十进制时，利用求各位上的数与k的幂的乘积后再相加的方法，十进制化其他进制可采用除k取余法.【解题策略】进位制的转换方法(1)要把k进制数化为十进制数，首先把k进制数表示成不同位上数字与k的幂的乘积之和，其次按照十进制的运算规则计算和.(2)十进制数化为k进制数(除k取余法)的步骤 要注意转化过程中基本结构与相应语句的对应.熟练后可直接写出程序.【题组训练】1.下列写法正确的是()A.858(8)B.865(7)C.121(3)D.68(6)【解析】选C.k进制中各位上的数字均小于k，故A，B，D错误.2.若六进制数1m05(6)(m为正整数)化为十进制数为293，则m=_.【解析】1m05(6
12、)=163+m62+5=221+36m=293，所以m=2.答案：2【补偿训练】1.已知三个数12(16)，25(7)，33(4)，将它们按由小到大的顺序排列为_.【解析】将三个数都化为十进制数.12(16)=116+2=18，25(7)=27+5=19，33(4)=34+3=15，所以33(4)12(16)25(7).答案：33(4)12(16)25(7)2.将八进制数123(8)化为十进制数，结果为_.【解析】182+281+380=64+16+3=83.答案：83 3.210(6)化成十进制数为_.【解析】210(6)=262+16=78.答案：78 课堂检测素养达标 1.给出下列说法：
13、在计算机中，做一次乘法运算所用的时间，比做一次加法运算所用的时间长得多；在计算机中，计算xk(k=2，3，n)要进行k次运算；因为秦九韶算法是在南宋时期提出的，所以现在在多项式求值中不是一种先进的算法；利用秦九韶算法求n次多项式的值时，可以将其转化为求n个一次多项式的值，其中正确的个数是()A.1 B.2 C.3 D.4【解析】选B.正确，不正确.2.把189化为三进制数，则末位数是()A.0 B.1 C.2 D.3【解析】选A.则末位数是0.3.利用辗转相除法求最大公约数，下列说法不正确的是()A.228和1 995的最大公约数是57 B.78和36的最大公约数是6 C.85和357的最大公
14、约数是34 D.153和119的最大公约数是17【解析】选C.由辗转相除法可得，85和357的最大公约数应该是17.4.(教材二次开发：练习改编)将51化为二进制数得_.【解析】答案：110011(2)5.阅读程序框图，利用秦九韶算法计算多项式f(x)=anxn+an-1xn-1+a1x+a0，当x=x0时，框图中A处应填入_.6.用两种方法求210与98的最大公约数.【解析】方法一：用辗转相除法：210=982+14，98=147.所以210与98的最大公约数为14.方法二：用更相减损术：因为210与98都是偶数，用2约简得 105和49，105-49=56，56-49=7，49-7=42，42-7=35，35-7=28，28-7=21，21-7=14，14-7=7.所以210与98的最大公约数为27=14.
