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

1、 算法 1、 兴趣导入（Topic-in）:有个小孩到楼下的小店买饮料。店主给他一瓶，然后小孩说没钱。店主生气地威胁说：“没钱找你妈妈去！”小孩被吓得瓶盖都掉地上了。捡起来一看：再来一瓶！于是把瓶盖给了店主，高高兴兴地走了2、 学前测试(Testing):1用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A1B2C3D4答案B解析29484342,84422，选B.2用更相减损术，求105与30的最大公约数时，需要做减法的次数是()A2 B3 C4 D5答案C解析1053075,753045,453015,301515.3930与868的最大公约数是_答案62解析9308681

2、628686214930与868的最大公约数为62.4、 把十进制数53转化为二进制数.解：53125124023122021120 110101（2）5、利用辗转相除法求3869与6497的最大公约数与最小公倍数。解：6497386912628386926281124126281241*214612411468731467320 所以3869与6497的最大公约数为73 最小公倍数为38696497/733443413、 知识讲解(Teaching)：1.辗转相除法例1 求两个正数a=204和b=85的最大公约数。分析：204与85两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根

3、据已有的知识即可求出最大公约数解：20485234显然204的最大公约数也必是85的约数，同样204与85的公约数也必是34的约数，所以204与85的最大公约数也是85与34的最大公约数。8534217341172+0则17为204与85的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若r00，则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r10，则r1为m，n的

4、最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；依次计算直至rn0，此时所得到的rn1即为所求的最大公约数。2.更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2 用更相减损术求91与49

5、的最大公约数.解：由于49不是偶数，把91和49以大数减小数，并辗转相减，即：914842 49427 42735 35728 28721 217141477所以，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的值，这样，我们只计算了四次乘法运算，五次加法运算.第二种做法与第一种做法相比，乘法的运算减少了，因

6、而能提高运算效率.对于计算机来说，做一次乘法运算所用的时间，比做一次加法运算所用的时间要多得多，计算机能更快的得到结果.4.进位制对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.电子计算机一般都使用二进制,下面我们来进行二进制与十进制之间的转化例1 把二进制数110011(2)化为十进制数.解:110011=1*25+1*24+0*23+1*24+0*22+1*21+1*

7、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取余法,还可以用下面的除法算式表示:8944221152122222220余数1001101把上式中的各步所得的余数从下到上排列即可得到89=1011001(2)上述方法也可以推广

8、为把十进制化为k进制数的算法,这种算法成为除k取余法.4、 强化练习(Training)一选择题（共16小题）1把77化成四进制数的末位数字为（）A4B3C2D1考点：排序问题与算法的多样性。专题：计算题。分析：利用“除k取余法”是将十进制数除以5，然后将商继续除以4，直到商为0，然后将依次所得的余数倒序排列即可得到答案解答：解：774=191194=4344=1014=01故77（10）=1031（4）末位数字为1故选D点评：本题考查的知识点是十进制与其它进制之间的转化，其中熟练掌握“除k取余法”的方法步骤是解答本题的关键2用秦九韶算法求多项式f（x）=x4+2x3+x23x1，当x=2时的

9、值，则 v3=（）A4B9C15D29考点：排序问题与算法的多样性。分析：由秦九韶算法的规则对多项式变形，求出，再代入x=2计算出它的值，选出正确选项解答：解：由秦九韶算法的规则f（x）=x4+2x3+x23x1=（x+2）x+1）x3）x1，v3=（x+2）x+1）x3又x=2，可得v3=（2+2）2+1）23=15故选C点评：本题考查秦九韶算法，解题的关键是理解秦九韶算法的原理，得出v3的表达式，秦九韶算法是求多项值的一个较简便易行的算法，在平时求多项式的值时加利用可以简单化计算3把67化为二进制数为（）A110000B1011110C1100001D1000011考点：排序问题与算法的多

10、样性。专题：计算题。分析：利用“除k取余法”是将十进制数除以2，然后将商继续除以2，直到商为0，然后将依次所得的余数倒序排列即可得到答案解答：解：672=331332=161162=8082=4042=2022=1012=01故67（10）=1000011（2）故选D点评：本题考查的知识点是十进制与其它进制之间的转化，其中熟练掌握“除k取余法”的方法步骤是解答本题的关键4用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时，需要做乘法和加法的次数分别是（）A6，6B5，6C5，5D6，5考点：排序问题与算法的多样性。专题：计算题。分析：把所给的多

