6)算法案例3.ppt
算法案例 算 法 案 例 辗转相除法和更相减损术辗转相除法和更相减损术 1、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求18和和30的最大公约数的最大公约数18和和30的最大公约数为的最大公约数为6 记记:(18 ,30 )=6求公因数的方法求公因数的方法:先用两个数公有的质因数连续去除先用两个数公有的质因数连续去除,一直除到所得的一直除到所得的商是互质数为止商是互质数为止,然后把所有的除数连乘起来然后把所有的除数连乘起来.2、求求8251和和6105的最大公约数的最大公约数 (8251 ,6105 )=?辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论：8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的公约数就可以了。的公约数就可以了。(8251 ,6105)=(6105 ,2146)第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462 +1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。(8251 ,6105)=(6105 ,2146)=(2146 ,1813)完整的过程完整的过程333=1482+37148=374+08251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148显然显然37是是148和和37的最大的最大公约数，也就是公约数，也就是8251和和6105的最大公约数的最大公约数 例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数思考思考1：从上面的两个例子可以概括出：从上面的两个例子可以概括出 计算的规则？计算的规则？S1：用大数除以小数：用大数除以小数S3：重复：重复S1，直到余数为，直到余数为0S2：除数除数变成变成被除数被除数，余数余数变成变成除数除数225=1351+90135=901+4590=452+0显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是停止的步骤，这实际上是一个循环结构。一个循环结构。m=n q r用程序框图表示出右边的过程用程序框图表示出右边的过程否r=m MOD nm=nn=rr=0?是S1：用大数除以小数：用大数除以小数S3：重复：重复S1，直到余数为，直到余数为0S2：除数除数变成变成被除数被除数，余数余数变成变成除数除数辗转相除法的程序框图辗转相除法的程序框图开始开始输入输入m,nr=m MOD nm=nn=rr=0?输出输出m结束结束是是否否INPUT“输入m,n”;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT“最大公约数是：”；mEND 九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子之数，以少减可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。多，更相减损，求其等也，以等数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是偶数。若任意给定两个正整数；判断他们是否都是偶数。若是，则用是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差与较小的以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。和差相等为止，则这个等数就是所求的最大公约数。例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减以大数减小数，并辗转相减 9863356335283528728721217141477所以，所以，98和和63的最大公约数等于的最大公约数等于7 练习练习2 2：用更相减损术求两个正数：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。(12)(12)3.3.辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较:（1 1）都是求最大公约数的方法，计算上辗）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别别当两个数字大小区别较大时计算次数的区别较明显。较明显。（2 2）从结果体现形式来看，辗转相除法体）从结果体现形式来看，辗转相除法体现结果是以相除余数为现结果是以相除余数为0 0则得到，而更相减损术则得到，而更相减损术则以减数与差相等而得到则以减数与差相等而得到.计算多项式计算多项式（）（）=当当x=5的值的值算法算法1：因为（）因为（）=所以（所以（5）=55555=3125625125255=3906算法算法2：（5）=5555510次的乘法运算次的乘法运算,5次的加法运算次的加法运算4次的乘法运算次的乘法运算,5次的加法运算次的加法运算=5（5555）=5（5（555 ）=5（5（5（55）=5（5（5（5（5）数书九章数书九章秦九韶算法秦九韶算法设设是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个这种将求一个n次多项式次多项式f（x）的值转化成求）的值转化成求n个一次多项式的值的个一次多项式的值的方法，称为方法，称为秦九韶算法秦九韶算法。例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：所以，当所以，当x=5时，多项式的值等于时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？开始开始输入输入n,an,xV=ani=n-1i=0?输出输出v结束结束输入输入aiV=v*x+aii=i-1是否例例3 已知一个已知一个4次多项式为次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解：解：将多项式变形：将多项式变形：按由里到外的顺序，依此计算一次多项式当按由里到外的顺序，依此计算一次多项式当x=5时的值：时的值：练习练习画出程序框图画出程序框图,表示用秦九韶算法求表示用秦九韶算法求5次多次多项式项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当当x=x0 (x0是任意实数是任意实数)时的值的过程时的值的过程,然后写出程序然后写出程序.否否程序框图程序框图开始开始输入输入a0,a1,a2,a3,a4,a5输入输入x0n5?n=1v=a5v=vx0+a5-nn=n+1输出输出v结束结束是是 INPUT a0,a1,a2,a3,a4,a5 INPUT x0 n=1 v=a5 WHILE n=5 v=vx0+a5-n n=n+1 WEND PRINT v END程序程序一、进位制一、进位制一、进位制一、进位制1、最常见的进位制是什么？2、除此之外还有哪些常见的进位制？请举例说明进位制是人们为了计数和运算方便而约定的记数系统。进位制是人们为了计数和运算方便而约定的记数系统。1、我们了解十进制吗？所谓的十进制，它是如何构成的？十进制由两个部分构成例如：3721其它进位制的数又是如何的呢？第二、它有“权位权位”，即从右往左从右往左为个位、十位、百位、千位等等。表示有：1个1，2个十，7个百即7个10的平方，3个千即3个10的立方第一、它有0、1、2、3、4、5、6、7、8、9十个数字；(用用10个数字来记数，称基数为个数字来记数，称基数为10)2 2、二进制二进制二进制是用二进制是用0 0、1 1两个数字来描述的。如两个数字来描述的。如1100111001等等（）二进制的表示方法（）二进制的表示方法区分的写法：区分的写法：1100111001（2 2）8 8进制呢？进制呢？k k进制呢？进制呢？a an na an-1n-1a an-2n-2a a2 2a a1(k)1(k)？如如73427342(8)(8)二、二进制与十进制的转换二、二进制与十进制的转换1、二进制数转化为十进制数、二进制数转化为十进制数例例1 将二进制数将二进制数110011(2)化成十进制数化成十进制数解：解：根据进位制的定义可知根据进位制的定义可知所以，所以，110011（2）=51。2、十进制转换为二进制、十进制转换为二进制 解：解：根据根据“逢二进一逢二进一”的原则，有的原则，有52 212（2（2（2（221）1）0）0）189126025124123022021120所以：所以：89=1011001（2）2（2（2（2321）0）0）12（2（242220）0）12（2523+2200）12624+230020892441442220222110112 51所以所以892（2（2（2（2 2 1）1）0）0）1例例2 把把89化为二进制数化为二进制数2、十进制转换为二进制、十进制转换为二进制例例2 把把89化为二进制数化为二进制数522212112244892222注意：注意：1.最后一步商为最后一步商为0，2.将上式各步所得的余数将上式各步所得的余数从下到上排列从下到上排列，得到：，得到：89=1011001（2）010余数余数01101例例3 把把89化为五进制数化为五进制数3、十进制转换为其它进制、十进制转换为其它进制解：解：根据根据除除k取余法取余法以以5作为除数，相应的除法算式为：作为除数，相应的除法算式为：所以，所以，89=324（5）。895175350423余数余数将k进制数a转换为十进制数b的程序a=anan-1 a3a2a1(k)=ank(n-1)+an-1k(n-2)+a3k2+a2k1+a1k0b=ab=a1 1k k0 0b=ab=a2 2k k1 1+b+bb=ab=a3 3k k2 2+b bb=ab=an nk kn-1 n-1+b+ba ai i=GET ai=GET aiGETGET函数用于取出函数用于取出a的右数第的右数第i i位数位数i=1i=1i=i+1i=i+1b=ab=ai ik ki-1i-1+b+bINPUT INPUT a,k,n,k,ni=1i=1b=0b=0WHILE i=nWHILE i=nt=GET ait=GET aib=t*k b=t*k(i-1)+b(i-1)+bi=i+1i=i+1WENDWENDPRINT bPRINT bENDEND例例.设计一个程序设计一个程序,把任意的十进制把任意的十进制a转化为转化为k进制数进制数b.开始开始输入输入a,k求求a 除以除以k的商的商q求求a 除以除以k的余数的余数r把得到的余数依次从右到左排列把得到的余数依次从右到左排列a=qq=0输出全部余数排列得到的进制数输出全部余数排列得到的进制数结束结束是是否否“，”；,练习：练习：完成下列进位制之间的转化：完成下列进位制之间的转化：（1）10231（4）=（10）；（2）235（7）=（10）；（3）137（10）=（6）；（4）1231（5）=（7）；（5）213（4）=（3）；（6）1010111（2）=（4）。30112434536211101113
