![新高一数学《案例1辗转相除法与更相减损术》_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-3/15/119669b9-0c88-46cb-815c-f19181680d52/119669b9-0c88-46cb-815c-f19181680d521.gif)
![新高一数学《案例1辗转相除法与更相减损术》_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-3/15/119669b9-0c88-46cb-815c-f19181680d52/119669b9-0c88-46cb-815c-f19181680d522.gif)
![新高一数学《案例1辗转相除法与更相减损术》_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-3/15/119669b9-0c88-46cb-815c-f19181680d52/119669b9-0c88-46cb-815c-f19181680d523.gif)
![新高一数学《案例1辗转相除法与更相减损术》_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-3/15/119669b9-0c88-46cb-815c-f19181680d52/119669b9-0c88-46cb-815c-f19181680d524.gif)
![新高一数学《案例1辗转相除法与更相减损术》_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-3/15/119669b9-0c88-46cb-815c-f19181680d52/119669b9-0c88-46cb-815c-f19181680d525.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、广灵五中高一数学备课组广灵五中高一数学备课组 刘鸿英刘鸿英1. 1. 回顾算法的三种表述:回顾算法的三种表述:自然语言自然语言程序框图程序框图程序语言程序语言(三种逻辑结构)(三种逻辑结构)(五种基本语句)(五种基本语句)2. 2. 思考:思考: 小学学过的求两个数最大公约数的方法?小学学过的求两个数最大公约数的方法? 先用两个公有的质因数连续去除,一直除到所得的商是先用两个公有的质因数连续去除,一直除到所得的商是互为质数为止,然后把所有的除数连乘起来互为质数为止,然后把所有的除数连乘起来. .复复 习回顾习回顾所以,所以,7575和和105105的最的最大公约数为大公约数为15152 2、除
2、了用这种方法外还有没有其它方法?、除了用这种方法外还有没有其它方法?如求如求82518251和和61056105的最大公约数的最大公约数. . 1 1、求两个正整数的最大公约数、求两个正整数的最大公约数求求7575和和105105的最大公约数的最大公约数75755 5151510510521215 57 73 31 1、辗转相除法、辗转相除法: :此算法是欧几里得在公元前此算法是欧几里得在公元前300300左右左右首先提出的首先提出的 (欧几里得算法)(欧几里得算法) 所谓辗转相除法所谓辗转相除法, ,就是对于给定的两个数就是对于给定的两个数, ,用较大用较大的数除以较小的数的数除以较小的数.
3、 .若余数不为零若余数不为零, ,则将余数和较小的则将余数和较小的数构成新的一对数数构成新的一对数, ,继续上面的除法继续上面的除法, ,直到大数被小数直到大数被小数除尽除尽, ,则这时较小的数就是原来两个数的最大公约数则这时较小的数就是原来两个数的最大公约数. .例例1.用辗转相除法求用辗转相除法求161与与63的最大公约数的最大公约数.161=2633563=1 352835=1 28728=4 70所以,所以,161与与63的最大公约数为的最大公约数为7 7新新 课课82518251= =610561051+1+21462146 61056105= =214621462+2+181318
4、13 21462146= =181318131+1+33333318131813= =3333335+5+148148333333= =1481482+2+3737148148= =37374 4所以所以3737是是82518251和和61056105的最大公约数的最大公约数 例例2 2、求、求82518251和和61056105的最大公的最大公约数约数. . P P4545) )练习练习1(1)1(1)用辗转相除法用辗转相除法求求225225和和135135的最大公约数的最大公约数225225= =1351351+1+9090135135= =90901+1+45459090= =45452
5、 2所以所以4545是是225225和和135135的最大公约数的最大公约数 思考:从上面的两个例子可思考:从上面的两个例子可以看出计算的规律是什么?以看出计算的规律是什么? S1S1:用大数除以小数:用大数除以小数S2S2:除数变成被除数,余数变成除数:除数变成被除数,余数变成除数S3S3:重复:重复S1S1,直到余数为,直到余数为0 0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤, ,这实际上是这实际上是一个循环结构一个循环结构m=nm=nq qr r算法步骤算法步骤第一步:输入两个正整数第一步:输入两个正整数m,n(mm,n(mn)
6、.n).第二步:计算第二步:计算m m除以除以n n所得的余数所得的余数r.r.第三步:第三步:m=n,nm=n,n=r.=r.第四步:若第四步:若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步. . 第五步:输出最大公约数第五步:输出最大公约数m.m.程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0? 输出输出m m结束结束INPUT “m,n=“;m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框
7、图程序框图程程 序序INPUT “m,n=“;m,nWHILE WEND r = m MOD nm = nn = rr0PRINT mENDr=1求求m m除以除以n n的余数的余数r rm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr0?r0? 输出输出m m结束结束r=1r=12 2、更相减损术、更相减损术第一步:任意给定两个正整数第一步:任意给定两个正整数; ;判断他们是否都是偶判断他们是否都是偶数数. .若是若是, ,则用则用2 2约简约简; ;若不是则执行第二步若不是则执行第二步. .第二步:以较大的数减较小的数第二步:以较大的数减较小的数, ,接着把所得的差与接着把所
8、得的差与较小的数比较较小的数比较, ,并以大数减小数并以大数减小数. .继续这个操作继续这个操作, ,直到直到所得的减数和差相等为止所得的减数和差相等为止, ,则这个等数就是所求的最则这个等数就是所求的最大公约数大公约数. . 算理:可半者半之算理:可半者半之, ,不可半者不可半者, ,副置分母、子之数副置分母、子之数, ,以少以少减多减多, ,更相减损更相减损, ,求其等也求其等也, ,以等数约之以等数约之. .例例3 3 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解:由于解:由于6363不是偶数,把不是偶数,把9898和和6363以大数减小数,并辗转相减以大数
9、减小数,并辗转相减 989863633535636335352828353528287 728287 7212121217 7141414147 77 7所以,所以,9898和和6363的最大公约数等于的最大公约数等于7 7 98=6313563=3512835=2817 辗转相除法与更相减损术的区别辗转相除法与更相减损术的区别(1)(1)都是求最大公约数的方法都是求最大公约数的方法, ,计算上辗转相除法以除法为主计算上辗转相除法以除法为主, ,更相减损术以减法为主更相减损术以减法为主, ,计算次数上辗转相除法计算次数相对较计算次数上辗转相除法计算次数相对较少少, ,特别当两个数字大小区别较大
10、时计算次数的区别较明显特别当两个数字大小区别较大时计算次数的区别较明显. .(2)(2)从结果体现形式来看从结果体现形式来看, ,辗转相除法体现结果是以相除余数辗转相除法体现结果是以相除余数为为0 0而而 得到得到, ,而更相减损术则以减数与差相等而得到而更相减损术则以减数与差相等而得到解法1:(更相减损术)由于49不是偶数,把91和49以大数减小数,并辗转相减,即:914942 49427 42735 35728 28721 21714 147791与49的最大公约数是7。解法2(辗转相除法) 9149142 494217 4276 91与49的最大公约数是7。探究探究3:怎样用更相减损术求
11、182与98的最大公约数? 方法:由于 182与98 都是偶数,故将它们同除以2,得91与49,再用上面的方法求得91与49的最大公约数为7,则72=14为182与98的最大公约数.理论迁移理论迁移 例例1 1 分别用辗转相除法和更相减损分别用辗转相除法和更相减损术求术求168168与与9393的最大公约数的最大公约数. . 辗转相除法:辗转相除法:168=93168=931+751+75, 93=7593=751+181+18, 75=1875=184+34+3, 18=318=36.6.更相减损术更相减损术:168-93=75:168-93=75, 93-75=1893-75=18, 75
12、-18=5775-18=57, 57-18=3957-18=39, 39-18=2139-18=21, 21-18=321-18=3, 18-3=1518-3=15, 15-3=1215-3=12, 12-3=912-3=9, 9-3=69-3=6, 6-3=3.6-3=3. 例例2 2 求求325325,130130,270270三个数的最大三个数的最大公约数公约数. . 因为因为325=130325=1302+652+65,130=65130=652 2,所以所以325325与与130130的最大公约数是的最大公约数是65.65. 因为因为270=65270=654+104+10,65=1065=106+56+5,10=510=52 2,所以,所以6565与与270270最大公约数是最大公约数是5. 5. 故故325325,130130,270270三个数的最大公约三个数的最大公约数是数是5.5.用更相减损术求两个整用更相减损术求两个整数数m,n的最大公约数的最大公约数INPUT “m,n=”;m,nWHILE mn IF mn T
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 厦门市第十中学招聘校医笔试真题2023
- 徽商期货有限责任公司招聘笔试真题2023
- 结构力学优化算法:灵敏度分析:结构尺寸与形状优化
- 结构力学数值方法:有限体积法(FVM):FVM软件操作与实践
- 教科版三年级上册科学教案(全册)
- 英语练与测﹒课课通(基础模块1)-答案
- 2024-2025学年广东省深圳市福田外国语学校九年级(上)开学数学试卷
- 跨境电商客户关系管理 习题-及答案 项目四习题参考答案(跨境电商客户关系管理)
- 2022离网光伏抽水系统
- 氯气的性质及应用 高一上学期化学苏教版(2019)必修第一册
- 中国儿童气质评定
- 内分泌科急性肾上腺皮质功能减退症诊疗规范2023版
- 《地理信息系统概论》教案
- 厨房卫生教案-劳动课教学设计
- 《photoshopcs5平面设计案例教程》
- 艾宾浩斯遗忘曲线-计划表《遗忘曲线》
- 招聘app开发方案
- 初一年级工作计划安排表
- 关于2023年国有企业三重一大决策制度
- 综掘机、综掘工艺专项安全风险辨识评估报告
- 常用温度加速模型计算
评论
0/150
提交评论