11、项式写成关于x的一次函数的形式，依次写出，得到最后结果，从里到外进行运算，结果有6次乘法运算，有6次加法运算，本题也可以不分解，直接从最高次项的次数直接得到结果解答：解：f（x）=3x6+4x5+5x4+6x3+7x2+8x+1=（3x5+4x4+5x3+6x2+7x+8）x+1=（3x4+4x3+5x2+6x+7）x+8+1=（3x+4）x+5x+6x+7x+8x+1需要做6次加法运算，6次乘法运算，故选A点评：本题考查用秦九韶算法进行求多项式的值的运算，不是求具体的运算值而是要我们观察乘法和加法的运算次数，本题是一个基础题5使用秦九韶算法计算x=2时f（x）=6x6+4x52x4+5x37

12、x22x+5的值，所要进行的乘法和加法的次数分别为（）A6，3B6，6C21，3D21，6考点：排序问题与算法的多样性。专题：计算题。分析：根据秦九韶算法求多项式的规则变化其形式，把f（x）=6x6+4x52x4+5x37x22x+5等到价转化为（6x+5）x2）x+5）x7）x2）x+5，就能求出结果解答：解：f（x）=6x6+4x52x4+5x37x22x+5=（6x+5）x2）x+5）x7）x2）x+5需做加法与乘法的次数都是6次，故选B点评：本题考查算法的多样性，正确理解秦九韶算法求多项式的原理是解题的关键，本题是一个比较简单的题目，运算量也不大，只要细心就能够做对6把27化为二进制数

13、为（）A1011（2）B11011（2）C10110（2）D10111（2）考点：排序问题与算法的多样性。专题：计算题。分析：利用“除k取余法”是将十进制数除以2，然后将商继续除以2，直到商为0，然后将依次所得的余数倒序排列即可得到答案解答：解：272=131132=6162=3032=1112=01故27（10）=11011（2）故选B点评：本题考查的知识点是十进制与其它进制之间的转化，其中熟练掌握“除k取余法”的方法步骤是解答本题的关键7用秦九韶算法计算多项式f（x）=5x5+4x4+3x32x2x1在x=4时的值时，需要进行的乘法、加法的次数分别是（）A14，5B5，5C6，5D7，5考

14、点：排序问题与算法的多样性。专题：计算题。分析：由秦九韶算法的原理，可以把多项式f（x）=5x5+4x4+3x32x2x1变形计算出乘法与加法的运算次数解答：解：多项式f（x）=5x5+4x4+3x32x2x1=（5x+4）x+3）x2）x1）x1不难发现要经过5次乘法5次加法运算故需要做乘法和加法的次数分别为：5、5故选B点评：本题考查秦九韶算法，考查在用秦九韶算法解题时一共会进行多少次加法和乘法运算，是一个基础题，解题时注意最后加还是不加常数项，可以直接看出结果8二进制数11001001（2）对应的十进制数是（）A401B385C201D258考点：排序问题与算法的多样性。专题：计算题。分

15、析：根据二进制和十进制之间的互化原则，需要用二进制的最后一位乘以2的0次方，以此类推，写出一个代数式，得到结果解答：解：二进制数11001001（2）对应的十进制数是120+123+126+127=201故选C点评：本题考查二进制和十进制之间的互化，本题解题的关键是理解两者之间的关系，不仅是这两种进位制之间的互化，既是还有其他的互化也可以用类似方法求解9用秦九韶算法在计算f（x）=2x4+3x32x2+4x6时，要用到的乘法和加法的次数分别为（）A4，3B6，4C4，4D3，4考点：排序问题与算法的多样性。专题：计算题。分析：由秦九韶算法能够得到f（x）=2x4+3x32x2+4x6=（2x+

16、3）x2）x+4）x6，由此能够求出结果解答：解：f（x）=2x4+3x32x2+4x6=（2x+3）x2）x+4）x6，用到的乘法的次数为4次，用到的加法的次数为4次故选C点评：本题考查秦九韶算法的应用，是基础题解题时要认真审题，仔细解答10用秦九韶算法求多项式f（x）=1+2x+x23x3+2x4在x=1时的值，v2的结果是（）A4B1C5D6考点：排序问题与算法的多样性。专题：计算题。分析：本题考查秦九韶算法，考查在用秦九韶算法解题时进行的加法和乘法运算，是一个基础题，先计算v1=anx+an1；再计算v2=v1x+an2，即得解答：解：v1=2（1）3=5；v2=（5）（1）+1=6，

