1.3　算法案例

　　学习目标：1.会用辗转相除法与更相减损术求两数的最大公约数．(重点、易混点)2.会用秦九韶算法求多项式的值．(重点)3.会在不同进位制间进行相互转化．(难点)

[自 主 预 习·探 新 知]

　　1．辗转相除法与更相减损术

　　(1)辗转相除法

　　①辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．

　　②所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．

　　(2)更相减损术

　　更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．

　　2．秦九韶算法

　　把一个n次多项式f(x)＝anxn＋an－1xn－1＋...＋a1x＋a0改写成如下形式：f(x)＝(...((anx＋an－1)x＋an－2)x＋...＋a1)x＋a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x＋an－2，v3＝v2x＋an－3，...，vn＝vn－1x＋a0，这种求n次多项式f(x)的值的方法叫秦九韶算法．

　　3．进位制

　　(1)进位制是人们为了计数和运算方便而约定的记数系统．"满 进一"就是 进制， 进制的基数是 .

(2)将 进制数化为十进制数的方法是：先把 进制数写成各位上的数字与