您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
用辗转相除法求最大公约数.docx 3页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：120 &&
用辗转相除法求最大公约数
你可能关注的文档：
··········
··········
辗除法百科名片辗除法（zhǎnchúfǎ）——辗转相除法，又名欧几里德算法（Euclideanalgorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法，其可追溯至3000年前。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。　　　　证明：　　设两数为a、b(b&a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a=bq......r1(0≤r)。若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2(0≤r2).若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。　　[编辑]算法　　辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：　　1.若r是a÷b的余数,则　　gcd(a,b)=gcd(b,r)　　2.a和其倍数之最大公因子为a。　　另一种写法是：　　1.a÷b，令r为所得余数（0≤r&b）　　若r=0，算法结束；b即为答案。　　2.互换：置a←b，b←r，并返回第一步。　　[编辑]虚拟码　　这个算法可以用递归写成如下:　　functiongcd(a,b){　　ifb&&0　　returngcd(b,amodb);　　else　　　　}　　或纯使用循环:　　functiongcd(a,b){　　　　whileb≠0{　　r:=　　a:=b;　　b:=r;　　}　　　　}　　pascal代码（递归）　　求两数的最大公约数　　functiongcd(a,b:integer):　　begin　　ifb=0thengcd:=a　　elsegcd:=gcd(b,amodb);　　　　其中“amodb”是指取a÷b的余数。　　例如，90的最大公因子是6,这可由下列步骤看出：　　abamodb　　06　　　　　　　　　　462126　　1260　　只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclideandomain）。　　辗转相除法的运算速度为O(n2)，其中n为输入数值的位数。　　辗转相除法原理及其详细证明如下:　　“辗转相除法”又叫做“欧几里得算法”，是公元前300年左右的希腊数学家欧几里得在他的著作《几何原本》提出的。利用这个方法，可以较快地求出两个自然数的最大公因数，即gcd或叫做HCF。　　最大公约数（greatestcommondivisor，简写为gcd；或highestcommonfactor，简写为hcf)　　所谓最大公因数，是指几个数的共有的因数之中最大的一个，例如8和12的最大公因数是4，记作gcd(8,12)=4。　　在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重覆），我们可以这样给出整除性的定义：　　对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。　　如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。　　由此我们可以得出以下推论：　　推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）　　推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除　　因为：将二式相加：a+b=hc+tc=(h+t)c同理二式相减：a－b=hc－tc=(h－t)c　　所以：(a±b)也能被c整除　　推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b　　因为：a=qb　b=ta　a=qtaqt=1因为q、t均为正整数，所以t=q=1　　所以：a=b　　辗转相除法是用来计算两个??的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:　　如果q和r是m除以n的商及余数，即m=nq+r，则gcd(m,n)=gcd(n,r)。　　证明是这样的:设a=gcd(m,n)，b=gcd(n,r)　　a=gcd(m,n)　　m能被a整除，并且n也能被a整除，则由推论1得：qn也能被a整除　　由推论2得：m-qn也能被a整除　　而m-qn=r，即r也能被a整除，所以a=b　　或　　b=gcd(n,r)　　n能被b整除，并且r也能被b整除，则由推论1得：qn也能被b整除　　由推论2得：qn+r也能被b整除　　而m
正在加载中，请稍后...用辗转相除法求两个数的最大公约数 - 经典算法问题 - 甘肃省康县第一中学欢迎您
甘肃省康县第一中学欢迎您
您现在的位置－ -&
用辗转相除法求两个数的最大公约数
作者:南广明
问题：用辗转相除法求两个数的最大公约数，并用流程图描述出来。分析：辗转相除法求最大公约数的步骤为：设给定的两个正整数位m和n，求他们的最大公约数的步骤：（1）以m除以n，令所得的余数为r.（2）若r=0，则输出结果n，算法结束；否则，继续步骤（3）。（3）令m=n，n=r，并返回步骤（1）继续进行。根据以上分析，我们用流程图描述如下：600)makesmallpic(this,600,1800);' src="/upload_files/article/97/336_04_srnxo.jpg" border="0" alt="4.JPG" title="4.JPG" />辗转相除法求最大公约数的流程图算法描述扩展：用伪代码描述辗转相除法求最大公约数的算法INPUT m,nr=m mod nDO WHILE r≠0& m=n& n=r& r=m mod nLOOPPRINT n
责任编辑：扫二维码下载作业帮
1.75亿学生的选择
下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
用辗转相除法求568和1065的最大公因数
扫二维码下载作业帮
1.75亿学生的选择
..497568÷497=1..71497÷71=7所以最大公因数是71明教为您解答,请点击[满意答案];如若您有不满意之处,请指出,我一定改正!希望还您一个正确答复!祝您学业进步!
为您推荐：
其他类似问题
用辗转相除法求568和1065的最大公因数 5-568=497 568>497,568-497=71 497-7*71=0 所以568和1065的最大公因数是71.数学辅导，Q，Q
扫描下载二维码用辗转相除法求与的最大公约数时，需做的除法次数为A．3B．4C．5D．6您好，您目前使用的浏览器版本比较旧，无法使用学优题库的新功能，建议您更换firefox或chrome浏览器学优网，成就我的梦想。 |
| 题文用辗转相除法求与的最大公约数时，需做的除法次数为A．3B．4C．5D．6&&&微信扫描左侧二维码，可以将本题分享到朋友圈，或者发送给同学或老师寻求帮助。纠错难度评价：做题心得：官方解析我要解析巩固&&&&&&&&&}