2019-2020学年高中数学 第1章 算法初步 1.3 算法案例课件 新人教A版必修3

第一章算法初步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】把“五进制”数1234(5)转化为“十进制”数，再把它转化为“八进制”数．思路点拨：k进制化十进制时，利用求各位上的数与k的幂的乘积后再相加的方法，十进制化为其他进制可采用除k取余法．[解]∵1234(5)＝1×53＋2×52＋3×51＋4×50＝194，而∴1234(5)＝194＝302(8)．1．(变条件)210(6)化成十进制数为________．85化成七进制数为________．78151(7)[210(6)＝2×62＋1×6＝78，所以85＝151(7)．]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.