第一节算法案例学习目标:理解掌握辗转相除法、更相减损之术、秦九韶算法等中国古代数学中的算法案例，并学会不同进位制间的相互转化学习过程：一、最大公约数问题问题一：求（1）18，30（2）104，256的最大公约数，我们一般会用什么方法和步骤来求两个数的最大公约数？问题二：求（3）1086，975（4）8251，6105的最大公约数，数据较大时我们要怎么求它们的最大公约数？方法一：辗转相除法例1.求两个正数8251和6105的最大公约数。（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）解：8251＝6105×1＋2146显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0则37为8251与6105的最大公约数。方法二：更相减损之术例2.用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98与63的最大公约数是7。练习：（1）225；135（2）98；196（3）72；168（4）153；119二、秦九韶算法案例问题三：怎样求多项式当时的值呢？当时的值呢？方法一：直接代入计算方法二:秦九韶算法例3.多项式当时的值呢？解：对于f(x)=x5+x4+x3+x2+x+1,我们可以对式子进行剥洋葱式的拆分，有f(x)=（x4+x3+x2+x+1）x+1=((x3+x2+x+1)x+1)x+1=(((x2+x+1)x+1)x+1)x+1=((((x+1)x+1)x+1)x+1)x+1所以x=5时，则f(x)=((((5+1)*5+1)*5+1)*5+1)*5+1=3906问题四：对于上述例子，用一般方法一共要进行几次乘法和加法运算，用秦九韶算法呢？秦九韶计算多项式的方法：如何应用秦九韶算法完成一般的多项式f(x)=anxn+an-1xn-1+….+a1x+a0求值问题？f(x)=anxn+an-1xn-1+….+a1x+a0=(...(anx+an-1)x+an-2)x+...+a1)x+a0求多项式的值时，首先计算最内层括号内依次多项式的值，即v1=anx+an-1然后由内向外逐层计算一次多项式的值，即v2=v1x+an-2v3=v2x+an-3......vn=vn-1x+a0这样，把n次多项式的求值问题转化成求n个一次多项式的值的问题练习：已知一个五次多项式f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求当x=5时多项式的值。三、进位制问题五：百位数字为a,十位数字为b，个位数字为c的数用多项式怎么表示？给班级的合影照有一张大小为2.15M的，它有多少K，有多少字节？10000秒是多少小时多少分零多少秒？进位制的概念：进位制是人们为了计数和运算方便而约定的记数系统,约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；等等，也就是说，“满几进一”就是几进制，几进制的基数就是几。内容一：其他进制数向十进制转化例4.十进制数4528表示的数可以写成4×103+5×102+2×101+8×100，依此类比，二进制数110011(2),八进制数7342(8)分别可以写成什么式子？解：110011(2)=1×25+1×24+0×23+0×22+1×21+1×207342(8)=7×83+3×82+4×81+2×80.总结：一般地，如何将k进制数anan-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？内容二：十进制数转化为其他进制例5.十进制数89化为二进制数是什么数？解：除k取余法：这种方法也可以推广为把十进制化为k进制数的算法,这种算法称为除k取余法.练习：十进制数191化为五进制数是什么数？趣味思考题：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？算法案例课程练习1.840和1764的最大公约数是（）A.84B.12C.168D.2522.用秦九韶算法计算多项式当时的值时，需要做乘法和加法的次数分别是（）A.6,6B.1