专题1.3 算法案例-20届高中数学同步讲义人教版（必修3）

《专题1.3 算法案例-20届高中数学同步讲义人教版（必修3）》由会员分享，可在线阅读，更多相关《专题1.3 算法案例-20届高中数学同步讲义人教版（必修3）（17页珍藏版）》请在七七文库上搜索。

1、1求两个正整数的最大公约数的算法（1）辗转相除法定义：辗转相除法是用于求_的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数算法步骤用辗转相除法求两个正整数的最大公约数，其算法步骤如下：第一步，给定两个正整数学科#网第二步，计算除以所得的余数第三步，第四步，若，则的最大公约数等于；否则，返回第二步程序框图如图所示：程序如下：INPUT m，nDO r=m MOD n m=nn=r LO

2、OP UNTIL r=0PRINT mEND或INPUT m，nr=1While r0 r=m MOD n m=nn=r WENDPRINT mEND（2）更相减损术定义：中国古代的数学专著九章算术中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也以等数约之”算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数程序框图程序如下：INPUT “

3、a，b=”;a，bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND2秦九韶算法（1）定义及原理：把一个n次多项式改写成如下形式：求多项式的值时，首先计算最内层括号内一次多项式的值，即，然后由内向外逐层计算一次多项式的值，即，这种求n次多项式的值的方法叫做秦九韶算法学*科网（2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n个一次式，可见计算时要用到的值，若令，我们可以得到下面的递推公式：这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现（3）算法步骤第一步，输入多项式次数n、最高次项的系数和x的值第二步，

4、将v的值初始化为，将i的值初始化为n1第三步，输入i次项的系数第四步，第五步，判断i是否大于或等于0若是，则返回第三步；否则，输出多项式的值v（4）程序框图如图所示：（5）程序如下：INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1WENDPRINT vEND3进位制（1）定义：进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满六十进一，就是六十进制；等等也就是说，“满几进一”就是几进制，几进制的基数就是几

5、一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式：说明：若一个数为十进制数，其基数可以省略不写学科#网若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数（2）将进制数转化为十进制数算法步骤：计算进制数的右数第位数字与的乘积，再将其累加，这是一个重复操作的步骤所以，可以用循环结构来构造算法，算法步骤如下：第一步，输入和的值第二步，将的值初始化为0，的值初始化为1第三步，第四步，判断是否成立若是，则执行第五步；否则，返回第三步第五步，输出的值程序框图如图所示：程序如下：INPUT “a，k，n=”；a，k，nb=0i=1t=

6、a MOD 10DO b=b+t*k(i-1) a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND（3）将十进制数转化为进制数转化方法：十进制数化为进制数用_，即先把十进制数a除以，商为，余数为，再把除以，商为，余数为，反复进行这种除法，直到商除以所得的商为0，余数是，即为止，此时将所有余数按从右到左排列就得到所要求的进制数算法步骤：第一步，给定十进制正整数a和转化后的数的基数第二步，求出a除以所得的商，余数第三步，把得到的余数依次从右到左排列第四步，若，则，返回第二步；否则，输出全部余数排列得到的进制数程序框图如图所示：程序如下：INPUT “a，k=

7、”；a，kb=0i=0DO q=ak r=a MOD k b=b+r*10i i=i+1 a=qLOOP UNTIL q=0PRINT bENDK知识参考答案：1（1）两个正整数2（2）3（3）除取余法K重点辗转相除法、更相减损术、秦九韶算法、进位制K难点用秦九韶算法求多项式的值，进位制间的转换K易错易对秦九韶算法中的运算次数理解错误1辗转相除法与更相减损术辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别两者的区别是：（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程学科.网（2）辗转相除法，下一次进行相除时，由

8、上一次的除数和余数直接相除即可而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数【例1】用辗转相除法和更相减损术求840与1764的最大公约数【答案】840与1764的最大公约数是84【解析】辗转相除法：1764=8402+84，840=8410+0，840与1764的最大公约数是84更相减损术：1764840=924，924840=84，84084=756，75684=672，67284=588，58884=504，50484=420，42084=33

9、6，33684=252，25284=168，16884=84，840与1764的最大公约数是84【例2】利用辗转相除法求3869与6497的最大公约数【答案】3869与6497的最大公约数为73【名师点睛】辗转相除法计算次数少，而更相减损术计算次数多，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，所以一般当数较小时考虑用更相减损术，当数较大时考虑用辗转相除法2秦九韶算法秦九韶算法的实质是：求多项式的值时，转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算这种算法的运算次数较少，是多项式求值比较先进的算法【例3】 用秦九韶算法计算多项式f（x）=12+35x8x2+79x

