python辗转相除法求最大公约数和最小公倍数的实现

目录
  • 辗转相除法求最大公约数和最小公倍数
    • 辗转相除法数学原理
    • python代码实现
    • 用递归的方式实现
  • Python3 20.辗转相除法
    • 算法分析
    • 源代码
    • 结果截图

辗转相除法求最大公约数和最小公倍数

辗转相除法数学原理

辗转相除法也称欧几里得算法，是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求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)

Python3 20.辗转相除法

算法分析

1.算法定义为：在有限的步骤内解决数学问题的程序，即为了解决某项工作或某个问题，所需要有限数量的机械性或重复性指令与计算步骤。

2.最大公约数：可整除两个整数的最大整数。

3.用两个数中较大的整数除以较小的数，求得商和余数。

源代码

# coding:gbk
Num_1 = int(input("请输入一个整数： "))
Num_2 = int(input("请输入一个整数： "))

if Num_1 < Num_2:
	Tmp_Num = Num_1       # 是交换而不是赋值
	Num_1 = Num_2
	Num_2 = Tmp_Num

while Num_2 != 0:
	Tmp_Num = Num_1 % Num_2
	Num_1 = Num_2
	Num_2 = Tmp_Num

print('输出这两个整数的最大公约数：', Num_1)

结果截图

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python自定义函数实现求两个数最大公约数、最小公倍数示例

    Python自定义函数实现求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python自定义函数实现求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 1. 求最小公倍数的算法: 最小公倍数  =  两个整数的乘积 /  最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: ① 整数A对整数B进行取整, 余数用整数C来表示    举例: C = A % B ② 如果C等于0,则C就是整数A和整数B的最大公约数 ③ 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2

  • Python实现求解最大公约数的五种方法总结

    目录 方法一:短除法 方法二:欧几里得算法(辗转相除法) 方法三:更相减损术 方法四:穷举法(枚举法) 方法五:Stein算法 求最大公约数是习题中比较常见的类型,下面小编会给大家提供五种比较常见的算法,记得帮忙点个赞哦! 一般来说,最大公约数的求法大概有5种 方法一:短除法 短除法是求最大公因数的一种方法,也可用来求最小公倍数.求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数.后来,使用分解质因数法来分别分解两个数的因

  • Python基于辗转相除法求解最大公约数的方法示例

    Python基于辗转相除法求解最大公约数的方法示例

    本文实例讲述了Python基于辗转相除法求解最大公约数的方法.分享给大家供大家参考,具体如下: 之前总结过一次高德纳TAOCP中的最大公约数求解,其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数. 这个题目我最初的理解理解错了,自然也没有做出标准答案.现在按照标准答案的解答写一下相应的代码实现: # -*- coding:utf-8 -*- #! python2 def MaxCommDivisor(m,n): while m * n != 0: m = m % n if m == 0

  • python辗转相除法求最大公约数和最小公倍数的实现

    python辗转相除法求最大公约数和最小公倍数的实现

    目录 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 python代码实现 用递归的方式实现 Python3 20.辗转相除法 算法分析 源代码 结果截图 辗转相除法求最大公约数和最小公倍数 辗转相除法数学原理 辗转相除法也称欧几里得算法,是用来求两个正整数的最大公约数的算法.接下来我们用实例来解释一下.假如我们需要求12和21的最大公约数,用辗转相除法是这样实现的: 21 / 12 = 1 (余 9) 12 / 9 = 1(余 3) 9 / 3 = 3 (余 0) 至此,得到21与12

  • python求最大公约数和最小公倍数的简单方法

    python怎么求最大公约数和最小公倍数 一.求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数.比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数. 具体代码如下: def gongyue(a, b): """ 欧几里得算法----辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 "

  • PHP编程求最大公约数与最小公倍数的方法示例

    本文实例讲述了PHP编程求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: //求最大公约数 function max_divisor($a,$b) { $n = min($a, $b); for($i=$n; $i>1; $i--) { if (is_int($a/$i)&&is_int($b/$i)) { return $i; //此处如果用echo $i;则输出结果为432:故应区分echo.return的区别 } } return 1; } //求最小公倍数 f

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • Python实现求最大公约数及判断素数的方法

    本文实例讲述了Python实现求最大公约数及判断素数的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python def showMaxFactor(num): count = num / 2 while count > 1: if num % count == 0: print 'largest factor of %d is %d' % (num, count) break #break跳出时会跳出下面的else语句 count -= 1 else: prin

  • java求最大公约数与最小公倍数的方法示例

    java求最大公约数与最小公倍数的方法示例

    本文实例讲述了java求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: Gongyueshu.java文件: package math; public class Gongyueshu { public static void main(String[] args) { //从控制台输入两个数据 int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); int y = 1 ; int b = 1;

  • 递归法求最大公约数和最小公倍数的实现代码

    数学原理:        设有两个数num1和num2,假设num1比较大.令余数r = num1 % num2.       当r == 0时,即num1可以被num2整除,显然num2就是这两个数的最大公约数.       当r != 0时,令num1 = num2(除数变被除数),num2 = r(余数变除数),再做 r = num1 % num2.递归,直到r == 0.       以上数学原理可以用具体的两个数做一下分析,这样容易理解.代码实现(求最大公约数): 复制代码 代码如下:

  • Java中使用辗转相除法求最大公约数

    比较好用的是辗转相除法. 比如:49和91  a      b        temp 49  %  91  =  49 91  %  49  =  42 49  %  42  =  7 42  %  7    =  0 所以最大公约数就是7. public class T { public static void main(String[] args) { int gcd = gcd(91, 49); System.out.println(gcd); } /** * greatest comm

  • JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象，回归迭代和循环】

    本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法.分享给大家供大家参考,具体如下: 方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来.最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) aj以外的所有其他非0项ak用ak mod aj代替:若没有除aj以外的其他非0项,则转到(4) (3) 转到(1) (4) a1,a2,..,an的最大公约数为aj 写

随机推荐