精华内容
下载资源
问答
  • 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。 这个题目我最初的理解理解错了,自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码...
  • 辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的: 21 / 12 = 1 (余 9) 12 / 9 = 1(余 3) 9 / 3...

    辗转相除法数学原理

    辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的:
    21 / 12 = 1 (余 9)
    12 / 9 = 1(余 3
    9 / 3 = 3 (余 0)
    至此,得到21与12的最大公约数为3(注意:这里的3是第二个式子取余得到的3,而非最后一个式子相除得到的),然后把两个数相乘再除以最大公约数就可以得到最小公倍数:(21*12)/ 3 = 84

    python代码实现

    接下来我们用python代码来实现这样一道题目:

    	题目:输入两个正整数,求其最大公约数和最小公倍数。
    
    def func(m,n):
        a = m
        b = n
        # 默认m>n,若不是,则交换
        if m < n:
            m,n = n,m
        while n != 0:
            # 对m除n取余
            r = m % n
            m = n
            n = r
        return m,(a*b)/m
    
    print("正整数m与n的最大公约数与最小公倍数分别为:",func(12,21))
    
    正整数m与n的最大公约数与最小公倍数分别为: (3, 84.0)
    

    用递归的方式实现

    def rec(m,n):
        # 默认m>n,若不是,则交换
        if m < n:
            m,n = n,m
        # 终止条件    
        if n == 0:
            return m,(a*b)/m
        # 递归部分
        return rec(n,m%n)
    
    a = 12
    b = 21
    print("正整数m与n的最大公约数与最小公倍数分别为:",rec(12,21))
    
    正整数m与n的最大公约数与最小公倍数分别为: (3, 84.0)
    
    展开全文
  • 辗转相除法:又称欧几里得算法辗转相除法python实现: #辗转相除法求解最大公约数 def Toss_and_Divide_method(m,n): #m和n中有一个为0时,循环结束 while m * n != 0: #若m>n则m为m/n的余数 #若m<...

    最大公约数:指两个或多个整数共有约数中最大的一个。

    辗转相除法:又称欧几里得算法。

    辗转相除法的python实现:

    #辗转相除法求解最大公约数
    def Toss_and_Divide_method(m,n):
        #m和n中有一个为0时,循环结束
        while m * n != 0:
            #若m>n则m为m/n的余数
            #若m<n则m还为m
            m = m % n
            #如果m被n整除,说明n就是最大公约数
            if m == 0:
                return n
            else:
                #若未整除,则倒过来用n/m取余
                n = n % m
                #如果n被m整除,说明m就是最大公约数
                if n == 0:
                    return m

     

    参考:https://blog.csdn.net/qq_41575507/article/details/90752742

    展开全文
  • 又称辗转相除法 算法描述:给定两个正整数m和n,求他们的最大公因子,即能够同时整除m和n的最大正整数。 算法步骤: 若m&lt;n,那么m↔n,为了确保m&gt;n。 求m除以n得到的余数r。 若r为0,算法结束,...

    greatest common divisor

    又称辗转相除法

    算法描述:给定两个正整数m和n,求他们的最大公因子,即能够同时整除m和n的最大正整数。

    算法步骤:

    1. 若m<n,那么m↔n,为了确保m>n。
    2. 求m除以n得到的余数r。
    3. 若r为0,算法结束,n为答案。
    4. 若r不为0,则m←n,n←r,再跳转到步骤2。

    其中←为赋值符号,右边的值赋值给左边; ↔为交换符号,两个变量交换它们的值。

    算法正确性证明:

    在经过步骤1,2之后,m,n,r满足下列关系:

    m=qn+r

    其中q是使等式成立的一个整数。比如42=2*20+2。

    如果r=0,那么m是n的倍数,所以n是m和n的最大公因子;如果r≠0,那么整除m和n的任何数也一定整除r=m-qn(可以想象假设某个公因子是e,那么e的整数倍减去e的整数倍,得到的结果还是e的整数倍),所以{m,n}和{n,r}的公因子集合是一样的。所以m←n,n←r是合理的,又因为r是m除以n的余数,所以r<n,那么算法是收敛的。

    算法实现(python):

    m=int(input("Please input a number m"))
    n=int(input("Please input a number n"))
    #step 1
    if m<n:
        _t=m
        m=n
        n=_t
    
    def gcd(m,n):
        #step 2
        _r=m % n
    
        #step 3
        if _r==0:
            return n
    
        #step 4
        else:
            m=n
            n=_r
            return gcd(m,n)
    if __name__=="__main__":
        print(gcd(m,n))
        
    
    

    现在已经有了实现求最大公约数的算法,只需要稍微修改一下就可以求最小公倍数(Least Common Multiple)了。因为假设m和n的最大公约数是r,用字母c表示最小公倍数,就有:

    c=m*n/r

    代码如下:

    def lcm(m,n):
        return int(m*n/gcd(m,n))
    

    参考文献:

    计算机程序设计艺术(The Art of Computer Programming),作者Donald Knuth

    展开全文
  • 辗转相除法辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。 例如,求(319,377): ∵ 319÷377=0(余319) ∴(319,377)=(377,319); ∵ 377÷319=1(余58) ∴(377,319)=...

    首先介绍下辗转相除法:

    辗转相除法

    辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法

    例如,求(319,377):

    ∵ 319÷377=0(余319)

    ∴(319,377)=(377,319);

    ∵ 377÷319=1(余58)

    ∴(377,319)=(319,58);

    ∵ 319÷58=5(余29)

    ∴ (319,58)=(58,29);

    ∵ 58÷29=2(余0)

    ∴ (58,29)= 29;

    ∴ (319,377)=29。

    可以写成右边的格式。

    用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。

    python实现:

    a,b=map(int,input("请输入两个数:").split())
    r=a%b
    while(r>0):
        a,b=b,r
        r=a%b
    print("最大公约数为:",b)

     

    展开全文
  • 求最大公约数的方法有很多,其中辗转相除法就是其中一种,是已知最古老的算法。 其算法步骤为: 1.大数除小数,如果能整除,那么小数就是所求的最大公约数 2.若不能整除,则用上一步的余数来除上一步的除数,所得...
  • 欧几里得算法求最大公约数:辗转相除法 具体做法:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除除数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,...
  • python编程:欧几里得算法又称辗转相除法,用于计算两个非负整数a,b的最大公约数。假如需要求1997和615两个正整数的最大公约数,用欧几里得算法,是这样的 至此,最大公约数为1 以除数和余数反复做除余运算,当余数...
  • Python3】20.辗转相除法

    千次阅读 2019-07-10 21:40:59
    1.算法定义为:在有限的步骤内解决数学问题的程序,即为了解决某项工作或某个问题,所需要有限数量的机械性或重复性指令与计算步骤。 2.最大公约数:可整除两个整数的最大整数。 3.用两个数中较大的整数除以较小的数...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 这是一个 Python 写的求最大公约数的算法。a = 12 b= 42def find_divisor(a,b): if a tmp = b b=a a=tmp while b!=0: r = a%b a = b b = r return aprint find_d
  • 刚好复习一下怎么求最大公约数,大一上学python的时候想破脑袋都做不出来的题目,现在想想当初的自己是真的菜。。 Problem B: 深入浅出学算法001-求最大公约数 Time Limit: 1 Sec Memory Limit: 64 MB Submit: 3982 ...
  • 欧几里德算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的: 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 =...
  • python算法

    2021-02-04 20:40:03
    算法:“为了解决某项工作或某个问题,所需要有限数量的机械性或重复性指令与计算步骤” 程序源自 ...#GCD辗转相除法求最大公约数 2021/02/04 20:40 if num_1<num_2: temp=num_1 num_1=num_2
  • python实现GCD算法

    千次阅读 2020-10-17 16:46:03
    1、辗转相除法: 已知a,b,c为正整数,若a除以b余c,则GCD(a,b)=GCD (b,c)。 2、更相减损术: 任意给定两个正整数,若是偶数,则用2约简。 以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。 ...
  • 最大公约数:辗转相除法 算法思想: 反复取除数作为被除数,余数作为除数,做除法运算。当余数为 0 时,取当前算式除数为最大公约数。 :param m_n: 包含两个整数的元组 :return: 两个整数的最大公约数
  • 扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。因此,有两个数a,b,对它们...
  • # Python 3.6 # 最大公约数,最大公因子 # Greatest Common ...# 辗转相除法 def gcd(num1: object, num2: object) -> object: print('num1={},num2={},r={}'.format( num1, num2, num1 % num2 ) ) ...
  • # Python 3.6# 最大公约数,最大公因子# Greatest Common Divisor# 辗转相除法def gcd(num1: object, num2: object) -> object:print("num1={},num2={},r={}".format( num1, num2, num1 % num2 ) )if num1...
  • 我知识浅薄,一开始被“欧几里德”的大名唬住了,去搜了一下才知道这就是高中时学过的“辗转相除法辗转相除法的用处 求两个正整数的最大公约数 示例 a = 30,b = 18,求 a 与 b 的最大公约数 a % b = 12 =>...
  • 欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。 其计算原理依赖于下面的定理: 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 最大公约数(greatest common ...
  • 欧几里得算法:“在数学中,辗转相除法,又称欧几里得算法(Euclidean algorithm),是求最大公约数的算法辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的...
  • 欧几里得算法证明及python实现

    千次阅读 2018-10-27 18:48:50
     欧几里得算法又称辗转相除法,是求两个整数的最大公约数非常有效的算法,具体内容是:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 2.欧几里得算法证明 :   a可以表示成a = kb + r...

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

python辗转相除法算法

python 订阅