算法案例导学案

高二年级数学（必修3）导学案一、自主预习（阅读课本34-39页，完成下列问题）任务1.辗转相除法（1）辗转相除法，又叫欧几里得算法，是一种求两个正整数的___________的古老而有效的算法．（2）辗转相除法的算法步骤第一步，给定________________.第二步，计算___________________.第三步，____________.第四步，若r＝0，则m、n的最大公约数等于___；否则，返回________.任务2.更相减损术第一步，任意给定两个正整数，判断它们是否都是_____．若是，用_______；若不是，执行_______ ．第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．任务3辗转相除法与更相减损术的区别和联系名称辗转相除法更相减损术区别①以除法为主．②两个整数差值较大时运算次数较少．③相除余数为零时得结果①以减法为主．②两个整数的差值较大时，运算次数较多．③相减，两数相等得结果．④相减前要做是否都是偶数的判断联系①都是求两个正整数的最大公约数的方法．②二者的实质都是递推的过程．③二者都要用循环结构来实现任务4秦九韶算法把一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写成如下形式：(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算_____________一次多项式的值，即v1＝__________，然后由内向外逐层计算一次多项式的值，即v2＝__________，v3＝__________，…………………，v n＝__________.这样，求n次多项式f(x)的值就转化为求________________的值．二、合作探究 归纳展示任务1：例1、分别用辗转相除法和更相减损术求261和319的最大公约数．规律方法 (1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．变式1. 用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．任务2：例2. 用秦九韶算法求f (x )＝3x 5＋8x 4－3x 3＋5x 2＋12x －6，当x ＝2的值．规律方法 (1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x ＝2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．(2) 注意：当多项式中n 次项不存在时，可将第n 次项看作nx •0 变式2. 用秦九韶算法计算f (x )＝6x 5－4x 4＋x 3－2x 2－9x ，需要加法与乘法运算的次数分别为( )．A ．5,4B ．5,5C ．4,4D ．4,5误区警示 对秦九韶算法中的运算次数理解错误 例 已知f(x)＝x5＋2x4＋3x3＋4x2＋5x ＋6，用秦九韶算法求这个多项式当x ＝2时的值时，做了几次乘法？几次加法？[错解] 根据秦九韶算法，把多项式改写成如下形式f(x)＝((((x ＋2)x ＋3)x ＋4)x ＋5)x ＋6.按照从内到外的顺序，依次计算一次多项式当x ＝2时的值：v1＝2＋2＝4；v2＝2v1＋3＝11；v3＝2v2＋4＝26；v4＝2v3＋5＝57；v5＝2v4＋6＝120.显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．在v1中虽然“v1＝2＋2＝4”，而计算机还是做了1次乘法“v1＝2×1＋2＝4”．因为用秦九韶算法计算多项式f(x)＝anxn ＋an －1xn －1＋…＋a1x ＋a0当x ＝x0时的值时，首先将多项式改写成f(x)＝(…(anx ＋an －1)x ＋…＋a1)x ＋a0，然后再计算v1＝anx ＋an －1，v2＝v1x ＋an －2，v3＝v2x ＋an －3，…，vn ＝vn －1x ＋a0.无论an 是不是1，这次的乘法都是要进行的． [正解] 由上分析可知，共做了5次乘法，5次加法． 追本溯源：直接法乘法运算的次数最多可达n ＋1n2，加法最多n 次，秦九韶算法通过转化把乘法运算的次数减少到最多n 次，加法最多n 次．1．利用秦九韶算法求P (x )＝a n x n ＋a n －1x n －1＋…＋a 1x ＋a 0，当x ＝x 0时P (x 0)的值，需做加法和乘法的次数分别为( ) A ．n ，n B ．n ，n (n ＋1)2C ．n,2n ＋1D ．2n ＋1，n (n ＋1)2。

1.4 算法案例[自主学习]1．符号Int(x )和Mod(a ，b )的含义是什么？2．“孙子问题”相当于怎样的数学问题？3.欧几里得辗转相除法是解决什么问题的数学方法，它的一般步骤是什么？[初探新知]1．“孙子问题”相当于求关于x ，y ，z 的不定方程组⎩⎪⎨⎪⎧ m ＝3x ＋2，m ＝5y ＋3，m ＝7z ＋2的正整数解．2．欧几里得辗转相除法(1)含义：求两个正数a ，b (a >b )的最大公约数的方法，称为欧几里得辗转相除法．(2)步骤：计算出a ÷b 的余数r ，若r ＝0，则b 即为a ，b 的最大公约数；若r ≠0，则把前面的除数b 作为新的被除数，把余数r 作为新的除数，继续运算，直到余数为0，此时的除数即为a ，b 的最大公约数．3．两个常用函数(1)Mod(a ，b )表示a 除以b 所得的余数．(2)Int(x )表示不超过x 的最大整数．[点睛]辗转相除法的理论根据是：由a ＝nb ＋r ⇒r ＝a －nb ，得a ，b 与b ，r 有相同的公约数．[小试牛刀]1．Int(5)＝________；Int ⎝⎛⎭⎫23＝________；Int(－3.14)＝________.答案：5 0 －42．用辗转相除法求32和14的最大公约数时，需要做________次除法运算．答案：33．用符号表示m被7除后余2为________．答案：Mod(m,7)＝2[典型题例][典例1]有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码．[解]设这三个数分别为m，m＋1，m＋2，则m满足的条件是Mod(m,15)＝0且Mod(m ＋1,17)＝0且Mod(m＋2,19)＝0.流程图：伪代码：[举一反三]下面一段伪代码的功能是________．2余1，除以3余2，除以5余3，又m 逐个增大，故输出的m 是满足条件的最小正整数．答案：求关于x ，y ，z 的不定方程组⎩⎪⎨⎪⎧ m ＝2x ＋1，m ＝3y ＋2，m ＝5z ＋3的最小正整数解[典例2] 用辗转相除法求396和270的最大公约数，并设计算法，画出流程图，写出伪代码．[解] 396＝270＋126,270＝2×126＋18,126＝18×7，因此396和270的最大公约数为18.算法如下：S1 a ←396S2 b ←270S3 如果Mod(a ，b )≠0，那么转S4，否则转S7S4 r ←Mod(a ，b )S5 a ←b b ←rS6 转 S3S7 输出b伪代码： 流程图：[举一反三]求396和270的最小公倍数．解：根据最大公约数和最小公倍数的关系可知这两个数的最小公倍数为396×270÷18＝5 940.[典例3]在平面直角坐标系中作出函数y＝2x和y＝4－x的图象，根据图象判断方程2x＝4－x的解的范围，再用二分法求这个方程的近似解(误差不超过0.001)，写出这个算法的伪代码，并画出流程图．[解]在同一坐标系内作出函数y＝2x和y＝4－x图象如图：由图象可知方程2x＝4－x有一根在[1,2]内．伪代码为：a←1b←2c←0.001While|a－b|≥cx0←(a＋b)/2f(a)←2a＋a－4f(x0)←2x0＋x0－4If f(x0)＝0 Then Exit WhileEnd IfIf f(a)f(x0)＜0Thenb←x0Elsea←x0End IfEnd WhilePrint x0流程图如下：[举一反三]在平面直角坐标系内作出y＝x2和y＝2x的图象，并判断方程x2＝2x在(－1,0)内有无实根．若有，求出这个实根的近似值(误差不超过0.01)．写出这个算法的伪代码．解：作出y＝x2和y＝2x的图象如图．由图可知方程x2＝2x在(－1,0)内有且只有一个实根x0.设f(x)＝x2－2x，∵f(－1)＞0 ，f(0)＜0，∴以上结论正确．求这个实根误差不超过0.01的近似值的伪代码如下：[达标训练][基础训练]1．Int ⎝⎛⎭⎫375＝________；Int(－11.2)＝________.答案：7 －122．用辗转相除法求85和51的最大公约数时，需要做除法的次数为________． 答案：33．84和32的最小公倍数是________．解析：先求84和32的最大公约数．84＝32×2＋20，32＝20＋12，20＝12＋8，12＝8＋4，8＝4×2.故84和32的最大公约数是4.所以84和32的最小公倍数为84×32÷4＝672.答案：6724．下列伪代码运行的一个结果是________．解析：此伪代码的功能是求⎩⎪⎨⎪⎧ m ＝4x ＋2，m ＝5x ＋3，m ＝7x ＋3的最小正整数，∴m ＝38.答案： 385．已知如图所示的流程图(其中的m ，n 为正整数)：(1)这个算法的功能是什么？(2)当m ＝286，n ＝91时，运行的结果是什么？解：(1)这个算法的功能是用辗转相除法求两个正整数的最大公约数．(2)∵286＝91×3＋13,91＝13×7，∴286与91的最大公约数是13.故运行结果为13.[能力提升]1．下列格式中正确的是________．①Mod(2,3)＝3；②Mod(3,2)＝2；③Mod(2,3)＝1; ④Mod(3,2)＝1.答案：④2．用二分法求方程的近似解，精确度为e，则循环结构的终止条件是______．(填序号)①|x1－x2|＞e；②x1－x2＝e；③x1＜e＜x2; ④|x1－x2|＜e.答案：④3．324,243,270的最大公约数为______．解析：324＝243×1＋81,243＝81×3＋0，故324和243的最大公约数为81.又270＝81×3＋27,81＝27×3＋0，∴324,243,270的最大公约数为27.答案：274．下列程序输出的n的值是__________．j←1n←0While j≤11j←j＋1If Mod(j，4)＝0Thenn←n＋1End Ifj←j＋1End WhilePrint n答案：35．m是一个正整数，对两个正整数a，b，如果a－b是m的倍数，则称a，b对模m 同余，用符号a≡b(Mod m)表示，则下列各式中：①12≡7(Mod5)；②21≡10(Mod3)；③34≡20(Mod2)；④47≡7(Mod40)．正确的有__________．(填序号)解析：逐一验证，由题意，①12－7＝5是5的倍数；②21－10＝11不是3的倍数；③34－20＝14是2的倍数；④47－7＝40是40的倍数．故①③④正确．答案：①③④6．下列伪代码的运行结果是________．a←120b←252While a≠bIf a＞ba←a－bElseb←b－aEnd IfEnd WhilePrint a解析：此伪代码的功能是求两个正整数的最大公约数．a，b的值依次是：(120,252)→(120,132)→(120,12)→(108,12)→(96,12)→(84,12)→(72,12)→(60,12)→(48,12)→(36，12)→(24,12)→(12,12)，∴输出12.答案：127．试写出求三个正整数a，b，c的最大公约数的算法语句．解：先写出的伪代码是求正整数a，b的最大公约数，设最大公约数用b表示，然后再写出求正整数b，c的最大公约数的伪代码，并输出其最大公约数，用b表示，可用“当型”语句写出伪代码．所求的算法语句(即伪代码)如下：Read a，b，cWhile Mod(a，b)≠0r←Mod(a，b)a←bb←rEnd WhileWhile Mod(c，b)≠0r←Mod(c，b)c←bb←rEnd WhilePrint b8．写出用二分法求方程x3－2x－3＝0在区间[1,2]内的一个近似解(误差不超过0.001)的一个算法，并画出流程图．解：本题考查了利用二分法算法求解方程近似解的方法．伪代码如下：流程图如图所示：。

辗转相除法与更相减损术学习目标：1°理解辗转相除法与更相减损术中蕴含的数学原理，根据原理进行算法分析； 2°能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3°感受算法的意义和价值。

知识情境：1：10 WHILE 语句: 计算机执行语句的过程是20 UNTIL 语句: 计算机执行语句的过程是你能编写一个程序,用二分法求方程220(0)x x -=>的近似解吗?2：我们已经学过求最大公约数的方法，你能求出18与30的公约数吗？如果公约数比较大而且根据我们的观察又不能得到一些公约数，又应该怎样求它们的最大公约数？比如,如何求1424与801的最大公约数？知识生成：1. 教学辗转相除法：思路：可以利用除法将大数化小,找两数的最大公约数.(适于两数较大时)(1)用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；(2)若0R ＝0,则n 为m,n 的最大公约数；若0R ≠0,则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；(3)若1R ＝0,则1R 为m,n 的最大公约数;若1R ≠0,则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R -即为所求的最大公约数.例题1：求两个正数1424和801的最大公约数.①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：(1) 任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.(2) 以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例题2. 用更相减损术求91和49的最大公约数.练一练：：1．求两个正数8251和2146;228和1995;5280和12155的最大公约数.2．用更相减损术求72和168的最大公约数.3．编写一个程序, 求两个正数8251和2146的最大公约数.4．比较辗转相除法与更相减损术的区别(1)都是求的方法，计算上辗转相除法以法为主，更相减损术以法为主，计算次数上法计算次数相对较少，特别当两个数字时计算次数的区别较明显．(2)从结果体现形式来看，辗转相除法体现结果是以则得到，而更相减损术则以而得到．。

一、辗转相除法与更相减损术1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的□01最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定□02两个正整数m，n.第二步，计算□03m除以n所得的余数r.第三步，□04m＝n，n＝r.第四步，若r＝0，则m，n□05m；否则，□06第二步．2．更相减损术(1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求□07两个正整数的最大公约数的算法．(2)基本过程第一步，任意给定两个正整数，判断它们是否都是□08偶数．若是，□09用2约简；若不是，执行□10第二步．第二步，以□11较大的数减去□12较小的数，接着把所得的差与□13较小的数比较，并以大数减小数，继续这个操作，直到所得的数□14相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．3．辗转相除法与更相减损术的区别与联系两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为0减数与差相等最大公约最后一步中的除数最后一步中的减数数的选取计算特点步骤较少，运算复杂步骤较多，运算简单相同点同为求两个正整数最大公约数的方法，都是递归过程1．秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》中提出的一种用于计算□15一元n次多项式的值的方法．2．把一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写成如下形式：f(x)＝□16(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.求多项式的值时，首先计算□17最内层括号内一次多项式的值，即v1＝□18a n x ＋a n－1，然后由内向外逐层计算一次多项式的值，即v2＝□19v1x＋a n－2，v3＝□20v2x＋a n－3，…v n＝□21v n－1x＋a0，这样，求n次多项式f(x)的值就转化为求□22n个一次多项式的值．三、进位制进位制是人们为了□23计数和□24运算方便而约定的记数系统，“满k进一”就是□25k进制，k进制的基数是k.把十进制数化为k进制数时，通常用除k取余法．1．判一判(正确的打“√”，错误的打“×”)(1)五进制的基数是5，用0,1,2,3,4,5六个数字表示．()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率．()(3)用秦九韶算法可以求两个正整数的最大公约数．()(4)不同进位制中，十进制的数比二进制的数大．()答案(1)×(2)√(3)×(4)×2．做一做(1)用更相减损术求98与63的最大公约数时，需做减法的次数为()A．4 B．5C．6 D．7答案C解析(98,63)→(35,63)→(35,28)→(7,28)→(7,21)→(7,14)→(7,7)，∴共进行6次减法．(2)用“辗转相除法”求得168与486的最大公约数是()A．3 B．4C．6 D．16答案C解析486＝168×2＋150,168＝150×1＋18,150＝18×8＋6,18＝3×6，故168与486的最大公约数为6.(3)下列关于利用更相减损术求156和72的最大公约数的说法中正确的是()A．都是偶数必须约简B．可以约简，也可以不约简C．第一步作差为156－72＝84；第二步作差为72－84＝－12D．以上都不对答案B解析约简是为了使运算更加简捷，故不一定要约简，A错误．C中第二步应为84－72＝12，故选B.(4)秦九韶算法是中国南宋时期的数学家秦九韶提出的一种求多项式值的简化算法，其求一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0值的算法是：v0＝a n，v1＝v0x＋a n－1，v2＝v1x＋a n－2，v3＝v2x＋a n－3，…，v n＝v n－1x＋a0，v n为所求f(x)的值，利用秦九韶算法，计算f(x)＝2x5＋x4＋3x3＋2x2＋x＋1当x＝2时的值时，v2的值为()A．2 B．5C．13 D．115答案C解析计算f(x)＝2x5＋x4＋3x3＋2x2＋x＋1时，当x＝2时，v0＝a n＝2，v1＝v0x＋a n－1＝2×2＋1＝5，v2＝v1x＋a n－2＝5×2＋3＝13.探究1求最大公约数例1如图所示的程序框图的算法思想源于数学名著《几何原本》中的“辗转相除法”，执行该程序框图(图中“m MOD n”表示m除以n的余数)，若输入的m，n分别为495,135，则输出的m＝()A．0 B．5C．45 D．90[答案]C[解析]该程序框图是求495与135的最大公约数，由495＝135×3＋90,135＝90×1＋45,90＝45×2，知495与135的最大公约数是45，所以输出的m＝45，故选C.拓展提升辗转相除法与更相减损术两种算法比较(1)使用辗转相除法，我们可依据a＝nb＋r这个式子，反复执行，直到r＝0为止，用更相减损术就依据r＝a－b这个式子，反复执行，直到r＝b为止．(2)由该题可以看出，用辗转相除法求最大公约数步骤较少，而用更相减损术运算较易，解题时要灵活运用．【跟踪训练1】求612,396,264的最大公约数．解这三个整数都比较大，适合用辗转相除法，具体步骤如下：612＝396×1＋216；396＝216×1＋180；216＝180×1＋36；180＝36×5.所以612和396的最大公约数为36.又264＝36×7＋12；36＝12×3.所以264和36的最大公约数为12，综上可得，612,396,264的最大公约数是12.探究2秦九韶算法及应用例2已知f(x)＝x5＋x3＋x2＋x＋1，求f(3)的值．[解]原多项式可化为f(x)＝((((x＋0)x＋1)x＋1)x＋1)x＋1，当x＝3时，v0＝1，v1＝1×3＝3，v2＝3×3＋1＝10，v3＝10×3＋1＝31，v4＝31×3＋1＝94，v5＝94×3＋1＝283，所以f(3)的值为283.[变式探究]本例在求f(3)的值过程中，加法、乘法运算的次数分别为多少？解加法4次，乘法5次．拓展提升用秦九韶算法计算多项式的值时应注意的问题当多项式中出现空项时，利用秦九韶算法求多项式的值，要补上系数为0的相应项，例如本题中的0x4这一项．当一个多项式空项很多时，用一般的计算方法可能更简单一些，如对于f(x)＝x6－2x2＋5，求f(2)的值，就没有必要再利用秦九韶算法了，直接将x＝2代入计算即可．【跟踪训练2】用秦九韶算法求多项式f(x)＝7x3＋3x2－5x＋11在x＝23时的值，在运算过程中下列数值不会出现的是()A．164 B．3767C．86652 D．85169答案D解析f(x)＝7x3＋3x2－5x＋11＝x[x(7x＋3)－5]＋11，则v0＝7，v1＝7×23＋3＝164，v2＝164×23－5＝3767，v3＝3767×23＋11＝86652，故在运算过程中不会出现的数值是D.探究3进位制例3(1)把二进制数1101(2)化为十进制数为________；(2)将十进制数458转化为四进制数为________；(3)比较85(9)和210(6)的大小．[答案](1)13(2)13022(4)(3)见解析[解析](1)1101(2)＝1×23＋1×22＋0×21＋1×20＝13，所以二进制数1101(2)转化为十进制的数为13.(2)所以458＝13022(4)．(3)因为85(9)＝5＋8×9＝77，210(6)＝0＋1×6＋2×62＝78，而78>77，所以210(6)>85(9)．拓展提升十进制数转化为其他进制数的方法步骤【跟踪训练3】(1)将101111011(2)转化为十进制的数；(2)将235(7)转化为十进制的数；(3)将137(10)转化为六进制的数；(4)将53(8)转化为二进制的数．解(1)101111011(2)＝1×28＋0×27＋1×26＋1×25＋1×24＋1×23＋0×22＋1×21＋1×20＝379(10)．(2)235(7)＝2×72＋3×71＋5×70＝124(10)．(3)∴137(10)＝345(6)．(4)53(8)＝5×81＋3×80＝43(10)．∴53(8)＝101011(2)．1.辗转相除法与更相减损术的区别和联系 名称辗转相除法更相减损术区别①以除法为主②两个整数差值较大时运算次数较少③相除余数为零时得结果 ①以减法为主②两个整数的差值较大时，运算次数较多③相减，两数相等得结果 ④相减前要做是否都是偶数的判断联系 ①都是求最大公约数的方法②二者的实质都是递归的过程③二者都要用循环结构来实现注意：应用更相减损术时，相减之前先判断两个数是否为偶数，若都是偶数则要反复除2，直至至少出现一个奇数为止．最后的公约数也是相减之后的数乘以约简数.2.秦九韶算法的特点秦九韶算法的特点在于把求一个n 次多项式的值转化为求n 个一次多项式的值，即把求f (x )＝a n x n ＋a n －1·x n －1＋…＋a 1x ＋a 0的值转化为求递推公式： ⎩⎨⎧v 0＝a n ，v k ＝v k －1x ＋a n －k (k ＝1，2，…，n ).这样可以最多计算n 次乘法和n 次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数，提高了运算效率. 3.十进制与其他进制的转化(1)将k进制转化为十进制的方法：先把k进制数写成各位上的数字与k的幂的乘积的形式，再按十进制的运算规则计算．(2)将十进制化成k进制的方法：用除k取余法，用k连续去除十进制数所得的商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的k进制数．注意：两个非十进制的数之间的转化，可以先化成十进制数，再化成另一进制的数，即将十进制作为“桥梁”.1．三位四进制数中的最大数等于十进制数的()A．63 B．83C．189 D．252答案A解析三位四进制数中的最大数为333(4)，则333(4)＝3×42＋3×41＋3＝63.2．把389化为四进制数，则该数的末位是()A．1 B．2C．3 D．4答案A解析故389＝12011(4)，末位为1.3．用秦九韶算法计算多项式f(x)＝3x6＋4x5－5x4＋6x3－7x2＋8x＋1，当x＝2时的值时，需要做乘法和加法的次数分别是()A．6,6 B．5,6C．5,5 D．6,5答案A解析由秦九韶算法将多项式改成如下形式：f(x)＝(((((3x＋4)x－5)x＋6)x－7)x＋8)x＋1，按由内到外的顺序，依次计算x＝2时的值．v0＝3，v1＝3×2＋4＝10，v2＝10×2－5＝15，v3＝15×2＋6＝36，v4＝36×2－7＝65，v5＝65×2＋8＝138，v6＝138×2＋1＝277.这样求多项式的值时，是通过求6个一次多项式的值得到的，故进行了6次乘法和6次加法．4．若175(r)＝125，则r＝________.答案8解析由题意可得，1×r2＋7×r＋5×r0＝125，整理得r2＋7r－120＝0，解得r＝8或r＝－15(舍去)，∴r＝8.5．用辗转相除法求294,84两数的最大公约数，并用更相减损术检验你的结果．解辗转相除法求解如下：294＝84×3＋42，84＝42×2.所以294与84的最大公约数是42.更相减损术验证如下：因为294与84都是偶数，可同时除以2，得147与42.因为147－42＝105，105－42＝63，63－42＝21，42－21＝21，所以294与84的最大公约数为21×2＝42.A级：基础巩固练一、选择题1．4830与3289的最大公约数为()A．23 B．35 C．11 D．13答案A解析4830＝1×3289＋1541；3289＝2×1541＋207；1541＝7×207＋92；207＝2×92＋23；92＝4×23.∴23是4830与3289的最大公约数．2．用辗转相除法计算56和264的最大公约数时，需要做的除法次数是() A．3 B．4 C．6 D．7答案B解析∵264÷56＝4……40,56÷40＝1……16,40÷16＝2……8,16÷8＝2，∴264与56的最大公约数是8，需要做的除法次数是4.故选B.3．用更相减损术求459与357的最大公约数，需要做减法的次数为() A．4 B．5 C．6 D．7答案B解析459－357＝102,357－102＝255,255－102＝153,153－102＝51,102－51＝51，所以459与357的最大公约数为51，共做减法5次．4．下列各数，化为十进制后，最大的为()A．101010(2)B．111(5)C．32(8)D．54(6)答案A解析101010(2)＝1×25＋0×24＋1×23＋0×22＋1×21＋0×20＝42,111(5)＝1×52＋1×51＋1×50＝31,32(8)＝3×81＋2×80＝26,54(6)＝5×61＋4×60＝34.故转化为十进制后，最大的是101010(2)．5．《周易》历来被人们视作儒家群经之首，它表现了古代中华民族对万事万物的深刻而又朴素的认识，是中华人文文化的基础，它反映出中国古代的二进制计数的思想方法．我们用近代术语解释为：把阳爻“——”当作数字“1”，把阴爻“— —”当作数字“0”，则八卦所代表的数表示如下：依此类推，则六十四卦中的“屯”卦，符号“”表示的十进制数是()A．18 B．17 C．16 D．15答案B解析由题意类推，可知六十四卦中的“屯”卦，符号“”表示的二进制数为010001，转化为十进制数，为1×20＋0×21＋0×22＋0×23＋1×24＋0×25＝17.二、填空题6．阅读程序框图，利用秦九韶算法计算多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x ＋a0，当x＝x0时，框图中A处应填入________．答案a n－k解析f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0，先用秦九韶算法改为一次多项式，f(x)＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.f1＝a n；k＝1，f2＝f1x0＋a n－1；k＝2，f3＝f2x0＋a n－2；…；归纳得第k次f k＋1＝f k x0＋a n－k.故A处应填a n－k.7．设2134与1455的最大公约数为m，则m化为三进制数为________．答案10121(3)解析2134＝1455＋679,1455＝679×2＋97,679＝97×7，∴2134与1455的最大公约数为97，∴m＝97.用97连续除3取余数，可得97化为三进制数为10121(3)．8．十六进制数与十进制数的对应如表：例如：A＋B＝11＋12＝16＋7＝F＋7＝17(16)，所以A＋B的值用十六进制表示就等于17(16)．试计算：A×B＋D＝________(用十六进制表示)．答案92(16)解析∵A×B＋D＝11×12＋14＝146,146÷16＝9……2,9÷16＝0……9，∴用十六进制表示146为92(16)．三、解答题9．10x1(2)＝y02(3)，求数字x，y的值．解∵10x1(2)＝1×20＋x×21＋0×22＋1×23＝9＋2x，y02(3)＝2×30＋y×32＝9y＋2，∴9＋2x＝9y＋2且x∈{0,1}，y∈{0,1,2}，所以x＝1，y＝1.B级：能力提升练10．用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64，当x＝2时的值．解将f(x)改写为f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，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.所以f(2)＝0，即x＝2时，原多项式的值为0.。

辗转相除法与更相减损术学习目标：1°理解辗转相除法与更相减损术中蕴含的数学原理，根据原理进行算法分析； 2°能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3°感受算法的意义和价值。

知识情境：1：10 WHILE 语句: 计算机执行语句的过程是20 UNTIL 语句: 计算机执行语句的过程是你能编写一个程序,用二分法求方程220(0)x x -=>的近似解吗?2：我们已经学过求最大公约数的方法，你能求出18与30的公约数吗？ 如果公约数比较大而且根据我们的观察又不能得到一些公约数，又应该怎样求它们的最大公约数？比如,如何求1424与801的最大公约数？知识生成：1. 教学辗转相除法：思路：可以利用除法将大数化小,找两数的最大公约数.(适于两数较大时)(1)用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；(2)若0R ＝0,则n 为m,n 的最大公约数；若0R ≠0,则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；(3)若1R ＝0,则1R 为m,n 的最大公约数;若1R ≠0,则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R -即为所求的最大公约数.例题1：求两个正数1424和801的最大公约数.①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：(1) 任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.(2) 以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例题2. 用更相减损术求91和49的最大公约数.练一练：：。

《算法案例——辗转相除法与更相减损术》导学案
Ⅰ知识回顾
回顾短除法求两个数的最大公约数。

例：求18与30的最大公约数。

Ⅱ知识探究(一)
如何求两个较大的数（如8251与6105）的最大公约数？
阅读书本P34，思考：
1、为什么求8251与6105的最大公约数可转化为求6105与2146的最大公约数？
2、仿照这个例题过程，求4081与20723的最大公约数.
3、能否将辗转相除法编写成一个计算机程序？需要用到什么语句？
框图1（直到型）：程序：
框图2（当型）：程序：
Ⅲ巩固提高
练习：1、（课本P45练习1）用辗转相除法求下列两个数的最大公约数：（1）225,135；（2）98,196；（3）72,168；（4）153,119.
2、求三个数：324，243，135的最大公约数.
3、求228与1995的最小公倍数.
Ⅳ知识探究（二）
阅读书本P36，理解更相减损术的过程和步骤。

1、仿照书本例题，利用更相减损术求5280与12115的最大公约数，并用辗转相
除法进行验证。

2、那种方法简单？比较这两种方法的区别。

Ⅴ小结
总结回顾辗转相除法和更相减损术的步骤。