版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
辗转相除法与第1页知识探究(一):辗转相除法思索1:18与30最大条约数是多少?你是怎样得到?先用两个数公有质因数连续去除,一直除到所得商是互质数为止,然后把全部除数连乘起来即为最大条约数.第2页思索2:对于8251与6105这两个数,因为其公有质因数较大,利用上述方法求最大条约数就比较困难.注意到8251=6105×1+2146,那么8251与6105这两个数条约数和6105与2146条约数有什么关系?第3页思索3:又6105=2146×2+1813,同理,6105与2146条约数和2146与1813条约数相等.重复上述操作,你能得到8251与6105这两个数最大条约数吗?2146=1813×1+333,148=37×4+0.333=148×2+37,1813=333×5+148,8251=6105×1+2146,6105=2146×2+1813,第4页
辗转相除法是一个重复执行直到余数等于0停顿步骤,这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q+r用程序框图表示出右边过程r=mMODnm=nn=rr=0?是否思考4:辗转相除法中的关键步骤是哪种逻辑结构?第5页思索5:上述求两个正整数最大条约数方法称为辗转相除法或欧几里得算法.普通地,用辗转相除法求两个正整数m,n最大条约数,能够用什么逻辑结构来结构算法?其算法步骤怎样设计?第一步,给定两个正整数m,n(m>n).第二步,计算m除以n所得余数r.第三步,m=n,n=r.第四步,若r=0,则m,n最大条约数等 于m;不然,返回第二步.
第6页思索6:该算法程序框图怎样表示?开始输入m,n求m除以n余数rm=nn=rr=0?是输出m结束否第7页思索7:该程序框图对应程序怎样表述?INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND开始输入m,n求m除以n余数rm=nn=rr=0?是输出m结束否第8页思索8:假如用当型循环结构结构算法,则用辗转相除法求两个正整数m,n最大条约数程序框图和程序分别怎样表示?第9页开始输入m,n求m除以n余数rm=nr>0?否输出m结束是n=rINPUTm,nWHILEr>0r=mMODnm=nn=rWENDPRINTmEND第10页练习1:利用辗转相除法求两数4081与20723最大条约数.(53)20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.第11页更相减损术“更相减损术”(也是求两个正整数最大条约数算法)步骤:第一步:任意给定两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步。第二步:以较大数减较小数,接着把所得差与较小数比较,并以大数减小数。继续这个操作,直到所得减数和差相等为止,则这个等数或这个数与约简数乘积就是所求最大条约数。第12页例、用更相减损术求98与63最大条约数(自己按照步骤求解)解:因为63不是偶数,把98和63以大数减小数,并辗转相减。所以,98和63最大条约数等于7。98-63=35
63-35=2835-28=728-7=2121-7=1414-7=7第13页更相减损是一个重复执行直到减数等于差时停顿步骤,这实际也是一个循环结构
思索:更相减损直到何时结束?利用是哪种算法结构?第14页程序:INPUT“a,b”;a,bi=0WHILEaMOD2=0ANDbMOD2=0a=a/2b=b/2i=i+1WENDDOIFb>aTHENt=aa=bb=tENDIFa=a-bLOOPUNTILa=bPRINTa*2^iEND开始输入:a,b输出:a×2i结束a=b?a=a/2,b=b/2Ya=a-bt=a,a=b,b=tb>a?aMOD2=0且bMOD2=0?YNNNYi=0i=i+1第15页
例2分别用辗转相除法和更相减损术求168与93最大条约数.辗转相除法:168=93×1+75, 93=75×1+18, 75=18×4+3, 18=3×6.第16页更相减损术:168-93=75,93-75=18,75-18=57,57-18=39,39-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-3=3.第17页例3:用辗转相除法和更相减损术求210与714最大条约数.第18页比较辗转相除法与更相减损术区分(1)都是求最大条约数方
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 材料范文之创建文明乡镇汇报材料
- 职场人如何管理自己有限的时间-职场
- 部编版四年级下册道德与法治期末测试卷附答案(考试直接用)
- 小学六年级下册数学期末测试卷含答案【轻巧夺冠】
- 毕业设计文献
- 人教版六年级下册数学期末测试卷及参考答案(轻巧夺冠)
- 人教版六年级下册数学期末测试卷含答案【完整版】
- 人教版四年级下册数学期末测试卷及参考答案【培优b卷】
- 人教版六年级下册数学期末测试卷(预热题)
- 人教版四年级下册数学期末测试卷及答案(新)
- 高二物理人教版选择性高分突破考点专题41普朗克黑体辐射理论
- DB32T769-2021餐饮计量规范
- 常见病幼儿返园护理
- 临床诊疗指南-耳鼻咽喉头颈外科分册
- MOOC 分析化学-大连理工大学 中国大学慕课答案
- 健身气功智慧树知到期末考试答案2024年
- 小学班会 课堂互动小游戏 扭蛋机抽奖课堂奖励游戏 课件
- 计划部门组织架构
- JTG C10-2007 公路勘测规范
- 霸王茶姬奶茶创业
- 河北省廊坊市高中联合体2024年高三第一次调研测试生物试卷含解析
评论
0/150
提交评论