PAGEPAGE4《算法案例》学案（约2课时）辗转相除法1．知识构建求最大公约数算法案例更相减损术求多项式的值：秦九韶算法（转化为一次多项式的值）进位制2．辗转相除法（1）辗转相除法：该算法又称欧几里得算法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，此时除数就是所求两正整数的最大公约数。（2）算法：第一步，输入两个正整数.第二步，判断的大小,让表示较大的数,表示较小的数.第三步，计算除以的余数.第四步，让.第五步，如果,则的最大公约数等于;否则返回第三步.（3）程序框图：参考必修三课本以及下面（4）的程序。（4）程序程序1：INPUT“m,n=”;m,nIFm<nTHENt=mm=nn=tENDIFDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND程序2：NPUT“m,n=”;m,nIFm<nTHENt=mm=nn=tENDIFr=1WHILEr<>0r=mMODnm=nn=rWENDPRINTmEND【例】辗转相除法用求与的最大公约数.解：第一步,第二步,第三步,因此,是与的最大公约数.4.更相减损术(1)更相减损术:《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”具体做法见下面的算法。(2)算法:第一步，任意给定两个正整数,判断它们是否都是偶数,若是,用约简之；若不是,执行第二步。第二步，以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的数相等为止.则这个数(等数)或这个数与约简数的乘积就是所求的最大公约数。(3)程序框图为:略(4)程序为:INPUT“m,n=”;m,nIFm<nTHENt=mm=nn=tENDIFk=0WHILE(mMOD2=0)AND(nMOD2=0)m=m/2n=n/2k=k+1WENDd=m-nWHILEd<>nIFd>nTHENm=dELSEm=nn=dENDIFd=m-nWENDd=2^k*dPRINTdEND【例】用更相减损术求98与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，并辗转相减：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98和63的最大公约数等于7。【例】用更相减损术求260和104的最大公约数。解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减：65-26=3939-26=1326-13=13所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52【例】用辗转相除法和更相减损术求三个数的最大公约数.解：辗转相除法,则与的最大公约数为又,,则与的最大公约数为因此,三个数的最大公约数为.更相减损术,,则与的最大公约数为又,,则与的最大公约数为因此,三个数的最大公约数为.【练习】1.用辗转相除法求和的最大公约数.(答案:)2.用更相减损术求和的最大公约数.(答案:)3.求的最大公约数.(答案:)5．秦九韶算法（1）秦九韶算法：求多项式的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求个一次多项式的值,共进行次乘法运算和次加法运算。（2）改写多项式:设,,,.【例】已知一个次多项式为,用秦九韶算法求这个多项式当时的值.解:根据秦九韶算法,把多项式改写成如下形式:按照从内到外的顺序,一次计算一次多项式当时的值:,,,,所以,当时,多项式的值为点评:如果多项式函数中有缺项的话，要以系数为的项补齐后再计算。【练习】1.已知多项式函数,求.（答案：）2.当时,求多项式的值.（答案：）3.求多项式当时的值.（答案：）6．进位制（1）进制数化为十进制数的计算公式为:=【例】把二进制数化为十进制数.解：【例】将八进制数化为十进制数。解：（2）十进制数化为进制数的方法：（除取余法）用连续去除该十进制数或所得的商，直到商数为零为止，然后把每次所得的余数倒着排成一个数，就是相应的进数。【例】把十进制数转化为二进制数。解：所以【例】把十进制数化为三进制数。解：