17、故选D点评：秦九韶算法的设计思想：一般地对于一个n次多项式f（x）=anxn+an1xn1+an2xn2+a1x+a0，首先改写成如下形式：f（x）=（anx+an1）x+an2）x+a1）x+a0，再计算最内层括号内一次多项式的值，即v1=anx+an1；然后由内向外逐层计算一多项式的值，即v2=v1x+an2，v3=v2x+an3，vn=vn1x+a011下列各数85（9）、210（6）、1000（4）、111111（2）中最大的数是（）A85（9）B210（6）C1000（4）D111111（2）考点：排序问题与算法的多样性。专题：计算题。分析：由题设条件，可以把这几个数化为十进制数，再

18、比较它们的大小，选出正确选项解答：解：85（9）=89+51=77；210（6）=236+16=78；1000（4）=143=64；111111（2）=125+124+123+122+121+120=32+16+8+4+2+1=63由上计算知最大的数是210（6），故选B点评：本题考查排序问题与算法的多样性，解题的关键是掌握住其它进位制数转化为十进制数的方法，统一进位制，再作比较12十进制数89化为二进制的数为（）A1001101（2）B1011001（2）C0011001（2）D1001001（2）考点：排序问题与算法的多样性。专题：计算题。分析：利用“除k取余法”是将十进制数除以2，然后将

19、商继续除以2，直到商为0，然后将依次所得的余数倒序排列即可得到答案解答：解：892=441442=220222=110112=5152=2122=1012=01故89（10）=1011001（2）故选B点评：本题考查的知识点是十进制与其它进制之间的转化，其中熟练掌握“除k取余法”的方法步骤是解答本题的关键13在下列各数中，最大的数是（）A85（9）B210（6）C1000（4）D11111（2）考点：排序问题与算法的多样性。专题：计算题。分析：欲找四个中最大的数，先将它们分别化成十进制数，后再比较它们的大小即可解答：解：85（9）=89+5=77；210（6）=262+16=78；1000（4

20、）=143=64；11111（2）=24+23+22+21+20=31故210（6）最大，故选B点评：本题考查的知识点是算法的概念，由n进制转化为十进制的方法，我们只要依次累加各位数字上的数该数位的权重，即可得到结果14把23化成二进制数是（）A00110B10111C10101D11101考点：排序问题与算法的多样性。专题：计算题。分析：利用“除k取余法”是将十进制数除以2，然后将商继续除以2，直到商为0，然后将依次所得的余数倒序排列即可得到答案解答：解：232=111112=5152=2122=1012=01故23（10）=10111（2）故选B点评：本题考查的知识点是十进制与其它进制之间

21、的转化，其中熟练掌握“除k取余法”的方法步骤是解答本题的关键二填空题（共11小题）15用秦九韶算法求多项式f（x）=12+35x8x2+79x3+6x4+5x5+3x6在x=4的值时，其中V1的值=7考点：排序问题与算法的多样性。专题：计算题。分析：首先把一个n次多项式f（x）写成（anx+an1）x+an2）x+a1）x+a0的形式，然后化简，求n次多项式f（x）的值就转化为求n个一次多项式的值，求出V3的值解答：解：把一个n次多项式f（x）=anxn+an1x（n1）+a1x+a0改写成如下形式：f（x）=anxn+an1x（n1）+a1x+a0=（anx（n1）+an1x（n2）+a1）

22、x+a0=（anx（n2）+an1x（n3）+a2）x+a1）x+a0=（anx+an1）x+an2）x+a1）x+a0求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1=anx+an1然后由内向外逐层计算一次多项式的值，即 v2=v1x+an2v3=v2x+an3vn=vn1x+a0这样，求n次多项式f（x）的值就转化为求n个一次多项式的值V1的值为7；故答案为：7点评：本题考查通过程序框图解决实际问题，把实际问题通过数学上的算法，写成程序，然后求解，属于中档题16把5进制的数412（5）化为7进制是212（7）考点：排序问题与算法的多样性。专题：计算题。分析：先把5进制的数412

23、（5）化为十进制数再变为七进制数，用除k取余法解答：解：412（5）=250+151+452=2+5+425=107107=270+171+27 2把5进制的数412（5）化为7进制是212（7）故答案为：212（7）点评：本题考查进位制之间的换算，熟练掌握进行制的变化规律是正确解题的要诀17用秦九韶算法计算多项式f（x）=8x4+5x3+3x2+2x+1在x=2时的值时，v2=45考点：排序问题与算法的多样性。专题：计算题。分析：首先把一个n次多项式f（x）写成（anx+a n1）x+an2）x+a1）x+a0的形式，然后化简，求n次多项式f（x）的值就转化为求n个一次多项式的值，求出V2的

