文件名称:计算两个整数的最大公约数
文件大小:2.64MB
文件格式:RAR
更新时间:2015-03-24 10:18:41
欧几里得算法 连续整数检测算法 中学里计算过程
计算两个整数的最大公约数 1、用于计算gcd(m,n)的欧几里得算法 第一步:如果n=0,返回m的值作为结果,同时过程结束;否则,进入第二步。 第二步:m除以n,将余数赋给r。 第三步:将n的值赋给m,将r的值赋给n,返回第一步。 2、用于计算gcd(m,n)的连续整数检测算法 第一步:将min(m,n)的值赋给t。 第二步:m除以t,如果余数为0,进入第三步;否则,进入第四步。 第三步:n除以t,如果余数为0,返回t的值作为结果;否则,进入第四步。 第四步:把t的值减1。返回第二步。 3、中学里计算gcd(m,n)的过程 第一步:找出m的所有质因数。 第二步:找出n的所有质因数。 第三步:从第一步和第二步求得的质因数分解式中找出所有的公因数(如果p是一个公因数,而且在m和n的质因数分解式中分别出现过pm和pn次,那么应该将p重复min{pm,pn}次)。 第四步:将第三步中找到的质因数相乘,其结果作为给定数字的最大公约数。
【文件预览】:
Exp01
----Exp01.dsw(922B)
----Exp01_1()
--------Exp01_1.plg(1KB)
--------Exp01_1.cpp(681B)
--------Exp01_1.dsp(4KB)
--------Debug()
----Exp01.opt(63KB)
----Exp01_3()
--------Exp01_3.cpp(3KB)
--------Exp01_3.dsp(4KB)
--------Exp01_3.plg(1KB)
--------Debug()
----Exp01.ncb(57KB)
----Exp01_2()
--------Exp01_2.plg(248B)
--------Exp01_2.dsp(4KB)
--------Exp01_2.cpp(809B)
--------Debug()