搜索
第一章算法初步1.3算法案例学习目标核心素养1．会用辗转相除法与更相减损术求两数的最大公约数．(重点、易混点)2．会用秦九韶算法求多项式的值．(重点)3．会在不同进位制间进行相互转化．(难点)1．通过古代传统算法，培养数学运算素养．2．借助算法案例，提升逻辑推理素养.自主预习探新知1．辗转相除法与更相减损术(1)辗转相除法①辗转相除法是用于求的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫．两个正整数的最大公约数欧几里得算法②所谓辗转相除法，就是对于给定的两个数，用除以．若余数不为零，则将构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时就是原来两个数的最大公约数．较小的数较大的数较小的数余数和较小的数(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＋a0，这种求n次多项式f(x)的值的方法叫秦九韶算法．由内向外最内层3．进位制(1)进位制是人们为了和而约定的记数系统．“满k进一”就是，k进制的基数是.(2)将k进制数化为十进制数的方法是：先把k进制数写成的形式，再．计数运算方便k进制k各位上的数字与k的幂的乘积之和按照十进制数的运算规则计算出结果(3)将十进制数化为k进制数方法是：．即，直到商为零为止，然后．就是相应的k进制数．把各步得到的余数倒排写出除k取余法用k连续去除十进制数所得的商1．在对16和12求最大公约数时，整个操作如下：16－12＝4,12－4＝8,8－4＝4.由此可以看出12和16的最大公约数是()A．4B．12C．16D．8A[根据更相减损术的方法判断．]2．下列有可能是4进制数的是()A．5123B．6542C．3103D．4312C[4进制中逢4进1，每位上的数字一定小于4.]3．已知多项式f(x)＝4x5＋3x4＋2x3－x2－x－12，用秦九韶算法求f(－2)等于()A．－1972B．1972C．1832D．－1832A[∵f(x)＝((((4x＋3)x＋2)x－1)x－1)x－12，∴f(－2)＝－1972.]4．利用辗转相除法求3869与6497的最大公约数时，第二步是________3869＝2628×1＋1241[第一步应为6497＝3869×1＋2628；第二步应为3869＝2628×1＋1241.]合作探究释疑难求最大公约数【例1】求228与1995的最大公约数．思路点拨：求两个正整数的最大公约数可以用辗转相除法，也可以用更相减损术．[解]法一：(辗转相除法)1995＝8×228＋171,228＝1×171＋57,171＝3×57，所以228与1995的最大公约数为57.法二：(更相减损术)1995－228＝1767,1767－228＝1539，1539－228＝1311,1311－228＝1083，1083－228＝855,855－228＝627，627－228＝399,399－228＝171，228－171＝57,171－57＝114，114－57＝57.所以228与1995的最大公约数为57.求最大公约数的两种方法1利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.2利用更相减损术求两个正整数的最大公约数的一般步骤是：第一步判断两个正整数是否都是偶数，若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数等数或这个数与约简的数的乘积就是所求的最大公约数.[跟进训练]1．用辗转相除法和更相减损术求1515与600的最大公约数，需要运算的次数分别为()A．4,15B．5,14C．5,13D．4,12B[辗转相除法：1515＝600×2＋315；600＝315×1＋285,315＝285×1＋30,285＝30×9＋15,30＝15×2，故最大公约数为15，且需计算5次．用更相减损术：1515－600＝915,915－600＝315,600－315＝285,315－285＝30,285－30＝255,255－30＝225,225－30＝195,195－30＝165,165－30＝135,135－30＝105,105－30＝75,75－30＝45,45－30＝15,30－15＝15.故最大公约数为15，且需计算14次．]秦九韶算法【例2】已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值．思路点拨：可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算．[解]将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式，当x＝5时的值：v0＝4；v1＝4×5＋2＝22；v2＝22×5＋3.5＝113.5；v3＝113.5×5－2.6＝564.9；v4＝564.9×5＋1.7＝2826.2；v5＝2826.2×5－0.8＝14130.2.所以当x＝5时，多项式的值等于14130.2.]利用秦九韶算法求多项式的值的步骤[跟进训练]2．用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋6x4＋5x5＋3x6在x＝－4时，v3的值为()A．－144B．－136C．－57D．34B[根据秦九韶算法多项式可化为f(x)＝(((((3x＋5)x＋6)x＋0)x－8)x＋35)x＋12.由内向外计算v0＝3；v1＝3×(－4)＋5＝－7；v2＝－7×(－4)＋6＝34；v3＝34×(－4)＋0＝－136.]进位制及其转化[探究问题]1．数学上通常使用什么进位制？它的原理是什么？[提示]十进制十进制的原理是满十进一．一个十进制正整数N可以写成an·10n＋an－1·10n－1＋…＋a1·101＋a0·100的形式，其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例如365＝3×102＋6×10＋5.2．你还知道哪些进位制？它们与目前我们使用的进位制数之间能否转化？[提示](1)二进制使用0和1这两个数字，基数为2.(2)八进制使用0,1,2,3,4,5,6,7这八个数字，基数为8.(3)十六进制使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个符号，基数为16.其中A，B，C，D，E，F分别相当于十进制中的10,11,12,13,14,15.它们与十进位制数之间可以转化，两个非十进制数之间也可以以十进制作“桥梁”，进行相互转化．3．不同的进位制数如何区分？[提示]一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示区别．例如270(8)表示270是一个8进制数．但十进制一般省略不写．【例3】下列四个数中，最大的是()A．11011(2)B．103(4)C．44(5)D．25思路点拨：先将各数都转化为十进制数，再比较大小．A[11011(2)＝1×24＋1×23＋0×22＋1×21＋1×20＝27，103(4)＝1×42＋0×41＋3×40＝19,44(5)＝4×51＋4×50＝24.∵27＞25＞24＞19，∴最大数是11011(2)．]1．(变条件)210(6)化成十进制数为________．78[210(6)＝2×62＋1×6＝78.]2．(变结论)把1234(5)化成七进制数为________．365(7)[∵1234(5)＝1×53＋2×52＋3×51＋4×50＝194.而∴1234(5)＝194＝365(7)]进位制的转换方法(1)要把k进制数化为十进制数，首先把k进制数表示成不同位上数字与k的幂的乘积之和，其次按照十进制的运算规则计算和．(2)十进制数化为k进制数(除k取余法)的步骤课堂小结提素养1．求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止．2．秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行．3．把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．1．判断下列结论的正误(正确的打“√”，错误的打“×”)(1)用辗转相除法与更相减损术都可以求两个正整数的最大公约数．()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率．()(3)不同进位制中，十进制的数比二进制的数大．()[答案](1)√(2)√(3)×2．用辗转相除法求72与120的最大公约数时，需要做除法次数为()A．4B．3C．5D．6B[120＝72×1＋48,72＝48×1＋24,48＝24×2.]3．将八进制数123(8)化为十进制数，结果为________．83[1×82＋2×81＋3×80＝64＋16＋3＝83.]4．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．[解]根据秦九韶算法，把多项式改写成如下形式：f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.而x＝2，所以有v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1397.所以当x＝2时，多项式的值为1397.Thankyouforwatching!