版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中国古代数学中的算法案例定义如果有一个自然数a能被自然数b整除,那么称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。1.求两个正整数最大公约数的算法1.求两个正整数最大公约数的算法问题:求78和36的最大公约数。7836239183136所以:78和36的最大公约数是2×3=6思考:假设a和b的最大公约数p,那么a-b,或是b-a是否能被p整除?例如,求78和36的最大公约数:(78,36)→(42,36)→(6,36)→(6,30)→(6,24)→(6,18)→(6,12)→(6,6).所以:78和36的最大公约数是6理论依据:由a-b=r→a=b+r,得(a,b)与(b,r)有相同的公约数.更相减损术等值算法简介更相减损术是出自?九章算术?的一种求最大公约数的算法,它原本是为约分而设计的。但它适用于任何需要求最大公约数的场合。例1:用等值算法〔更相减损术〕求以下两数的最大公约数。〔1〕225,135;〔2〕98,280.答案:(1)45;(2)14.输出bYN输入a,ba
≠b结束开始a>bb=b-aa=a-bYN程序:a=input(“a=〞);b=input(“b=〞);whilea<>bifa>ba=a-b;elseb=b-a;endendprint(%io(2),b,“两数的最大公约数为:〞)辗转相除法辗转相除法最早出现在欧几里得的几何原本中〔大约公元前300年〕欧几里得辗转相除法〔2〕98,280.〔98,280〕→〔98,84〕→〔14,84〕输出bb=rYN输入a,ba=br=amodbr
≠0结束开始r=aModb第一步:输入两个正整数a,b〔a>b〕;第二步:求出a÷b的余数r;第三步:假设r≠0,令a=b,b=r,,重复第二步;假设r=0,执行第四步第四步:输出最大公约数b.a=input(“a=〞);b=input(“b=〞);r=modulo(a,b);whiler<>0a=b;b=r;r=modulo(a,b);endb更相减损术和辗转相除法的主要区别在于:前者所使用的运算是“减〞,后者是“除〞。从算法思想上看,两者并没有本质上的区别,但是在计算过程中,如果遇到一个数很大,另一个数比较小的情况,可能要进行很屡次减法才能到达一次除法的效果,所以辗转相除法更好一些。早在我国先秦时期,?墨经?上就已经给出了圆的定义。我国古代数学经典?九章算术?在第一章“方田〞章中写到“半周半径相乘得积步〞,也就是我们现在所熟悉的面积公式。为了证明这个公式,我国魏晋时期数学家刘徽写了一篇1800余字的注记,这篇注记就是数学史上著名的“割圆术〞。2.割圆术刘徽形容他的“割圆术〞说:割之弥细,所失弥少,割之又割,以至于不可割,那么与圆合体,而无所失矣。简单来说所谓“割圆术〞,是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。第一,从半径为1的圆内接正六边形开始,计算它的面积S6;第二,逐步加倍圆内接正多边形的边数,分别计算圆内接正十二边形,正二十四边形,正四十八边形,…的面积,到一定的边数〔设为2n〕为止,得到一列递增的数,S6,S12,S24,S48,…,S2n.第三,S2n近似等于圆面积。下面的关键是找出正n边形的面积与正2n边形的面积之间的关系,以便递推。设圆的半径为1,正n边形的边长AB为xn,弦心距OG为hn;面积为Sn,根据勾股定理,得:容易知道x6=1,
正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积,即正2n边形的边长为于是由求得S12=3;S24≈3.105828;……
按照这样的思路,刘徽把圆内接正多边形的面积一直算到了正3072边形,并由此而求得了圆周率为3.14和3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。祖冲之〔429~500〕南北朝时期杰出的数学家和天文学家,在数学方面,祖冲之推算出圆周率π的缺乏近似值〔朒数〕3.1415926和过剩近似值〔盈数〕3.1415927,指出π的真值在盈、朒两限之间,即3.1415926<π<3.1415927n=6;x=1;s=6*sqrt(3)/4;fori=1:1:5h=sqrt(1-(x/2)^2);s=s+n*x*(1-h)/2;n=2*n;x=sqrt((x/2)^2+(1-h)^2);endprint(%io(2),n,s)程序:3、秦九韶算法秦九韶〔1208年-1261年〕南宋官员、数学家,与李冶、杨辉、朱世杰并称宋元数学四大家。字道古,汉族,自称鲁郡〔今山东曲阜〕人,生于普州安岳〔今属四川〕。精研星象、音律、算术、诗词、弓剑、营造之学,历任琼州知府、司农丞,后遭贬,卒于梅州任所,著作?数书九章?,其中的大衍求一术、三斜求积术和秦九韶算法是具有世界意义的重要奉献。求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法。3.求多项式的值的算法一般的解决方案直接计算2×55-5×54-4×53+3×52-6×5+7的值。
上述算法一共做了解15次乘法运算,5次加法运算.有没有更高效的算法?用提取公因式的方法多项式变形为f(x)=2x5-5x4-4x3+3x2-6x+7=x4(2x-5)-4x3+3x2-6x+7=x3((2x-5)x-4)+3x2-6x+7…………=((((2x-5)x-4)x+3)x-6)x+7从内到外,如果把每一个括号都看成一个常数,那么变形后的式子中有哪些“一次式〞?x的系数依次是什么?计算的过程可以列表表示为:f(x)=((((2x-5)x-4)x+3)x-6)x+7,x=5v0=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∴f(5)=2677总结:这样共作了5次加法,5次乘法.秦九韶算法?数书九章?——秦九韶算法设是一个n次的多项式对该多项式按下面的方式进行改写:直接计算多项式乘法
次,加法
次?用秦九韶算法计算多项式乘法
次,加法
次?练习:用秦九韶算法求多项式f(x)=5x5+2x4+3x3+x-8当x=8时的值,并答复需要几次乘法?几次加法?解:f(x)=((((5x+2)x+3)x+0)x+1)x-8,x=8f(x)=5x5+2x4+3x3+0x2+x-8v0=5v1=v0x+2=5×8+2=42v2=v1x+3=42×8+3=339v3=v2x+0=339×8+0=2712v4=v3x+1=2712×8+1=21697v5=v4x-8=21697×8-8=173568∴f(8)=1735685次加法,5次乘法怎样用程序框图表示秦九韶算法?观察秦九韶算法的数学模型,计算vk时要用到vk-1的值,假设令v0=an,我们可以得到下面的递推公式:v0=anvk=vk-1·x+an-k(k=1,2,…,n)这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现。开始输入x,n;a0,a1,a2,…,ank=k-1v=v*x+ak输出S结束k=n,v=an开始输入x,n;a0,a1,a2,…,ank>0是否Scilab语言:x=input("x=");n=input("n=");result=input("Thefirstxishu");fori=1:1:n
a=input("xishu:");result=result*x+a;enddisp(result,"Theresultis:");(2021全国卷8)中国古代有计算多项式值的秦九韶算法,右图是实现该算法的程序框图.执行该程序框图,假设输入的x=2,n=2,依次输入的a为2,2,5,那么输出的〔〕(A)7〔B〕12〔C〕17〔D〕34C〔2021全国卷2〔8〕〕右边程序框图的算法思路源于我国古代数学名著?九章算术?中的“更相减损术〞。执行该程序框图,假设输入a,b分别为14,18,那么输出的a=〔A〕0〔B〕2〔C〕4〔D〕14B.秦九韶是我国南宋时期的数学家,普州〔现四川省安岳县〕人,他在所著的?数书九章?中提出的多项式求值的秦九韶算法,至今仍是比较先进的算法.如下图的程序框图给出了利用秦九韶算法求某多项式值的一个实例.假设输入n,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年全球并购趋势年中展望-29正式版
- (高清版)GB∕T 37338-2019 电动摩托车和电动轻便摩托车用仪表
- 信息技术 开放系统互连 OSI登记机构的操作规程 第3部分:ISO和ITU-T联合管理的顶级弧下的对象标识符弧的登记 征求意见稿
- (3篇)小学新生入学家长代表发言稿
- 2024年商业地产行业运行半年报-2024.08-11正式版
- 某大型公园工程施工施工组织设计
- 2024年9月河北沧州泊头市事业单位面试题及参考答案
- 北师大版小学六年级上册第二单元分数混合运算单元测评试卷(共9套)
- 中国异丁烯行业市场规模现状及投资前景分析报告2024-2030年
- 科学计划和自由
- JTS-170-2015邮轮码头设计规范
- 标书技术服务方案(2篇)
- 糖尿病视网膜病变:案例分析
- 2024春季形势与政策讲稿第三讲走好新时代科技自立自强之路
- (正式版)JBT 11270-2024 立体仓库组合式钢结构货架技术规范
- 医疗器械岗位培训课件
- MDS3400调度指挥通信系统介绍
- 幼儿园也是我的家课件
- 学生指导与服务体系建设方案
- (高清版)DZT 0205-2020 矿产地质勘查规范 岩金
- 2024贵州磷化(集团)有限责任公司招聘笔试参考题库附带答案详解
评论
0/150
提交评论