算法案例教案4苏教版必修.doc
《算法案例教案4苏教版必修.doc》由会员分享,可在线阅读,更多相关《算法案例教案4苏教版必修.doc(12页珍藏版)》请在咨信网上搜索。
1、第八课时 算法案例教学目标:本节通过算法案例的学习,进一步理解算法的含义,掌握算法设计的常用方法.教学重点:如何在伪代码中运用条件语句.教学难点:如何在伪代码中运用条件语句.教学过程:.课题导入1.中国古代数学中算法的内容是非常丰富的,比如,中国古代数学著作九章算术中介绍了下述“约分术”:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”给出了求任意两个数的最大公约数的一种算法,被后人称为“更相减损术”.这种方法与欧氏的辗转相除法异曲同工,本质上是相同的.2.中国是研究不定方程最早的国家,公元初的五家共井问题就是一个不定方程组问题,公元5世纪的张丘建算经中的
2、百鸡问题标志着中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.研究不定方程要解决三个问题:判断何时有解;有解时决定解的个数;求出所有的解.二分法是用计算机求解多项式方程的一种常用方法.基本思想是:如果取a,b的中点x0=(a+b)/2;若f(x0)=0,则x0就是方程的根,若f(a)f(x0)0,则解在(x0,b)上,以x0代替a,否则解在(a,x0)之间,以x0代替b,重复上述步骤,直到|ab|c,c是一个很小的正数,计算终止,x0就是方程的根.讲授新课例1:古今中外,许多人致力于圆周率的研究与计算.为了计算出圆周率的越来越好的近似值,一代代的数学家为这个神秘
3、的数贡献了无数的时间与心血.我国东汉的数学家刘徽利用“割圆术”计算圆的面积及圆周率.“割圆术”被称为千古绝技,它的原理是用圆内接正多边形的面积去逼近圆的面积,具体计算如下:在单位圆内作内接正六边形,其面积记为A1,边长记为a1,在此基础上作圆内接正12边形,面积记为A2,边长为a2一直做下去,记该圆的内接正62n1边形面积为An,边长为an.由于所考虑的是单位圆,计算出的An即为圆周率的近似值,n越大,An与越接近.你能设计这样计算圆周率的一个算法吗?我的思路:应首先推导出an,an1,An,An1的关系.如图,设PQ为圆内接正62n1边形的一边,即PQ=an1,OR为与PQ垂直的半径,R为P
4、Q弧的平分点,显然PR=an.a1=1,an=PR=(n=2,3,4),A1=61=,An=62n1|OR|PT|=32n2an1(n=2,3,4).通过上面两式,从a11开始进行迭代,可逐步计算出an与An.由于所考虑的是单位圆,计算出的An即为圆周率的近似值,n越大,An与越接近.算法和流程图如下:BeginRead n1aFor I from 2 to nA32I2aaSqrt22Sqrt1a2/4;Print I,A,aEnd forEnd流程图:例2:有一个故事是讲唐代大官杨埙提拔官员的经过.他让两个资格职位相同的候选人解答下面这个问题,谁先答出就提拔谁.“有人在林中散步,无意中听到
5、几个强盗在商量怎样分配抢来的布匹.若每人分6匹,就剩5匹;若每人分7匹,就差8匹.问共有强盗几个?布匹多少?”你能用一个简单算式求出强盗个数和布匹数吗?我的思路:这个问题可看作二元一次方程组问题.问题的特点是给出两种分配方案,一种分法分不完,一种分法不够分.中国古代的九章算术一书中搜集了许多这类问题,各题都有完整的解法,后人称这种算法为“盈不足术”.这种算法可以概括为两句口诀:有余加不足,大减小来除.公式:(盈不足)两次所得之差人数,每人所得数人数盈物品总数,求得强盗有(85)(76)13(人),布匹有613583(匹).伪代码:Read a,b,c,dx(a+b)/(dc)ycx+aprin
6、t x,y流程图:例3:由F0=1,F1=1,Fn=Fn2+Fn1所定义的数列Fn,称为斐波那契数列,试设计一个求数列的前100项的值的算法,画出流程图并用伪代码表示.我的思路:数列Fn有个特点,前两个数都是1,从第3个数开始,每个数都是前两个数的和,例如:3是1和2的和;13是5和8的和等等.此问题的算法用流程图和伪代码表示:a1;b1;n1;输出n,;while nb),求它们的最大公约数.解析:求两个正整数a、b(ab)的最大公约数,可以归结为求一数列:a,b,r1,r2,rn1,rn,rn+1,0此数列的首项与第二项是a和b,从第三项开始的各项,分别是前两项相除所得的余数,如果余数为0
7、,它的前项rn+1即是a和b的最大公约数,这种方法叫做欧几里得辗转相除法,其算法如下:S1输入a,b(ab);S2求a/b的余数r;S3如果r0,则将ba,rb,再次求a/b的余数r,转至S2;S4输出最大公约数b.伪代码如下:10Read a,b20rmod(a,b)30Ifr=0thenGoto 8040Else50ab60br70Goto 2080Print b流程图如下:点评:算法的多样性:对于同一个问题,可以有不同的算法.例如求1+2+3+100的和,可以采用如下方法:先求1+2,再加3,再加4,一直加到100,最后得到结果5050.也可以采用这样的方法:1+2+3+100=(1+1
8、00)+(2+99)+(3+98)+(50+51)=50101=5050.显然,对于算法来说,后一种方法更简便,而循环累加更适用于计算机解题.因此,为了有效地进行解题,不仅要保证算法正确,还要选择好的算法,即方法简单、运算步骤少,能迅速得出正确结果的算法.例5:求1734,816,1343的最大公约数.分析:三个数的最大公约数分别是每个数的约数,因此也是任意两个数的最大公约数的约数,也就是说三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.解:用“辗转相除法”.先求1734和816的最大公约数,1734=8162+102;816=1028;所以1734与816的最大公约数为
9、102.再求102与1343的最大公约数,1343=10213+17;102=176.所以1343与102的最大公约数为17,即1734,816,1343的最大公约数为17.例6:猴子吃桃问题:有一堆桃子不知数目,猴子第一天吃掉一半,觉得不过瘾,又多吃了一只,第二天照此办法,吃掉剩下桃子的一半另加一个,天天如此,到第十天早上,猴子发现只剩一只桃子了,问这堆桃子原来有多少个?解析:此题粗看起来有些无从着手的感觉,那么怎样开始呢?假设第一天开始时有a1只桃子,第二天有a2只第9天有a9只,第10天有a10只.在a1,a2,a10中,只有a10=1是知道的,现要求a1,而我们可以看出a1,a2,a1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 案例 教案 苏教版 必修
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。