精华内容
下载资源
问答
  • 主要介绍了Python基于更相减损术实现求解最大公约数的方法,简单说明了更相减损术的概念、原理并结合Python实例形式分析了基于更相减损术实现求解最大公约数的相关操作技巧与注意事项,需要的朋友可以参考下
  • 更相减损术

    2021-05-20 17:11:04
    本词条缺少概述图,补充...中文名更相减损术别名中华更相减损术类型数学算术出处《九章算术》用途求最大公约数原用途分数的约分作用适用任何需要求最大公约数的场合更相减损术思想编辑《九章算术》是中国古代的数...

    本词条缺少概述图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!

    更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

    中文名

    更相减损术

    别    名

    中华更相减损术

    类    型

    数学算术出    处

    《九章算术》

    用    途

    求最大公约数

    原用途

    分数的约分

    作    用

    适用任何需要求最大公约数的场合

    更相减损术思想

    编辑

    《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,原文是:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

    白话文译文:

    (如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

    更相减损术使用步骤

    编辑

    第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

    则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

    其中所说的“等数”,就是公约数。求“等数”的办法是“更相减损”法。

    更相减损术实例

    编辑

    例1、用更相减损术求98与63的最大公约数。

    解:由于63不是偶数,把98和63以大数减小数,并辗转相减:

    98-63=35

    63-35=28

    35-28=7

    28-7=21

    21-7=14

    14-7=7

    所以,98和63的最大公约数等于7。

    例2、用更相减损术求260和104的最大公约数。

    解:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26。

    此时65是奇数而26不是奇数,故把65和26辗转相减:

    65-26=39

    39-26=13

    26-13=13

    所以,260与104的最大公约数等于13乘以第一步中约掉的两个2,即13*2*2=52。

    更相减损术证明

    编辑

    设gcd(x,y)=d,则满足x=k1*d,y=k2*d,易得k1与k2互质。

    情况1:x=y。显然,gcd(x,y)=x=gcd(x,0)=gcd(x,y-x)。

    情况2:不妨令x

    用反证法。

    假设k1,(k2 - k1)不互质,

    令gcb(k1.k2-k1) = m(m为正整数且m>1);

    k1 = m*a,k2 - k1 = m*b

    k2 = (a+b)m

    即k1,k2有公约数m,与k1,k2互质矛盾

    所以假设不成立

    即k1,(k2 - k1)互质

    所以gcb(x,x-y) = d = gcb(x,y)

    综上,gcd(x,y)=gcd(x,y-x)。

    命题得证

    当然,此结论可用数学归纳法推广到一般,该性质对多个整数都成立。

    即:gcd(x,y,z,...)=gcd(x,y-x,z-y,...)。

    直观证明:

    对于gcd(x,y,z)=gcd(x,y-x,z-y):

    gcd(x,y,z)=gcd(x,gcd(y,z))=gcd(x,gcd(y,z-y))=gcd(x,y,z-y)=gcd(gcd(x,y),z-y)=gcd(gcd(x,y-x),z-y)=gcd(x,y-x,z-y)。

    更多项依次类推。

    更相减损术比较

    编辑

    辗转相除法也可以用来求两个数的最大公约数。

    更相减损术和辗转相除法的主要区别在于前者所使用的运算是“减”,后者是“除”。从算法思想上看,两者并没有本质上的区别,但是在计算过程中,如果遇到一个数很大,另一个数比较小的情况,可能要进行很多次减法才能达到一次除法的效果,从而使得算法的时间复杂度退化为O(N),其中N是原先的两个数中较大的一个。相比之下,辗转相除法的时间复杂度稳定于O(logN)。

    更相减损术Stein算法

    编辑

    更相减损法有点类似于求最大公约数的Stein算法。在更相减损法中,若两个是偶数则同除以2,结果乘以2。如果增加一个判断,若为一奇一偶则偶数除以2,结果不变,若为两个奇数才相减,这样就变成了计算大整数最大公约数的非常好的一个算法,Stein算法。

    在上面的实例中,下面是更相减损法与Stein算法的比较,从中可以发现两种算法的相似性。Stein 算法与更相减损术的操作流程

    更相减损法:操作甲数乙数甲数乙数

    98639863

    98-63=35633598是偶数,除以24963

    63-35=283528都是奇数,63-49=144914

    35-28=728714是偶数,除以2497

    28-7=2172149-7=42427

    21-7=1471442是偶数,除以2217

    14-7=77721-7=14147

    7-7=07014是偶数,除以277

    7-7=070

    更相减损术“可半者半之”

    编辑

    通常认为,算法描述中的第一步“可半者半之”是指分子分母皆为偶数的时候,首先用2约简。因为更相减损术原先是专用来约分,所以并不用考虑最后计算结果时,要把第一步中约掉的若干个2再乘回去。加入这一步的原因可能是,分母、分子皆为偶数是在分数加减运算的结果中比较容易遇到的一种情况,用这种方法有可能减少数字的位数,简化计算。

    当然,省略这个以2约简的步骤,也能得到正确的答案。

    更相减损术电脑

    编辑

    更相减损术Basic

    INPUT "m,n=";m,n

    i=0

    WHILE m MOD 2=0 AND n MOD 2=0

    m=m/2

    n=n/2

    i=i+1

    WEND

    DO

    IF m

    r=m

    m=n

    n=r

    END IF

    m=m-n

    LOOP UNTIL m=0

    PRINT “m、n的最大公约数为”;n*2ˆi

    END

    (i=i+1部分可以省略,因为,不进行约简,一样可以求出)

    更相减损术python

    # 更相减损法,求最大公约数

    def gcf(a, b):

    # 减少倍数

    reduction = 1

    while True:

    # 可半者半之

    if a % 2 == 0 and b % 2 == 0:

    a //= 2

    b //= 2

    reduction *= 2

    else:

    # 不可半者

    break

    while True:

    # 副置分母、子之数,以少减多,更相减损,求其等也

    big = max(a, b)

    small = min(a, b)

    if small * 2 == big:

    return small * reduction

    else:

    a, b = small, big - small

    更相减损术C语言

    #include 

    int main()

    {

    int a,b;

    scanf("%d%d",&a,&b);

    while(a != b)

    { if(a > b)a -= b;

    else b -= a;

    }

    printf("m、n的最大公约数为%d",a);

    return 0;

    }

    更相减损术C++

    //非递归形式:

    #include 

    using namespace std;

    int main()

    {

    int a,b;

    cin>>a>>b;

    while(a != b)

    {

    if(a > b)

    a -= b;

    else

    b -= a;

    }

    cout<

    return 0;

    }//递归形式:

    #include 

    using namespace std;

    //下面这个gcd函数在正int型内完全通用,返回a,b的最大公因数。

    //但是当a,b之间差距较大时(如100000倍)会导致错误(栈过深)

    int gcd(int a,int b){

    if(a==b)return a;

    else if(a>b)a-=b;

    else b-=a;

    return gcd(a,b);

    }

    int main(){

    int a,b;

    cin>>a>>b;

    cout<

    return 0;

    }

    展开全文
  • 辗转相除法, 又名欧几里德算法Euclidean algorithm乃求两数之最大公因数算法它是已知最古老的算法, 其可追溯至前300年它首次出现于欧几里德的几何原本中而在中国则可以追溯至东汉出现的九章算术它并不需要把二数作质...
  • 「@Author:Runsen」❝编程的本质来源于算法,而算法的本质来源于数学,编程只不过将...高中数学在必修三中,有一个非常重要的知识点,叫做「碾转相除法、更相减损术」。辗转相除法, 又名欧几里德算法(Euclidean a...

    「@Author:Runsen」❝

    编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。「---- Runsen」❞

    先问你们一个小学问题:「如何求两个整数的最大公约数?」

    曾经见过不少的算法题,发现有的并不在数据结构和算法大纲中,而是来源于高中数学。

    高中数学在必修三中,有一个非常重要的知识点,叫做「碾转相除法、更相减损术」。

    辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至公元前300年前。

    在古代,有一个比较出名的数学家,叫做「刘徽」。而更相减损术是我国数学家刘徽的专著《九章算术》中记载的.

    碾转相除法

    辗转相除是求最大公约数的一种算法。给两个数,我们可以把它组成数对(a,b)

    辗转相除法基于如下原理:「两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。」

    求a和b的最大公约数,就用ab中较小的数去除另一个数,这个时候会有一个余数,当余数是0的时候,那个较小的数就是最大公约数。

    若余数不是0,那么我们用这个余数来替换那个比较大的数,然后以此类推,直到算出最大公约数。

    比如,下面我用碾转相除法求100和24的最大公约数,很明显最大公约数就是25。100 = 24 * 4  + 4

    24  =  4 * 6  + 0

    很显然4和6中,那个较小的数4就是100和24最大公约数。

    下面用碾转相除法求55和120的最大公约数,很明显最大公约数就是5。55 = 120 * 0  + 55

    120  =  55 * 2  + 10

    55 = 10 * 5 + 5

    很显然10和5中,那个较小的数5就是55和120最大公约数。

    db42eaa28f4d697aa0cbcc503cd4a81f.png算法的流程图(摘自百度百科)

    因此得到设两数为m,n,这里不需要判断两数中谁最大。

    求m,n两数的最大公约数的步骤为:

    用m除以n,m%n=r(r>=0)。如果r=0,则min(m,n)。

    如果r≠0,用n除以r,依此循环,直到r=0结束

    下面,我们将使用对碾转相除法进行代码化。def gcd(a, b):

    # 如果b是0,退出循环

    while b:

    # 循环赋值

    a, b = b, a%b

    return a

    print(gcd(100,25)) #25

    辗转相除法本质上是一种递归的代码,把求两个大数的公约数gcd(a,b)转化为 求其中较小的数和两数的相除余数的最大公约数gcd(b,a%b),直至b为0,则返回a为求得的最大公约数gcd(gcd(a,b), 0)。

    因此可以得到:gcd(a,b) = gcd(b,a%b) = gcd(gcd(a,b), 0)def gcd(a, b):

    return gcd(b, a % b) if b != 0 else a

    print(gcd(55,120)) #5

    下面对Python代码进行Java的代码转化/**

    * @author Runsen

    * @date 2020/12/9 13:18

    */

    public class Gcd{

    public static void main(String[] args){

    int gcd = gcd(91, 49);

    System.out.println(gcd);

    }

    private static int gcd(int a, int b){

    while(b != 0) {

    int temp = a % b;

    a = b;

    b = temp;

    }

    return a;

    }

    }

    下面对Python代码进行JavaScript的代码转化。function gcd(a, b){

    while(b != 0){

    temp = a % b;

    a = b;

    b = temp;

    };

    return a;

    }

    console.log((gcd(55,120))) #5

    更相减损术

    我国早期也有求最大公约数问题的算法,就是更相减损术。

    在《九章算术》中有更相减损术求最大公约数的步骤:可半者半之,不可半者,副置分母子之数,以少减多,更相减损,求其等也,以等数约之。

    更相减损术来源于数的整除性质:即如果两个整数a、b都能被c整除,那么a与b的差也能被C整除。

    比如求98和63的最大公约数。

    先看98和63这两个数,因为63不是偶数,所以用大数减去小数,得到98-63=35 , 63-35=28 35-28=7 , 28-7=21 , 21-7=14 , 14-7=7 。

    「此时,减数和差相等7」,所以98和63的最大公约数是7。

    再比如求260和104的最大公约数。

    先看260和104两个数,这两个数都是偶数,所以用2约简得130和52。

    约简之后的130和52也都是偶数,继续用2约简得65和26,此时65不是偶数,所以用大数减去小数 65-26=39 , 39-26=13 , 26-13=13。

    此时,减数和差相等,再上面约去2个2, 得到的数是13,所以260和104的最大公约数是2×2×13=52。

    因此更相减损术不在如下:如果两个整数都是偶数,就使用2约简,直到两个整数不再都是偶数,然后执行第2步。如果两个整数不都是偶数,则直接执行第2步。

    用较大的数减去较小的数,如果得到的差恰好等于较小的数,则停止。否则,对较小的数和差值重复这个过程。

    第1步中约掉的若干个2和第2步中得到的差的乘积为原来两个整数的最大公约数。

    94283a5079cf7c6bcd54a580f7f945d8.png

    下面,我们将使用对更相减损术进行代码化。'''

    @Author:Runsen

    @WeChat:RunsenLiu

    @微信公众号:Python之王

    @CSDN:https://blog.csdn.net/weixin_44510615

    @Github:https://github.com/MaoliRUNsen

    @Date:2020/12/9

    '''

    def MaxCommDivisor(m, n):

    # 如果两个整数都是偶数,就使用2约简,需要记录约简次数

    index = 1

    while m % 2 == 0 and n % 2 == 0:

    m = m / 2

    n = n / 2

    index = index * 2

    # 用较大的数减去较小的数,因此需要判断m和n的大小,确保m是最大的。

    if m 

    m, n = n, m

    # 用较大的数减去较小的数,如果得到的差恰好等于较小的数,则停止。否则,对较小的数和差值重复这个过程。

    while m - n != n:

    diff = m - n

    if diff > n:

    m = diff

    else:

    m = n

    n = diff

    return n * index

    print(MaxCommDivisor(24, 12)) #12

    更相减损术和辗转相除法在一千多年前的东方和西方同时被提出,这说明天才的想法总是惊人的相似,人类科技文明的进程也是同步的,这就是算法之美。❝

    本文已收录 GitHub,传送门~[1] ,里面更有大厂面试完整考点,欢迎 Star。❞

    Reference[1]

    传送门~:https://github.com/MaoliRUNsen/runsenlearnpy100

    - END -

    展开全文
  • C语言 用更相减损术求最大公约数,最小公倍数

    千次阅读 多人点赞 2019-02-03 20:56:58
    更相减损术 更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。 出处 《九章算术》 用途 求最大公约数 作用 适用任何需要求最大公约数...

    更相减损术
    更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。

    出处
    《九章算术》
    用途
    求最大公约数
    作用
    适用任何需要求最大公约数的场合

    思想
    《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,原文是:
    可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

    白话文译文:
    (如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。

    使用步骤
    第一步:任意给定两个正整数;判断它们是否都是偶数。
    若是,则用2约简;见例2
    若不是则执行第二步。见例1
    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
    其中所说的“等数”,就是最大公约数。求“等数”的办法就是“更相减损”法。
    简述为:
    有两整数a和b:

    ① 若a>b,则a=a-b

    ② 若a<b,则b=b-a

    ③ 若a=b,则a(或b)即为两数的最大公约数

    ④ 若a≠b,则再回去执行①

    例如求27和15的最大公约数过程为:

    27-15=12( 15>12 ) 15-12=3( 12>3 )

    12-3=9( 9>3 ) 9-3=6( 6>3 )

    6-3=3( 3==3 ),多次重复辗转相减,(重复操作用循环) 若a=b,则a(或b)即为两数的最大公约数。
    先有个大概的了解,再结合代码,来细细体会。
    在这里插入图片描述

    #include<stdio.h> 
    main()
    {	int a,b,num1,num2;
    	printf("请输入这两个数:");
    	scanf("%d %d",&a,&b);
    	num1=a,num2=b;//在判断之前先把a,b存放在num1,num2里,求最小公倍数 
    	//	printf("a、b的最小公倍数为:%d",num1*num2/a);错在哪儿?错在最小公倍数的算法不知道 
    	while(a!=b)/* a, b不相等,大数减小数,直到相等为止。*/ 
    	{
    	if(a>b)
    	a-=b;
    	else
    	b-=a;
    	}//a==b结束循环,根据更相减损术,若a==b,则a(或b)即为两数的最大公约数。
    	printf("a、b的最大公约数为:%d\n",a);
    	printf("a、b的最小公倍数为:%d",num1*num2/a);//最小公倍数=两整数的乘积÷最大公约数
    }
    

    知识小补丁:
    求最小公倍数算法:
    最小公倍数=两整数的乘积÷最大公约数

    求最大公约数算法:
    (1)辗转相除法

    #include <stdio.h>
    //程序分析:利用辗除法。
    int main()
    {   int a,b,num1,num2,temp;
    	printf("please input two number:\n");
    	scanf("%d%d",&num1,&num2);
    	if(num1<num2)//比较大小,大做分母,小做分子
        {   temp = num1;//这是两个数比大小的经典算法
    		num1 = num2;
    		num2 = temp;
    	}
    	a = num1;//小者给a
    	b = num2;//大者给b
    	while(b!=0)/*利用辗除法,直到b为0为止*/
    	{   temp = a%b;//这是重复取余的操作
    		a=b;
    		b=temp;
    	}
    	printf("公约数:%d\n",a);
    	printf("公倍数:%d\n",num1*num2/a);
    }
    

    利用辗除法求最大公约数和最小公倍数:https://blog.csdn.net/YJG7D314/article/details/86760128

    (2)更相减损术
    例1、用更相减损术求98与63的最大公约数。
    解:由于63不是偶数,把98和63以大数减小数,并辗转相减:
    98-63=35
    63-35=28
    35-28=7
    28-7=21
    21-7=14
    14-7=7
    所以,98和63的最大公约数等于7
    在这里插入图片描述

    例2、用更相减损术求260和104的最大公约数。
    解:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26。
    此时65是奇数而26不是奇数,故把65和26辗转相减:
    65-26=39
    39-26=13
    26-13=13
    所以,260与104的最大公约数等于13乘以第一步中约掉的两个2,即1322=52。
    在这里插入图片描述

    展开全文
  • 欧几里得算法和更相减损术证明

    千次阅读 2019-06-21 10:43:56
    更相减损术 不妨设A>B,设A和B的最大公约数为X,所以 A=aX,B=bx,其中a和b都为正整数,且a>b。 C = A-B,则有: C=aX−bX=(a−b)X 因为a和b均为正整数,所以C也能被X整除,即A、B、C最大公约数均为X 所以gcd...

    欧几里得算法
    gcd(greatest common divisor) 最大公约数,指两个整数所有公共约数中最大的。
    首先先上结论,求最大公约数,我们可以通过递归c=a%b,gcd(a,b)=gcd(b,c),c=0时返回b计算,复杂度是log(n)
    很明显,这个伟大的结论gcd(a,b)=gcd(b,a%b),就是著名的欧几里得公式。
    那么怎么证,其实还挺简单的。我们把证明分为两步骤:

    • 1、证明gcd(a,b)是b,a%b的一个公约数
    • 2、证明这个公约数是最大的。

    1、我们设gcd(a,b)=d,a>b,再令a=k1d,b=k2d.
    我们再设,a=kb+c(也就是a除以b商k余c),那么c就是余数,也就是a%b.
    将上面那个式子移项,得到c=a-k
    b,然后再把a=k1d,b=k2d,这两个式子里的a、b带入式子,得到:
    c=k1d-kk2d,再提取公因数d,得到c=(k1-kk2)d.这样就说明,c(也就是a%b)有d这个约数,因为开始我们设b也有d这个约数,所以gcd(a,b)是b,a%b的一个公约数。
    2、现在知道了它是一个公约数,那么怎么证它是最大的?(其实感性分析,a%b都变小了,公约数不可能更大呀!)
      但是数学是一门严谨的学科,我们要严谨证明。我们知道,c(a%b)=(k1-k
    k2)d,b=k2d,我们只需要证明k1-kk2、k2互质就好了。
    这里可以用到反证法:我们假设k1-k
    k2=qt,k2=pt,并且t>1(也就是那两个不互质)。
    我们将前面那个式子移项,得到k1=qt+kk2,再把这个k1代到最开始的a=k1d,得到a=(qt+kk2)d,再利用乘法分配律,得到:
      a=q
    t
    d+kk2d,这时,我们再把k2=pt带入上式,得到a=qtd+kptd.提取公因数:a=(q+kp)td
      现在,再和b=ptd比较,发现他们的最大公因数变成了t*d和开始矛盾,所以假设不成立,反证成功!
    更相减损术
    不妨设A>B,设A和B的最大公约数为X,所以 A=aX,B=bx,其中a和b都为正整数,且a>b。
    C = A-B,则有:
    C=aX−bX=(a−b)X

    因为a和b均为正整数,所以C也能被X整除,即A、B、C最大公约数均为X
    所以gcd(A,B) = gcd(B,A-B)

    展开全文
  • cout更相减损术 主要思想: 与辗转相除法类似,用较大数减去较小数,若不为零,则用减数减去所得结果,如此循环。 代码如下: int gcd (int a,int b){ if (a-b!=0) return gcd(b,a-b); else return b; } //此处省略...
  • 更相减损术求gcd

    2020-03-05 17:09:46
    可半者半之 16,24 ----- 8 ,12 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<string> ......
  • 辗转相除法:两个正整数a和b(a&gt;b),它们的最大公约数等于a除以b的余数c...更相减损术:两个正整数a和b(a&gt;b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25,25减去10的差是...
  • Java作业——求最大公约数——更相减损术 虽然算法简单,但是因为很不熟练,所以一开始的代码有较多错误,以下是经过多次修改后的代码。 代码: package homework3.GreatestCommonDivisor; import java.util....
  • 具体算法思路可见百度百科,代码如下: #include<iostream> #include<algorithm> using namespace std; int f(int x,int y); int main() { int a,b; cin>>a>>b; ...
  • 辗转相除法和更相减损术

    千次阅读 2019-09-03 15:41:19
    高中学过的求大公约数的方法就是辗转相除法和更相减损术了。 辗转相除法递归版 #include <iostream> using std::cin; using std::cout; using std::endl; int gcd(int a, int b) { return b == 0 ? a : gcd(b...
  • 使用更相减损术求最大公约数

    千次阅读 2018-12-05 10:25:51
    * 使用更相减损术求最大公约数 * 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 * 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。...
  • 更相减损术是《九章算术》中给出的一种用于约分的方法,也可以用来计算最大公约数,其步骤为:1)如果两个整数都是偶数,就使用2约简,直到两个整数不再都是偶数,然后执行第2步。如果两个整数不都是...
  • 算法思想: 用较大的那个数减去较小的那个数,再用减数和差中,较大的那个减去较小的那个,重复这个过程,直到减数和差相等.减数就为最大公因数. #include <stdio.h> #include <stdlib.h>...
  • 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。...int get_common(int a,int b) //减损就是用大数减小数,再用减过后的数与之前较小数比较,再用大数减小数,直至...
  • 更相减损术出自我国著名算数书《九章算术》,原本是用于分数的约分,后多用来计算两个整数的最大公约数。 具体步骤: 第一步:给定两个正整数,判断是否为偶数,若是则用2简约,否则执行第二步。 第二步:以较大的数...
  • 3. 更相减损术 : 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,...
  • 数学:更相减损术

    2018-08-15 09:57:00
    利用更相减损术求两个大数的最大公约数 这个题我没有过。。BZOJ1876 原因有这么几个: 如果使用十进制高精度配合普通更相减损术之后会T4个点 如果使用十进制高精度配合优化之后的更相减损术会T7个点 如果使用万...
  • 求解两个int类型数字a, b的最大公约数的常用的办法一般有两种:第一种是辗转相除术,第二种是更相减损术,下面使用更相减损术求解最大公约数: 设A > B,A = ax, B = bx 则C = A - B = ax - bx,所以A、B、C的...
  • 九章算术更相减损术的的c语言实现

    千次阅读 2019-04-19 21:34:54
    《九章算术》中介绍了这个方法,叫做”更相减损术”,即“可半者半之,不可半者,副置分母、子之数,以少减多,相减损,求其等也。以等数约之。”  翻译成现代语言如下:  第一步:任意给定两个正整数;判断它们...
  • 更相减损术的问题是遇到差别很大的数据,比如99999和1的时候要互减99998次,这样显然不行,所以我们做一个改进,把上面两个方法的优势结合起来。 三、两种方法的结合 结合的规律是这样的: 1.如果a、b都是偶数...
  • 更相减损术 介绍 ​   更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合 步骤 任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简...
  • 相减损法:也叫 更相减损术,是出自《 九章算术》的一种求最大公约数的算法,它原本是为 约分而设计的,但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以...
  • 相减损法:也叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。 #include<stdio.h> int main() { int a, b; int count=1; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,466
精华内容 586
关键字:

更相减损术

友情链接: linedetection.rar