24、值解答：解：f（x）=8x4+5x3+3x2+2x+1=（8x+5）x+3）x+2）x+1v0=8；v1=82+5=21；v2=212+3=45故答案为：45点评：本题考查秦九韶算法与算法的多样性，解答本题，关键是了解秦九韶算法的规则，求出v2的表达式18用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时，至多需要做乘法和加法的次数分别是6和6考点：排序问题与算法的多样性。专题：规律型。分析：把所给的多项式写成关于x的一次函数的形式，依次写出，得到最后结果，从里到外进行运算，结果有6次乘法运算，有6次加法运算，本题也可以不分解，直接从最高次项的

25、次数直接得到结果解答：解：f（x）=3x6+4x5+5x4+6x3+7x2+8x+1=（3x+4）x+5x+6x+7x+8x+1需要做6次加法运算，6次乘法运算，故答案为6，6点评：本题考查秦九韶算法，考查在用秦九韶算法解题时一共会进行多少次加法和乘法运算，是一个基础题，解题时注意最后加还是不加常数项，可以直接看出结果19用秦九韶算法求多项式f（x）=5x5+2x4+3.5x32.6x2+1.7x0.8当x=5时的值的过程中v3=689.9考点：排序问题与算法的多样性。专题：计算题。分析：由秦九韶算法的规则将多项式f（x）=5x5+2x4+3.5x32.6x2+1.7x0.8这形得出v3，再代

26、入x=5求值解答：解：f（x）=5x5+2x4+3.5x32.6x2+1.7x0.8=（5x+2）x+3.5）x2.6）x+1.7）x0.8v3=（5x+2）x+3.5）x2.6将x=5代入得v3=（55+2）5+3.5）52.6=689.9故答案为689.9点评：本题考查排序问题与算法的多样性，解答本题，关键是了解秦九韶算法的规则，求出v3的表达式20完成下列进位制之间的转化：1234=34102（4）考点：排序问题与算法的多样性。分析：将1235依次除以4，求余数，最后把余数从下到上连接起来即为4进制数解答：解：由题意，1234除以4，商为308，余数为2，308除以4，商为77，余数为0

27、，77除以4，商为19，余数为1，19除以4，商为4，余数为3，将余数从下到上连起来，即34102故答案为：34102点评：本题考查算法的概念，以及进位制的运算，属于基础题基础题21进制转化：403（6）=223（8）考点：排序问题与算法的多样性；算法的概念。专题：计算题。分析：首先对403（6）化为10进制，然后依次除以8，求余数，最后把余数从下到上连接起来即为8进制数解答：解：先转化为10进制为：4*36+0*6+3=147 147/8=18318/8=222/8=02将余数从下到上连起来，即223故答案为：223点评：本题考查算法的概念，以及进位制的运算通过把3进制转化为10进制，再把1

28、0进制转化为8进制其中10进制是一个过渡22完成右边进制的转化：1011（2）=11（10）=13（8）考点：排序问题与算法的多样性。专题：计算题。分析：若二进制的数有n位，那么换成十进制，等于每一个数位上的数乘以2的（n1）方，再相加即可；而要将十进制的数转化为8进制，而要采用除8求余法；解答：解：（1011）2=123+022+12+1=11118=13，18=01，故1011（2）=11（10）=13（8），故答案为11，13点评：本题考查的知识点是不同进制之间的转换，熟练掌握K进制与十进制之间的转换方法“累加权重法”和“除k求余法”是解答本题的关键5、 反思总结(Thinking)： 堂堂清落地训练 （5-10分钟的测试卷，坚持堂堂清，学习很爽心）1将多项式x3+2x2+x1用秦九韶算法求值时，其表达式应写成（x+2）x+1）x1考点：排序问题与算法的多样性。专题：数学模型法。分析：利用秦九韶算法解题，需要一层一层的提出x最后整理出关于x的一次函数的形式，提两次x得到结果解答：解：x3+2x2+x1=（x2+2x+1）x1=（x+2）x+1）x1，故答案为：（x+2）x+1）x1点评：本题考查排序问题与算法的多样性，本题解题的关键是整理出一系列的x的一次函数的形式，本题是一个基础题2写出将8进制数23760转化为7进制数的过程考点：排序问题与算法的多样性。专题：