10、3+6x4+5x5+3x6在x=4时的值时，V3的值为A845B220C57D34【答案】C【解析】多项式f（x）=12+35x8x2+79x3+6x4+5x5+3x6=（3x+5）x+6）x+79）x8）x+35）x+12，当x=4时，v0=3，v1=3（4）+5=7，v2=7（4）+6=34，v3=34（4）+79=57故选C【例4】用秦九韶算法计算函数f（x）=2x4+3x3+5x4在x=2时的函数值【答案】62【名师点睛】利用秦九韶算法计算多项式的值的策略：（1）正确地将多项式改写，若在多项式中有几项不存在，可将这些项的系数看成0，即把这些项看做（2）由内向外逐次计算学科*网（3）每一

11、步计算结果准确，由于下一次计算用到上一次计算的结果，应认真、细致地计算每一步3进位制把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数【例5】将八进制数127（8）化为十进制数【答案】87【解析】【例6】已知一个k进制的数123（k）与十进制的数38相等，求k的值【答案】5【解析】将转化为十进制，由题意，得k2+2k+3=38，所以k2+2k35=0，所以k=5或k=7（舍）所以k=5【名师点睛】除k取余法的两个关注点：要连续除：用k连续去除十进制数或所得的商，直到商为零为止若是其他进位制的数，在没有特别说明的前提下，其基数必

12、须写出，常在数的右下角标明基数1秦九韶算法的先进性主要体现在减少运算次数，下列说法正确的是A可以减少加法运算次数B可以减少乘法运算次数C同时减少加法和乘法的运算次数D加法次数和乘法次数都有可能减少2用秦九韶算法求多项式，当时的值，先算的是A44=16B74=28C444=64D74+6=343把十进制的23化成二进制数是A00 110（2）B10 111（2）C10 1111（2）D11 101（2）4若十进制数26等于k进制数32，则k等于A4B5C6D85用更相减损术求294和84的最大公约数时，需要做减法的次数是A3B4C5D661 037和425的最大公约数是A51B17C9D37已知

13、多项式，用秦九韶算法求等于ABCD8用更相减损术求156与91的最大公约数时，需要做减法的次数是_9将45（6）改写成十进制数为_10用秦九韶算法计算多项式当时的值时，乘法运算的次数为_11用更相减损术求288与153的最大公约数12用秦九韶算法求多项式当时的值13在下列四个数中，最小的数是ABCD14用秦九韶算法计算多项式当时的值时，的值为ABCD15若98与63的最大公约数为，二进制数化为十进制数为，则A53B54C58D6016用更相减损术求123和48的最大公约数是A3B7C9D1217计算机是将信息转换成二进制处理，二进制即“逢二进一”，如表示二进制数将它转化成十进制形式是，那么将二

14、进制数（2）转换成十进制形式是A217-2B216-2C216-1D215-118在下列各数中，最大的数是ABCD19完成进位制之间的转化：_20（1）把八进制数化为十进制数；（2）把1285化为16进制数21先将412（5）化成十进制的数，然后用“除k取余法”再化成七进制的数22用辗转相除法和更相减损术求261与319的最大公约数1234567131415161718BDBDBBADBCACB1【答案】B【解析】通过对秦九韶算法的理解，可知它的主要作用是减少乘法的次数，将原来的乘法次数由减少到n，而对加法没有影响故选B学科%网2【答案】D3【答案】B【解析】232=111，112=51，52

15、=21，22=10，12=01，故23（10）=10111（2）故选B4【答案】D【解析】由题意知，解得故选D5【答案】B【解析】6【答案】B【解析】1 0374252187，425187251，18751334，5134117，34172，即1 037和425的最大公约数是177【答案】A【解析】，8【答案】5【解析】求最大公约数的过程如下：，故13是最大公约数，共进行了5次减法运算9【答案】29（10）【解析】由于45（6）=461+560=29（10）故答案为：29（10）10【答案】5【解析】，不难发现要经过5次乘法，5次加法运算11【答案】详见解析【解析】288153135，1531

16、3518，13518117，1171899，991881，811863，631845，451827，27189，1899因此288与153的最大公约数为912【答案】详见解析13【答案】D【解析】因为，所以最小的数是故选D14【答案】B【解析】，则，故选B15【答案】C【解析】，和的最大公约数是7，即二进制数化为十进制数为，即，则故选C学科*网16【答案】A【解析】123-48=75，75-48=27，48-27=21，27-21=6，21-6=15，15-6=9，9-6=3，6-3=3，所以123和48的最大公约数是317【答案】C【解析】（2）18【答案】B19【答案】213【解析】，20【答案】（1）3809；（2）【解析】（1）=；（2）用16连续去除1285，直到商为0为止，所得到的余数依次从右向左排列，就得到21【答案】详见解析【解析】412（5）=250+151+452=2+5+425=107，107=715+2，15=72+1，2=70+2把5进制的数412（5）化为7进制是212（7）22【答案】详见解析【解析】辗转相除法：319261158，26158429，58=292，学科网所以261与319的最大公约数为29