第89讲四种算法案例【知识要点】算法案例有辗转相除法、更相减损术、秦九韶算法和进位制.一、辗转相除法辗转相除法求两个数的最大公约数，其算法可以描述如下：①输入两个正整数和；②求余数：计算除以，将所得余数存放到变量中；③更新被除数和余数：=，=；④判断余数是否为0.若余数为0，则输出结果；否则转向第②步继续循环执行如此循环，直到得到结果为止.例：利用辗转相除法求6105与2146的最大公约数6105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0最后的除数37是6105与2146的最大公约数.二、更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术.在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.解题步骤：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数.例：用更相减损术求98与63的最大公约数98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以98和63的最大公约数是7.三、秦九韶算法秦九韶算法适用一般的多项式的求值问题.用秦九韶算法求一般多项式.当时的函数值，可把次多项式的求值问题转化成求个一次多项式的值的问题，即求=+=+=+……=+这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现.用秦九韶算法求一般多项式.当时的函数值，需要次乘法运算，次加法运算.四、进位制1、概念进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为，即可称进位制，简称进制.现在最常用的是十进制，通常使用10个阿拉伯数字0—9进行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.一般地，若是一个大于1的整数，那么以为基数的进制可以表示为：，而表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.2、进位制间的转换（1）非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：（2）把十进制数转换为进制数，一般利用“除取余法”.例：把89化为二进制数.所以注意：利用除取余法解答时，最后的余数是从下往上写，不要从上往下写.（3）非十进制之间的转换，先把它转换成十进制，再把十进制转换成其他进制.【方法讲评】算法案例一辗转相除法解题步骤1、输入两个正整数和；2、求余数：计算除以，将所得余数存放到变量中；3、更新被除数和余数：=，=；4、判断余数是否为0.若余数为0，则输出结果；否则转向第②步继续循环执行如此循环，直到得到结果为止.【例1】数的最大公约数是（）A．B．C．D．【点评】求三个数的最大公约数，可以先求其中两个数的最大公约数，再求另外两个数的最大公约数，再求这两个最大公约数的最大公约数.【反馈检测1】三个数390,455,546的最大公约数是（）A.65B.91C.26D.13算法案例二更相减损术解题步骤以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数.【例2】根据我国古代数学名著《九章算术》中的“更相减损术”．求得144，28的最大公约数为（）A．4B．2C．0D．14【解析】，所以最大公约数是4.【点评】本题就是利用更相减损术求的最大公约数，也可以利用辗转相除法求解.【反馈检测2】和的最大公约数是（）A．3B．9C．17D．51算法案例三秦九韶算法解题步骤把次多项式的求值问题转化成求个一次多项式的值的问题，即求=+=+=+……=+【例3】已知，应用秦九韶算法计算当时的值为.【点评】利用秦九韶算法要经过次乘法和次加法.在利用秦九韶算法计算时，必须把缺的项补充起来，缺的指数幂的项的系数为零即可，并按照降幂排列.【反馈检测3】用秦九韶算法计算多项式当时的值时，的结果为.A．B．C．D．算法案例四进位制解题步骤1、非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：；2、把...
