【学案导学设计】学年高中数学 1.3 算法案例课堂教学课件1 新人教A必修3

第一章算法初步

1.3算法案例35915[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？〖创设情景，揭示课题〗183023∴18和30的最大公约数是2×3=6.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.案例1辗转相除法与更相减损术〖创设情景，揭示课题〗[问题2]:我们都是利用找公约数的方法来求最大公约数，如果两个数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数?〖研探新知〗1.辗转相除法:例1求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。1.辗转相除法:例1求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。第一步,给定两个正数m,n第二步,计算m除以n所得到余数r第三步,m=n,n=r第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步辗转相除法求最大公约数算法：思考：需不需要比较m，n的大小不需要否开始输入两个正数m,nr=mMODnr=0?输出m结束m=nn=r是程序框图练习1：利用辗转相除法求两数4081与20723的最大公约数.(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.2.更相减损术: 我国早期也有解决求最大公约数问题的算法，就是更相减损术。 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2用更相减损术求98与63的最大公约数. 解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98与63的最大公约数是7。练习2：用更相减损术求两个正数84与72的最大公约数。(12)辗转相除法法与更相减减损术的比比较:（1）都是求最最大公约数数的方法，，计算上辗辗转相除法法以除法为为主，更相相减损术以以减法为主主;计算次数上上辗转相除除法计算次次数相对较较少，特别别当两个数数字大小区区别较大时时计算次数数的区别较较明显。（2）从结果体体现形式来来看，辗转转相除法体体现结果是是以相除余余数为0则得到，而而更相减损损术则以减减数与差相相等而得到到.〖教学设计〗[问题1]设计求多项项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算算法,并写出程序序.x=5f=2＊x^5-5＊x^4-4＊x^3+3＊x^2-6＊x+7PRINTfEND程序点评:上述算法一一共做了15次乘法运算算,5次加法运算算.优点是简单单,易懂;缺点是不通通用,不能解决任任意多项式式求值问题题,而且计算效效率不高.n次多项式至至多n(n+1)/2次乘法运算算和n次加法运算算案例2秦九韶算法法这析计算上上述多项式式的值,一共需要9次乘法运算算,5次加法运算算.[问题2]有没有更高高效的算法法?分析:计算x的幂时,可以利用前前面的计算算结果,以减少计算算量,即先计算x2,然后依次计计算的值.第二种做法与与第一种做法法相比,乘法的运算次次数减少了,因而能提高运运算效率.而且对于计算算机来说,做一次乘法所所需的运算时时间比做一次次加法要长得得多,因此第二种做做法能更快地地得到结果.[问题3]能否探索更好好的算法,来解决任意多多项式的求值值问题?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=((2x3-5x2-4x+3)x-6)x+7=(((2x2-5x-4)x+3)x-6)x+7=((((2x-5)x-4)x+3)x-6)x+7v0=2v1=v0x-5=2××5-5=5v2=v1x-4=5××5-4=21v3=v2x+3=21×5+3=108v4=v3x-6=108×5-6=534v5=v4x+7=534×5+7=2677所以,当x=5时,多项式的值是是2677.这种求多项式式值的方法就就叫秦九韶算法.变为求几个一一次式的值几个乘法几个加法？秦九韶《数书九章》.2-50-43-60x=5105252512512160560830403034所以,当x=5时,多项式的值是是15170.练习:用秦九韶算法法求多项式f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.解:原多项式先化化为:f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0列表21517015170注意:n次多项式有n+1项,因此缺少哪一一项应将其系系数补0.f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.我们可以改写写成如下形式式:f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.求多项式的值值时,首先计算最内内层括号内一一次多项式的的值,即v1=anx+an-1,然后由内向外外逐层计算一一次多项式的的值,即一般地,对于一个n次多项式v2=v1x+an-2,v3=v2x+an-3,……,vn=vn-1x+a0.这样,求n次多项式f(x)的值就转化为为求n个一次多项式式的值.这种算法称为为秦九韶算法.点评:秦九韶算法是是求一元多项项式的值的一一种方法.它的特点是:把求一个n次多项式的值值转化为求n个一次多项式式的值,通过这种转化化,把运算的次数数由至多n(n+1)/2次乘法运算和和n次加法运算,减少为n次乘法运算和和n次加法法运算算,大大提提高了了运算算效率率.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3,…………,vn=vn-1x+a0.观察上上述秦秦九韶韶算法法中的的n个一次次式,可见vk的计算算要用用到vk-1的值.若令v0=an,得v0=an,vK=vK-1x+an-k(k=1,2,……,n）这是一一个在在秦九九韶算算法中中反复复执行行的步步骤,因此可可用循循环结结构来来实现现.第一步步,输入多多项式式次数数n、最高高次项项的系系数an和x的值第二步步,将v的值初初始化化为an，将i的值初初始化化为n-1第三步步,输入i次项的的系数数ai第四步步,v=vx+ai,i=i-1第五步步,若i>=0,则返回回第三三步，，否则则输出出v算法分分析：：否程序框框图开始输入n,an,x的值输入aii>=0?i=n-1v=anv=vx+aii=i-1输出v结束是[问题1]我们常常见的的数字字都是是十进进制的的,但是并并不是是生活活中的的每一一种数数字都都是十十进制制的.比如时时间和和角度度的单单位用用六十十进位位制,电子计计算机机用的的是二二进制制.那么什什么是是进位位制?不同的的进位位制之之间又又有什什么联联系呢呢?进位位制制是是人人们们为为了了计计数数和和运运算算的的方方便便而而约约定定的的一一种种记记数数系系统统，，约约定定满满二二进进一一,就是是二二进进制制;满十十进进一一,就是是十十进进制制;满十十六六进进一一,就是是十十六六进进制制;等等等.“满满几几进进一一””,就是是几几进进制制,几进进制制的的基数数就是是几几.可使使用用数数字字符符号号的的个个数数称称为为基基数数.基数数都都是是大大于于1的整整数数.案例例3进位位制制如二二进进制制可可使使用用的的数数字字有有0和1,基数数是是2;十进进制制可可使使用用的的数数字字有有0,1,2,……,8,9等十十个个数数字字,基数数是是10;十六六进进制制可可使使用用的的数数字字或或符符号号有有0~9等10个数数字字以以及及A~F等6个字字母母(规定定字字母母A~F对应10~15),十六进制制的基数数是16.注意:为了区分分不同的的进位制制,常在数字字的右下下脚标明明基数,.如111001(2)表示二进进制数,34(5)表示5进制数.十进制数数一般不不标注基基数.[问题2]十进制数数3721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它可可以写成成下面的的形式:3721=3××103+7×102+2×101+1×100.想一想二二进制数数1011(2)可以类似似的写成成什么形形式?1011(2)=1×23+0×22+1×21+1×20.同理:3421(5)=3×53+4×52+2×51+1×50.C7A16(16)=12××164+7×163+10××162+1×161+6×160.一般地,若k是一个大大于1的整数,那么以k为基数的的k进制数可可以表示示为一串串数字连连写在一一起的形形式anan-1…a1a0(k)(0<an<k,0≤an-1,…,a1,a0<k)意思是:(1)第一个数数字an不能等于于0;(2)每一个数数字an,an-1,…,a1,a0都须小于于k.k进制的数数也可以以表示成成不同位位上数字字与基数数k的幂的乘乘积之和和的形式式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.注意这是是一个n+1位数.[问题3]二进制只用0和1两个数字,这正好与电路路的通和断两两种状态相对对应,因此计算机内部都都使用二进制制.计算机在进行行数的运算时时,先把接受到的的数转化成二二进制数进行行运算,再把运算结果果转化为十进进制数输出.那么二进制数数与十进制数数之间是如何何转化的呢?例3:把二进制数110011(2)化为十进制数数.分析:先把二进制数数写成不同位位上数字与2的幂的乘积之之和的形式,再按照十进制制数的运算规规则计算出结结果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.k进制数转化为为十进制数的的方法先把k进制的数表示示成不同位上上数字与基数数k的幂的乘积之之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十进制制数的运算规规则计算出结结果.例4:把89化为二进制的的数.分析:把89化为二进制的的数,需想办法将89先写成如下形形式89=an×2n+an-1×2n-1+…+a1×21+a0×20.89=44××2+1,44=22××2+0,22=11××2+0,11=5×2+1,5=2×2+1,89=44××2+1,=(22×2+0)×2+1=((11××2+0)××2+0)××2+1=(((5××2+1)××2+0)××2+0)××2+1=((((2×2+1)×2+1)×2+0)×2+0)×2+1=(((((1×2)+0)×2+1)×2+1)×2+0)×2+0)×2+1