《算法案例--辗转相除法》名师课件2.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《算法案例--辗转相除法》名师课件2.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法案例-辗转相除法 算法 案例 辗转 除法 名师 课件
- 资源描述:
-
1、算法案例-辗转相除法名师课件2 韩信是秦末汉初的著名军事家韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场卫士的簇拥下来到练兵场,刘邦问韩信有什么方法刘邦问韩信有什么方法,不要逐个不要逐个报数报数,就能知道场上的士兵的人数就能知道场上的士兵的人数,韩信先令士兵排成韩信先令士兵排成3列纵队列纵队,结果有结果有2人多余人多余,接着下令排成接着下令排成5列纵队列纵队,结果又多出结果又多出3人人,随后他随后他又下令改为又下令改为7列纵队列纵队,这次又剩下这次又剩下2人无法成整行人无法成整行.在场的人都在场的人都哈哈大笑哈哈大笑,以为韩信不能清点出准确的人数
2、以为韩信不能清点出准确的人数,不料笑声刚落不料笑声刚落,韩韩信高声报告共有士兵信高声报告共有士兵2333人人.众人听了一楞众人听了一楞,不知道韩信用什么不知道韩信用什么方法这么快就能得到正确的结果的方法这么快就能得到正确的结果的.今天今天,我们将以这些古典案例的思想我们将以这些古典案例的思想,设计出适宜计算机的设计出适宜计算机的运行程序运行程序,提高我们对基本算法结构和算法语句在实际中的运提高我们对基本算法结构和算法语句在实际中的运用能力用能力.复习引入问题1:在小学中我们是如何求出两个正整数的最大公约数的呢?例例1 1:求:求2424与与3030的最大公约数。的最大公约数。解:解:2 3 0
3、 2 4 用公有质因数用公有质因数2除,除,3 15 1 2 用公有质因数用公有质因数3除,除,5 4 5和和4互质不除了。互质不除了。得:得:18和和24最大公约数是:最大公约数是:236 问题2:如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?新课讲解定义:所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数。用于求两个正整数的最大公约数理论基础:理论基础:已知已知m,n,rm,
4、n,r为正整数,若为正整数,若m=nq+rm=nq+r(0rn0rn).第二步:计算第二步:计算m除以除以n所得的余数所得的余数r.第三步:第三步:m=n,n=r.第四步:若第四步:若r0,则则m,n的最大公约数等于的最大公约数等于m;否则转到第二步否则转到第二步.第五步:输出最大公约数第五步:输出最大公约数m.程序框图程序框图如右图示:如右图示:程序程序如下:如下:INPUT “m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND开始开始输入输入m,n r=m MOD n m=nr=0?是是否否 n=r 输出输出m结束结束新课讲解开始开始
5、输入输入m,n求求m除以除以n的余数的余数rm=nn0?否否输出输出m结束结束是是n=rINPUT mINPUT m,n nWHILE nWHILE n0 0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND用当型循环结构构造算法用当型循环结构构造算法:新课讲解九章算术九章算术更相减损术更相减损术 算理:算理:可半者半之,不可半者,副置分母、子可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等之数,以少减多,更相减损,求其等也,以等数约之。数约之。原理原理:第一步:第一步:任意给定两个正整数;判断他们是否
展开阅读全文