《第一节算法案例.doc》由会员分享，可在线阅读，更多相关《第一节算法案例.doc（4页珍藏版）》请在金锄头文库上搜索。
1、第一节 算法案例学习目标:理解掌握辗转相除法、更相减损之术、秦九韶算法等中国古代数学中的算法案例，并学会不同进位制间的相互转化学习过程：一、最大公约数问题问题一：求（1）18，30（2）104，256的最大公约数，我们一般会用什么方法和步骤来求两个数的最大公约数？问题二：求（3）1086，975（4）8251， 6105的最大公约数，数据较大时我们要怎么求它们的最大公约数？方法一：辗转相除法例1.求两个正数8251和6105的最大公约数。（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）解：8251610512146显然825
2、1的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。6105214621813 21461813133318133335148 333148237 1483740则37为8251与6105的最大公约数。方法二：更相减损之术例2.用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：986335633528 35287 28721 21714 1477所以，98与63的最大公约数是7。练习：（1）225；135 （2）98；196 （3）72；
3、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问题四：对于上述例子，用一般方法一共要进行几次乘法和加法运算，用秦九韶算法呢？秦九韶计算多项式的方法：如何应
4、用秦九韶算法完成一般的多项式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-2 v3=v2x+an-3 . vn=vn-1x+a0这样，把n次多项式的求值问题转化成求n个一次多项式的值的问题练习：已知一个五次多项式f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8用秦九韶算法求当x=5时多项式的值。三、进位制问题
5、五：百位数字为a,十位数字为b，个位数字为c的数用多项式怎么表示？给班级的合影照有一张大小为2.15M的，它有多少K，有多少字节？10000秒是多少小时多少分零多少秒？进位制的概念：进位制是人们为了计数和运算方便而约定的记数系统,约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；等等，也就是说，“满几进一”就是几进制，几进制的基数就是几。内容一：其他进制数向十进制转化例4.十进制数4528表示的数可以写成4103+5102+2101+8100，依此类比，二进制数110011(2),八进制数7342(8)分别可以写成什么式子？解：110011(2)=125+124+023
6、+022+121+1207342(8)=783+382+481+280.总结：一般地，如何将k进制数anan-1a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？内容二：十进制数转化为其他进制例5.十进制数89化为二进制数是什么数？解： 除k取余法： 这种方法也可以推广为把十进制化为k进制数的算法,这种算法称为除k取余法.练习：十进制数191化为五进制数是什么数？趣味思考题：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？算法案例课程练习1.84
7、0和1764的最大公约数是（ ）A.84 B.12 C.168 D.2522.用秦九韶算法计算多项式当时的值时，需要做乘法和加法的次数分别是（ ）A.6 , 6 B.10 , 6 C.5 , 6 D.6 , 53.把88化为五进制数是（ ）A.3245 B.3235 C.2335 D.33254.用辗转相除法求72与120的最大公约数时，需要做除法次数为( )A.4 B.3 C.5 D.65.使用秦九韶算法求在时的值可减少运算次数，做加法和乘法的次数分别为（ ）A.n,n B. C. D.6.45和150的最大公约数和最小公倍数分别是( )A.5,150 B.15,450 C.450,15 D.15,1507.二进制数101 110（2）转化为八进制数为( )A.45（8） B.56（8） C.67（8） D.78（8）8.用秦九韶算法求多项式在x=-1.3的值时，令；时，的值为（）A.-9.8205 B.14.25 C.-22.445D.30.97859.下列各数中最小的是( )A111111(2) B210(6) C1000(4) D81(8)10.七进制数中各个数位上的数字只能是_中的一个11.三个数72,120,168的最大公约数是_12.现有长度为2.4米和5.6米两种规格的钢筋若干，要焊接一批正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？
