高二年级数学,算法(学生版)

———————————————————————————————————————————————————1算法一、兴趣导入（Topic-in）:有个小孩到楼下的小店买饮料。店主给他一瓶，然后小孩说没钱。店主生气地威胁说：“没钱找你妈妈去！”小孩被吓得瓶盖都掉地上了。捡起来一看：再来一瓶！于是把瓶盖给了店主，高高兴兴地走了……二、学前测试(Testing):1．用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A．1B．2C．3D．42．用更相减损术，求105与30的最大公约数时，需要做减法的次数是()A．2B．3C．4D．53．930与868的最大公约数是________．4、把十进制数53转化为二进制数.5、利用辗转相除法求3869与6497的最大公约数与最小公倍数。———————————————————————————————————————————————————2三、知识讲解(Teaching)：1.辗转相除法例1求两个正数a=204和b=85的最大公约数。分析：204与85两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数解：204＝85×2＋34显然204的最大公约数也必是85的约数，同样204与85的公约数也必是34的约数，所以204与85的最大公约数也是85与34的最大公约数。85＝34×2＋1734＝117×2+0则17为204与85的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；……依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。2.更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。———————————————————————————————————————————————————3例2用更相减损术求91与49的最大公约数.解：由于49不是偶数，把91和49以大数减小数，并辗转相减，即：91－48＝4249－42＝742－7＝3535－7＝2828－7＝2121－7＝1414－7＝7所以，91与49的最大公约数是7。3.秦九韶算法材料：求多项式f(x)=x5+x4+x3+x2+x+1当x=5时，有两种方法.第一种方法是把5代入多项式f(x),计算各项的值，然后把它们加起来.这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算.第二种做法是我们先计算x2的值，然后再一次计算x2x,(x2x)x，((x2x)x)x的值，这样，我们只计算了四次乘法运算，五次加法运算.第二种做法与第一种做法相比，乘法的运算减少了，因而能提高运算效率.对于计算机来说，做一次乘法运算所用的时间，比做一次加法运算所用的时间要多得多，，计算机能更快的得到结果.4.进位制对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.电子计算机一般都使用二进制,下面我们来进行二进制与十进制之间的转化例1把二进制数110011(2)化为十进制数.———————————————————————————————————————————————————4解:110011=1*25+1*24+0*23+1*24+0*22+1*21+1*20=32+16+2+1=51例2把89化为二进制数.解:根据二进制数满二进一的原则,可以用2连续去除89或所得商,然后去余数.具体的计算方法如下:89=2*44+144=2*22+022=2*11+011=2*5+15=2*2+1所以:89=2*(2*(2*(2*(2*2+1)+1)+0)+0)+1=1*26+0*25+1*24+1*23+0*22+0*21+1*20=1011001(2)这种算法叫做除2取余法,还可以用下面的除法算式表示:把上式中的各步所得的余数从下到上排列即可得到89=1011001(2)上述方法也可以推广为把十进制化为k进制数的算法,这种算法成为除k取余法.四、强化练习(Training)8944221152122222220余数1001101———————————————————————————————————————————————————5一．选择题（共16小题）1．把77化成四进制数的末位数字为（）A．4B．3C．2D．12．用秦九韶算法求多项式f（x）=x4+2x3+x2﹣3x﹣1，当x=2时的值，则v3=（）A．4B．9C．15D．293．把67化为二进制数为（）A．110000B．1011110C．1100001D．10000114．用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时，需要做乘法和加法的次数分别是（）A．6，6B．5，6C．5，5D．6，55．使用秦九韶算法计算x=2时f（x）=6x6+4x5﹣2x4+5x3﹣7x2﹣2x+5的值，所要进行的乘法和加法的次数分别为（）A．6，3B．6，6C．21，3D．21，66．把27化为二进制数为（）A．1011（2）B．11011（2）C．10110（2）D．10111（2）7．用秦九韶算法计算多项式f（x）=5x5+4x4+3x3﹣2x2﹣x﹣1在x=﹣4时的值时，需要进行的乘法、加法的次数分别是（）A．14，5B．5，5C．6，5D．7，58．二进制数11001001（2）对应的十进制数是（）A．401B．385C．201D．2589．用秦九韶算法在计算f（x）=2x4+3x3﹣2x2+4x﹣6时，要用到的乘法和加法的次数分别为（）A．4，3B．6，4C．4，4D．3，410．用秦九韶算法求多项式f（x）=1+2x+x2﹣3x3+2x4在x=﹣1时的值，v2的结果是（）A．﹣4B．﹣1C．5D．611．下列各数85（9）、210（6）、1000（4）、111111（2）中最大的数是（）A．85（9）B．210（6）C．1000（4）D．111111（2）12．十进制数89化为二进制的数为（）A．1001101（2）B．1011001（2）C．0011001（2）D．1001001（2）———————————————————————————————————————————————————613．在下列各数中，最大的数是（）A．85（9）B．210（6）C．1000（4）D．11111（2）14．把23化成二进制数是（）A．00110B．10111C．10101D．11101二．填空题（共11小题）15．用秦九韶算法求多项式f（x）=12+35x﹣8x2+79x3+6x4+5x5+3x6在x=﹣4的值时，其中V1的值=．16．把5进制的数412（5）化为7进制是．17．用秦九韶算法计算多项式f（x）=8x4+5x3+3x2+2x+1在x=2时的值时，v2=．18．用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时，至多需要做乘法和加法的次数分别是和．19．用秦九韶算法求多项式f（x）=5x5+2x4+3.5x3﹣2.6x2+1.7x﹣0.8当x=5时的值的过程中v3=．20．完成下列进位制之间的转化：1234=（4）．21．进制转化：403（6）=（8）．22.完成右边进制的转化：1011（2）=（10）=（8）五、反思总结(Thinking)：堂堂清落地训练———————————————————————————————————————————————————7（5-10分钟的测试卷，坚持堂堂清，学习很爽心）1．将多项式x3+2x2+x﹣1用秦九韶算法求值时，其表达式应写成．2．写出将8进制数23760转化为7进制数的过程．3．已知一个5次多项式为f（x）=4x5﹣3x3+2x2+5x+1，用秦九韶算法求这个多项式当x=2时的值．4．(1)用辗转相除法求840与1764的最大公约数．(2)用更相减损术求459与357的最大公约数．5.求两个正数8251和6105的最大公约数。———————————————————————————————————————————————————86、用更相减损术求98与63的最大公约数.7、利用秦九韶算法求多项式1352.75.38123)(23456xxxxxxxf在6x的值，写出详细步骤。