版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法事例一.【课标要求】经过阅读中国古代数学中的算法事例,领会中国古代数学对世界数学发展的贡献。二.【命题走向】算法是高中数学新课程中的新增内容,本讲的重点是几种重要的算法事例思想,复习时重算法的思想轻算法和程序的结构。展望2010年高考队本讲的观察是:以选择题或填空题的形式出现,分值在5分左右,观察的热门是算法实例和传统数学知识的联合题目三.【重点精讲】1.求最大条约数(1)短除法求两个正整数的最大条约数的步骤:先用两个数公有的质因数连续去除,向来除到所得的商是两个互质数为止,而后把全部的除数连乘起来2)穷举法(也叫列举法)穷举法求两个正整数的最大条约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到条约数立刻中止列举,获得的条约数即是最大条约数3)展转相除法展转相除法求两个数的最大条约数,其算法能够描绘以下:①输入两个正整数m和②求余数r:计算m除以n,将所得余数寄存到变量r中;③更新被除数和余数:m=n,n=r;④判断余数r能否为0。若余数为0,则输出结果;不然转向第②步持续循环履行这样循环,直到获得结果为止。
n;4)更相减损术我国初期也有解决求最大条约数问题的算法,就是更相减损术。在《九章算术》中记录了更相减损术求最大条约数的步骤:可半者半之,不行半者,副置分母?子之数,以少减多,更相减损,求其等也,以等数约之步骤:Ⅰ.随意给出两个正数;判断它们能否都是偶数。假如,用2约简;若不是,履行第二步。Ⅱ.以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。持续这操作,直到所得的数相等为止,则这个数(等数)就是所求的最大条约数。2.秦九韶算法秦九韶算法的一般规则:秦九韶算法合用一般的多项式f(x)=anxn+an-1xn-1+.+a1x+a0的求值问题。用秦九韶算法求一般多项式f(x)=anxn+an-1xn-1+.+a1x+a0当x=x0时的函数值,可把n次多项式的求值问题转变成求n个一次多项式的值的问题,即求v0=anv1=anx+an-1v2=v1x+an-2v3=v2x+an-3..vn=vn-1x+a0察看秦九韶算法的数学模型,计算vk时要用到vk-1的值,若令v0=an。我们能够获得下边的递推公式:v0=anvk=vk-1+an-k(k=1,2,n)这是一个在秦九韶算法中频频履行的步骤,能够用循环结构来实现排序排序的算法好多,课本主要介绍里两种排序方法:直接插入排序和冒泡排序(1)直接插入排序在平时生活中,常常遇到这样一类排序问题:把新的数据插入到已经排好次序的数据列中。比如:一组从小到大排好次序的数据列{1,3,5,7,9,11,13},往常称之为有序列,我们用序号1,2,3,表示数据的地点,欲把一个新的数据8插入到上述序列中。达成这个工作要考虑两个问题:(1)确立数据“8”在原有序列中应当据有的地点序号。数据“8”所处的地点应知足小于或等于原有序列右侧全部的数据,大于其左侧地点上全部的数据。(2)将这个地点空出来,将数据“8”插进去。对于一列无序的数据列,比如:{49,38,65,97,76,13,27,49},怎样使用这类方法进行排序呢?基本思想很简单,即频频使用上述方法排序,由序列的长度不停增添,向来抵达成整个无序列就有序了第一,{49}是有序列,我们将38插入到有序列{49}中,获得两个数据的有序列:{38,49},而后,将第三个数据65插入到上述序列中,获得有序列:{38,49,65}依据这类方法,直到将最后一个数据65插入到上述有序列中,获得{13,27,38,49,49,65,76,97}这样,就达成了整个数据列的排序工作。注意到无序列“插入排序算法”成为认识决这类问题的平台(2)冒泡法排序所谓冒泡法排序,形象地说,就是将一组数据依据从小到大的次序摆列时,小的数据视为质量轻的,大的数据视为质量沉的。一个小的数据就好似水中的气泡,往上挪动,一个较大的数据就好似石头,往下挪动。明显最后会沉到水底,最轻的会浮到顶,频频进行,直到数据列排成为有序列。以上过程反应了这类排序方法的基本思路。我们先对一组数据进行剖析。设待排序的数据为:{49,38,65,97,76,13,27,49}排序的详细操作步骤以下:1.将第
1个数与右侧相邻的数
38进行比较,因为
38<49,49应下沉,即向右挪动,所以互换他们的地点,获得新的数据列:{38,49,65,97,76,13,27,49}2.将新数据列中的第
2个数
49与右侧相邻的数
65进行比较,因为
65>49,所以次序不变,获得新的数据列:{38,49,65,97,76,13,27,49}3.将新数据列中的第
3个数
65与右侧相邻的数
97进行比较,因为
97>65,所以次序不变,获得新的数据列:4.将新数据列中的第
{38,49,65,97,76,13,27,49}4个数97与右侧相邻的数76进行比较,因为
76<97,97
应下沉,所以次序不变,获得新的数据列:5.将新数据列中的第
{38,49,65,76,97,13,27,49}5个数97与右侧相邻的数13进行比较,
因为
13<97,97
应下沉,所以次序改变,获得新的数据列:6.将新数据列中的第
{38,49,65,76,13,97,27,49}6个数97与右侧相邻的数27进行比较,因为
27<97,97
应下沉,所以次序改变,获得新的数据列:7.将新数据列中的第
{38,49,65,76,13,97,27,49}7个数97与右侧相邻的数49进行比较,因为
49<97,97
应下沉,所以次序改变,获得新的数据列:{38,49,65,76,13,97,49,27}我们把上述过程称为一趟排序。其基本特色是最大的数据沉究竟,即排在最左侧地点上的数据是数组中最大的数据。频频履行上边的步骤,就能达成排序工作,排序过程不会超出趟。这类排序的方法称为冒泡排序。上边的剖析拥有一般性,假如数据列有n个数据构成,至多经过n-1趟排序,就能完成整个排序过程4.进位制(1)观点进位制是一种记数方式,用有限的数字在不一样的地点表示不一样的数值。可使用数字符号的个数称为基数,基数为n,即可称n进位制,简称n进制。此刻最常用的是十进制,往常使用10个阿拉伯数字0—9进行记数。对于任何一个数,我们能够用不一样的进位制来表示。比方:十进数57,能够用二进制表示为111001,也能够用八进制表示为71、用十六进制表示为39,它们所代表的数值都是同样的。一般地,若k是一个大于一的整数,那么以k为基数的k进制能够表示为:anan1...a1a0(k)(0ank,0an1,...,a1,a0k),而表示各样进位制数一般在数字右下脚加注来表示,如111001表示二进制数,34(5)表(2)示5进制数。(2)进位制间的变换对于进位制的变换,教科书上以十进制和二进制之间的变换为例解说,并推行到十进制和其余进制之间的变换。这样做的原由是,计算机是以二进制的形式进行储存和计算数据的,而一般我们传输给计算机的数据是十进制数据,所以计算机一定先将十进制数转换为二进制数,再办理,明显运算后初次获得的结果为二进制数,同时计算机又把运算结果由二进制数变换成十进制数输出。非十进制数变换为十进制数比较简单,只需计算下边的式子值即可:第一步:从左到右挨次拿出k进制数anan1.....a1a0(k)各位上的数字,乘以相应的k的幂,k的幂从n开始取值,每次递减1,递减到0,即ankn,an1kn1,.........,a1k,a0k0;第二步:把所获得的乘积加起来,所得的结果就是相应的十进制数。十进制数变换成非十进制数把十进制数变换为二进制数,教科书上供给了“除2取余法”,我们能够类比获得十进制数变换成k进制数的算法“除k取余法”。非十进制之间的变换一个自然的想法是利用十进制作为桥梁。教科书上供给了一个二进制数据与16进制数据之间的互化的方法,也就是先有二进制数转变为十进制数,再由十进制数转变成为16进制数。四.【典例分析】题型1:求最大条约数例1.(1)用展转相除法求123和48的最大条约数?(2)用更相减损来求80和36的最大条约数?分析:(1)展转相除法求最大条约数的过程以下:(成立带余除式)123=2×48+2748=1×27+2127=1×21+621=3×6+36=2×3+0最后6能被3整除,得123和48的最大条约数为3。2)剖析:我们将80作为大数,36作为小数,履行更相减损术来求两数的最大条约数。履行结束的准则是减数和差相等更相减损术:因为80和36都是偶数,要去公因数2。80÷2=40,36÷2=18;40和18都是偶数,要去公因数2。40÷2=20,18÷2=9下边来求20与9的最大条约数,20-9=1111-9=29-2=77-2=55-2=33-2=12-1=1可得80和36的最大条约数为22×1=4。评论:对照两种方法控制好算法的结束,展转相除法是抵达余数为0,更相减损术是到达减数和差相等。例2.设计一个算法,求出840与1764的最大公因数。分析:我们已经学习过了对自然数的素因数分解的方法,下边的算法就是在此基础上设计的。解题思路以下:第一对两个数进行素因数分解:840=23×3×5×7,1764=22×32×72,其次,确立两个数的公共素因数:2,3,7。接着确立公共素因数的指数:对于公共素因数2,840中为23,1764中为22,应取较少的一个22,同理可得下边的因数为3和7。算法步骤:第一步:将840进行素数分解23×3×5×7;第二步:将1764进行素数分解22×32×72;第三步:确立它们的公共素因数:2,3,7;第四步:确立公共素因数2,3,7的指数分别是:2,1,1;第五步:最大公因数为22×31×71=84。评论:质数是除1之外只好被1和自己整除的正整数,它应当是无穷多个,可是当前没有一个规律来确立全部的质数题型2:秦九韶算法例3.(2009福州模拟)假如履行右边的程序框图,那么输出的S()开始A.22B.46i1,s1C.94D.190答案C2、(2009浙江卷理)某程ii1序框图以下图,该程序运转后输出的k的值是()A.4B.5s2(s1)C.6D.7【分析】对于k0,s1,k1,而对于k1,s3,k2,则i5?否是输出s结束k2,s38,k3,后边是k3,s38211,k4,不切合条件时输出的k4.答案A3、(2009天津卷理)阅读上(右)图的程序框图,则输出的S=()A26B35C40D57【分析】当i1时,T2,S2;当i2时,T5,S7;当i3时,T8,S15;当i4时,T11,S26;当i5时,T14,S40;当i6时,T17,S57,应选择C。答案C4(2009安徽卷文)程序框图上(右)(即算法流程图)以下图,其输入结果是_______。【分析】依据流程图可得a的取值挨次为1、3、7、15、31、63答案127评论:秦九韶算法合用一般的多项式f(x)=anxn+an-1xn-1+.+a1x+a0的求值问题。直接法乘法运算的次数最多可抵达(n1)n,加法最多n次。秦九韶算法经过转变把乘法运算的次数2减少到最多n次,加法最多n次。例4.已知多项式函数f(x)=2x5-5x4-4x3+3x2-6x+7,求当x=5时的函数的值。分析:把多项式变形为:f(x)=2x5-5x4-4x3+3x2-6x+7=((((2x-5)x-4)x+3)x-6)x+7计算的过程能够列表表示为:多项式x系数2-5-43-67运算运算所得的值10251055402670+变形后x的"系数"25211085342677*5最后的系数2677即为所求的值算法过程:0v=21v=2×5-5=5v2=5×5-4=21v3=21×5+3=1084v=108×5-6=534v=534×5+7=26775评论:假如多项式函数中出缺项的话,要以系数为0的项补齐后再计算。题型三:排序例4.试用两种排序方法将以下8个数:7,1,3,12,8,4,9,10。依据从大到小的次序进行排序。分析:能够依据直接插入排序和冒泡排序这两种方法的要求,联合图形,剖析写出。直接插入法排序:[7]131284910[71]31284910[731]1284910[12731]84910[128731]4910[1287431]910[12987431]10[1210987431]冒泡排序7777777711333333331121212121212121218888888814444444419999999911010101010101010第一趟771212121231288910128791098491088491077791044441033333111111第2趟第3趟第4趟第5趟第6趟评论:直接插入法和冒泡法排序是常有的排序方法,经过该例,我们对照能够发现,直接插入排序比冒泡排序更有效一些,履行的操作步骤更少一些例6.给出以下四个数:6,-3,0,15,用直接插入法排序将它们按从小到大的次序摆列,用冒泡法将它们按从大到小的次序排剖析:无论从大到小的次序仍是按从大到小的次序,都可按两种方法的步骤进行排序。分析:直接插入排序法:[6]-3015[-36]015[-306]15[-30615]用冒泡排序法排序:6666666151515-3-3000151566600-3151500000151515-3-3-3-3-3-3-3题型4:进位值例7.把十进制数89化为三进制数,并写出程序语句.分析:详细的计算方法以下:89=3×29+229=3×9+29=3×3+03=3×1+01=3×0+1所以:89(10)=1011001(3)。评论:依据三进制数满三进一的原则,能够用3连续去除89及其所的得的商,而后按倒序的先后次序拿出余数构成数据即可。例8.将8进制数314706(8)化为十进制数,并编写出一个实现算法的程序。432分析:314706(8)=3×85+1×8+4×8+7×8+0×81+6×80=104902。所以,化为十进制数是104902。评论:利用把k进制数转变为十进制数的一般方法就能够把8进制数314706(8)化为十进制数,而后依据该算法,利用GET函数,应用循环结构能够设计程序。五.【思想总结】1.求最大条约数开始(1)展转相除法程序框图与程序语句输入:m,n程序:INPUT“m,n=”;m,nr=mMODnDOr=mMODnm=nm=nn=rn=rLOOPUNTILr=0PRINTNr=0?ENDY输出:开始2)更相减损术更相减损术程序:INPUT“请输入两个不相等的正整数”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb<aTHENt=aa=bb=tENDIFc=a-ba=bb=cLOOPUNTILa=bPRINTa^iEND对于两个正整数怎样选择适合的方法求他们的最大条约数方法合用范围及特色短除法适合两个较小的正整数或两个质因数较少的正整数,简易易操作。穷举法适共计算机操作,但一一考证过于繁琐。合用于两个较大的正整数,以除法为主,展转相除法计算次数相对较少,特别展转相除法当两个数字大小差异较大时计算次数较明显。合用于两个较大的正整数,更相减损术以减法为主,计算次数上相对于展转相更相减损术处法许多。2.我们以这个5次多项式函数为
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 工程项目管理合同管理练习题
- 2025年鹤岗货运从业资格考试题
- 2025年北京货运从业资格证考试题技巧
- 2025年潮州货运资格证考试有哪些项目
- 《G蛋白耦联受体》课件
- 地下商场非开挖扩建协议
- 铁路工程预算员招聘协议样本
- 制药工厂租赁合同样本
- 美发卫生操作规范
- 临时策划师聘用合同范本
- cmmi3过程域直接证据
- 初三数学中考模拟试卷共八套
- 经典绘本推荐--《果果的花朵》
- 剑桥英语 中级班 听力脚本剑桥二
- 蛋白质分选与膜泡运输
- 弹簧设计公差标准
- X62W万能铣床电气控制
- 常用普通螺纹加工的中径和顶径极限偏差快速查询表
- 质量认证基础知识(共218页).ppt
- 《光学教程》[姚启钧]课后习题解答
- ACOG指南:妊娠期高血压疾病指南(专家解读)
评论
0/150
提交评论