高中数学必修二 专题1.3 算法案例(1)

第一章算法初步1.3算法案例1．求两个正整数的最大公约数的算法（1）辗转相除法①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数．②算法步骤用辗转相除法求两个正整数的最大公约数，其算法步骤如下：第一步，给定两个正整数,mn．第二步，计算m除以n所得的余数r．第三步，,mnnr．学+科网第四步，若0r，则,mn的最大公约数等于m；否则，返回第二步．③程序框图如图所示：④程序如下：INPUTm，nDOr=mMODnm=nn=rPRINTmEND或INPUTm，nr=1Whiler0r=mMODnm=nn=rPRINTmEND（2）更相减损术①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．”②算法步骤第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．③程序框图④程序如下：INPUT“a，b=”;a，bWHILEa≠br=a-bIFbrTHENa=bb=rELSEa=rENDIFWENDPRINTbEND2．秦九韶算法（1）定义及原理：把一个n次多项式1110()nnnnfaxaxxaxa改写成如下形式：2110()((()))nnnfaxaxxaxaxa．求多项式的值时，首先计算最内层括号内一次多项式的值，即11nnvaxa，然后由内向外逐层计算一次多项式的值，即212323,nnvvxavvxa，…，10nnvvxa，这种求n次多项式()fx的值的方法叫做秦九韶算法．（2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n个一次式，可见计算kv时要用到1kv的值，若令0nva，我们可以得到下面的递推公式：0____________(1,2,,)nkvavkn．这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现．（3）算法步骤第一步，输入多项式次数n、最高次项的系数na和x的值．第二步，将v的值初始化为na，将i的值初始化为n－1．第三步，输入i次项的系数ia．第四步，,1ivvxaii．第五步，判断i是否大于或等于0．若是，则返回第三步；否则，输出多项式的值v．（4）程序框图如图所示：（5）程序如下：INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi=0PRINT“i=”；iINPUT“ai=”；av=v*x+ai=i-1WENDPRINTvEND3．进位制（1）定义：进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满六十进一，就是六十进制；等等．也就是说，“满几进一”就是几进制，几进制的基数就是几．一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式：1210()110110(,,,,,0,0,,,)nnnknnnnaaaaaaaaaakaaakN．说明：①若一个数为十进制数，其基数可以省略不写．②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．（2）将k进制数转化为十进制数①算法步骤：计算k进制数a的右数第i位数字ia与1ik的乘积1iiak，再将其累加，这是一个重复操作的步骤．所以，可以用循环结构来构造算法，算法步骤如下：第一步，输入,ak和n的值．第二步，将b的值初始化为0，i的值初始化为1．第三步，1,1iibbakii．第四步，判断in是否成立．若是，则执行第五步；否则，返回第三步．第五步，输出b的值．②程序框图如图所示：③程序如下：INPUT“a，k，n=”；a，k，nb=0i=1t=aMOD10DOb=b+t*k^(i-1)a=a\10t=aMOD10i=i+1LOOPUNTILinPRINTbEND（3）将十进制数转化为k进制数①转化方法：十进制数化为k进制数用____________，即先把十进制数a除以k，商为0q，余数为0r，再把0q除以k，商为1q，余数为1r，…，反复进行这种除法，直到商1nq除以k所得的商为0，余数是nr，即1nnqr为止，此时将所有余数按从右到左排列就得到所要求的k进制数10()nnkrrr．②算法步骤：第一步，给定十进制正整数a和转化后的数的基数k．第二步，求出a除以k所得的商q，余数r．第三步，把得到的余数依次从右到左排列．第四步，若0q，则aq，返回第二步；否则，输出全部余数r排列得到的k进制数．③程序框图如图所示：学！科网④程序如下：INPUT“a，k=”；a，kb=0i=0DOq=a\kr=aMODkb=b+r*10^ii=i+1a=qLOOPUNTILq=0PRINTbENDK知识参考答案：1．（1）两个正整数2．（2）1knkvxa3．（3）①除k取余法K—重点辗转相除法、更相减损术、秦九韶算法、进位制K—难点用秦九韶算法求多项式的值，进位制间的转换K—易错易对秦九韶算法中的运算次数理解错误1．辗转相除法与更相减损术辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别．两者的区别是：学科+网（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程．（2）辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数．【例1】用辗转相除法和更相减损术求840与1764的最大公约数．【答案】840与1764的最大公约数是84．【解析】辗转相除法：1764=840×2+84，840=84×10+0，∴840与1764的最大公约数是84．更相减损术：1764–840=924，924–840=84，840–84=756，756–84=672，672–84=588，588–84=504，504–84=420，420–84=336，336–84=252，252–84=168，168–84=84，∴840与1764的最大公约数是84．【例2】利用辗转相除法求3869与6497的最大公约数．【名师点睛】辗转相除法计算次数少，而更相减损术计算次数多，但是更相减损术每一步的计算都是减法，比做除法运算要简单一些，所以一般当数较小时考虑用更相减损术，当数较大时考虑用辗转相除法．2．秦九韶算法秦九韶算法的实质是：求多项式1110()nnnnfaxaxxaxa的值时，转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算．这种算法的运算次数较少，是多项式求值比较先进的算法．【例3】用秦九韶算法计算多项式f（x）=12+35x–8x2+79x3+6x4+5x5+3x6在x=–4时的值时，V3的值为A．–845B．220C．–57D．34【答案】C【解析】∵多项式f（x）=12+35x–8x2+79x3+6x4+5x5+3x6=（（（（（3x+5）x+6）x+79）x–8）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+5x–4在x=2时的函数值．【名师点睛】利用秦九韶算法计算多项式的值的策略：（1）正确地将多项式改写，若在多项式中有几项不存在，可将这些项的系数看成0，即把这些项看做0nx．（2）由内向外逐次计算．（3）每一步计算结果准确，由于下一次计算用到上一次计算的结果，应认真、细致地计算每一步．3．进位制把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．【例5】将八进制数127（8）化为十进制数．【答案】87【解析】21081271828786416787．【例6】已知一个k进制的数123（k）与十进制的数38相等，求k的值．【答案】5【解析】将转化为十进制，210212312323kkkkkk，由题意，得k2+2k+3=38，所以k2+2k–35=0，所以k=5或k=–7（舍）所以k=5．【名师点睛】除k取余法的两个关注点：①要连续除：用k连续去除十进制数或所得的商，直到商为零为止．②若是其他进位制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．1．秦九韶是我国古代数学家的杰出代表之一，他的《数学九章》概括了宋元时期中国传统数学的主要成就．由他提出的一种多项式简化算法称为秦九韶算法：它是一种将n次多项式的求值问题转化为n个一次式的算法．即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法．用秦九韶算法求多项式f（x）=4x5–x2+2，当x=3时的值时，需要进行的乘法运算和加法运算的次数分别为A．4，2B．5，2C．5，3D．6，22．用秦九韶算法计算多项式f（x）=2x6+5x5+6x4+23x3–8x2+10x–3，当x=2时，V3的值为A．9B．24C．71D．1343．二进制数101101（2）对应的十进制数是A．45B．44C．46D．474．k进制数3651（k），则k可能是A．2B．4C．6D．85．将十进制数17转化为二进制数为A．11110B．10101C．10011D．100016．二进制数110011（2）化为十进制数为A．51B．52C．25223D．250047．用秦九韶算法计算多项式f（x）=2x4–x3+3x2+7，在求x=3时对应的值时，v3的值为__________．8．用辗转相除法求1813和333的最大公约数时，需要做__________次除法．9．10101（2）转化为十进制数是__________．10．用秦九韶算法求多项式f（x）=7x3+3x2–5x+11在x=23时的值，在运算过程中下列数值不会出现的是A．164B．3767C．86652D．8516911．下列四个数中数值最大的是A．1111（2）B．16C．23（7）D．30（6）12．进位制是人们为了计数和运算方便而约定的计数系统，“满几进一”就是几进制，不同进制之间可以相互转化，例如把十进制的89转化为二进制，根据二进制数“满二进一”的原则，可以用2连续去除89得商，然后取余数，具体计算方法如下：把以上各步所得余数从下到上排列，得到89=1011001（2）这种算法叫做“除二取余法”，上述方法也可以推广为把十进制数化为k进制数的方法，称为“除k取余法”，那么用“除k取余法”把89化为七进制数为__________．学&科网13．将4034与10085的最大公约数化成五进制数．14．用秦九韶算法求多项式：f（x）=12+35x–8x2+79x3+6x4+5x5+3x6在x=–4的值．15．（1）用辗转相除法求5280和12155的最大公约数，并用更相减损术检验．（2）先将412（5）化成十进制的数，然后用“除k取余法”再化成七进制的数．16．试求出84，108，132和156这四个数的最大公约数．17．用秦九韶算法计算764()85321fxx