![有关辗转相除法和更相减损术的问题市公开课一等奖省赛课微课金奖课件_第1页](http://file4.renrendoc.com/view12/M04/2C/33/wKhkGWZANvyAYF_5AABbj8sC3qw273.jpg)
![有关辗转相除法和更相减损术的问题市公开课一等奖省赛课微课金奖课件_第2页](http://file4.renrendoc.com/view12/M04/2C/33/wKhkGWZANvyAYF_5AABbj8sC3qw2732.jpg)
![有关辗转相除法和更相减损术的问题市公开课一等奖省赛课微课金奖课件_第3页](http://file4.renrendoc.com/view12/M04/2C/33/wKhkGWZANvyAYF_5AABbj8sC3qw2733.jpg)
![有关辗转相除法和更相减损术的问题市公开课一等奖省赛课微课金奖课件_第4页](http://file4.renrendoc.com/view12/M04/2C/33/wKhkGWZANvyAYF_5AABbj8sC3qw2734.jpg)
![有关辗转相除法和更相减损术的问题市公开课一等奖省赛课微课金奖课件_第5页](http://file4.renrendoc.com/view12/M04/2C/33/wKhkGWZANvyAYF_5AABbj8sC3qw2735.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
相关辗转相除法和更相减损术问题第1页探究一,辗转相除法思索1:在小学中我们是怎样求出两个正整数最大条约数呢?算法案例之求最大条约数求以下几组正整数最大条约数。(注:若整数m和n满足n整除m,则(m,n)=n。用(m,n)来表示m和n最大条约数。)(1)(18,30)(2)(24,16)(3)(63,63)(4)(72,8)(5)(301,133)解:21824用公有质因数2除,
3912用公有质因数3除,
343和4互质不除了。得:18和24最大条约数是:2×3=6
例、求18与24最大条约数:6;8;63;8;7;短除法想一想,怎样求8251与6105最大条约数?
第2页
思索2:对于8251与6105这两个数,它们最大条约数是多少?你是怎样得到?
因为它们公有质因数较大,利用上述方法求最大条约数就比较困难.有没有其它方法能够较简单找出它们最大条约数呢?第3页
思索3:注意到8251=6105×1+2146,那么8251与6105这两个数条约数和6105与2146条约数有什么关系?
我们发觉6105=2146×2+1813,同理,6105与2146条约数和2146与1813条约数相等.
思索4:重复上述操作,你能得到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停顿步骤,这实际上是一个循环结构
思索4:辗转相除直到何时结束?主要利用是哪种算法结构?如此循环,直到得到结果。①输入两个正整数m和n;②求余数r:计算m除以n,将所得余数存放到变量r中;③更新被除数和余数:m=n,n=r。④判断余数r是否为0:若余数为0则输出结果,不然转向第②步继续循环执行。第5页第一步,给定两个正整数m,n(m>n).第二步,计算m除以n所得余数r.第三步,m=n,n=r.
第四步,若r=0,则m,n最大条约数等于m;不然,返回第二步.
思索5:你能把辗转相除法编成一个计算机程序吗?第6页程序框图开始输入m,n求m除以n余数rm=nn=rr=0?是输出m结束否INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND第7页
思索6:假如用当型循环结构结构算法,则用辗转相除法求两个正整数m、n最大条约数程序框图和程序分别怎样表示?第8页开始输入m,n求m除以n余数rm=nr≠0?否输出m结束是n=rINPUTm,nWHILEr<>0r=mMODnm=nn=rWENDPRINTmEND第9页练习:用辗转相除法求以下两数最大条约数:(1)(225,135)(2)(98,196)(3)(72,168)(4)(153,119)45982417第10页二、更相减损术
《九章算术》是中国古代数学专著,其中“更相减损术”也能够用来求两个数最大条约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”意思是:
第一步:任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
第二步:以较大数减去较小数,接着把差与较小数比较,并以大数减小数.继续这个操作,直到所得数相等为止,则这个等数或这个数与约简数乘积就是所求最大条约数.第11页例1:用更相减损术求98与63最大条约数.98-63=35,14-7=7.21-7=14,28-7=21,35-28=7,63-35=28,因为63不是偶数,所以所以最大条约数是7.第12页
例2分别用辗转相除法和更相减损术求168与93最大条约数.168=93×1+75,93=75×1+18,75=18×4+3,18=3×6.辗转相除法:更相减损术: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.第13页
例4求325,130,270三个数最大条约数.
因为325=130×2+65,130=65×2,所以325与130最大条约数是65.
因为270=65×4+10,65=10×6+5,10=5×2,所以65与270最大条约数是5.
故325,130,270三个数最大条约数是5.第14页
练习:用更相减损术求两个正整数m,n最大条约数,能够用什么逻辑结构来结构算法?其算法步骤怎样设计?
第一步,给定两个正整数m,n(m>n).
第二步,计算m-n所得差k.
第三步,比较n与k大小,其中大者用m表示,小者用n表示.
第四步,若m=n,则m,n最大条约数等于m;不然,返回第二步.
讨论:该算法程序框图怎样表示?第15页开始输入m,nn>k?m=n是输出m结束m≠n?k=m-n是否n=km=k否
讨论:该程序框
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024房地产代办手续合同
- 2024房地产开发合伙协议书范本
- 乙醇项目建议书报告
- 人工智能 预训练模型 第2部分:评测指标与方法 编制说明
- 2024商铺租赁合同范本简单4年
- 2024创业合伙人合作的协议书范本
- 2024年绞线机项目建议书报告
- 家长会教师经典发言稿15篇
- 2024房地产合同管理论文
- 2024建筑单项施工合同范本
- 公司的员工激励机制问题研究
- 个人与公司车辆租赁合同范文
- 磁动力发电机项目商业计划书范文参考
- 液压缸设计常用结构参数及计算表
- 第五小学骨干教师培养实施方案
- 涡阳四中教师教案、听课记录及学生作业检查评比方案
- 人民调解卷宗范本
- 六年级下册心理健康试卷(共2页)
- 全国啦啦操规定套路-一级花球舞蹈啦啦操
- 三相交流电缆的电场仿真
- 公务员政审-社区现实表现证明模板.doc
评论
0/150
提交评论