【蓝桥杯学习笔记】2. 常用模型----最大公约数和最小公倍数

【蓝桥杯学习笔记】2. 常用模型----最大公约数和最小公倍数 系列文章目录

【蓝桥杯学习笔记】1. 入门基本语法及练习题

---

文章目录

系列文章目录前言一、最大公约数二、最小公倍数总结

---

前言

 蓝桥本笔记-----从入门到放弃

 本片文章使用Python语言编写----Now is better than never

---

一、最大公约数

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

1.两个数的情况：

import math
math.gcd(54,24) # 6

2.多个数的情况：

    思路（递归的方法）：就是把多个数当做数组，然后左右分半，把左半边数组的最大公约数和右半边数组的最大公约数，这两个数求一次最大公约数即可。（假定左半边的和右半边的是可求）。

def multi_gcd(array):
    L = len(array)
    if L == 1:
        return array[0]
    elif L == 2:
        return math.gcd(array[0], array[1])
    else:
        return math.gcd(multi_gcd(array[:L//2]), multi_gcd(array[L//2:]))

a = [46, 28, 50, 12, 8, 50, 48, 38, 32, 52, 38, 36, 48, 10, 28, 28, 20, 50, 22, 38, 34]
print(multi_gcd(a))  

运行结果： 

二、最小公倍数

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数

1.两个数情况

代码如下（示例）：

import math
math.lcm(54,24)

2多个数情况

    思路（递归的方法）：就是把多个数当做数组，然后左右分半，把左半边数组的最大公约数和右半边数组的最大公约数，这两个数求一次最大公约数即可。（假定左半边的和右半边的是可求）。

代码如下（示例）：

def multi_gcd(array):
    L = len(array)
    if L == 1:
        return array[0]
    elif L == 2:
        return math.gcd(array[0], array[1])
    else:
        #print(array[:L//2],'---',array[L//2:])
        return math.gcd(multi_gcd(array[:L//2]), multi_gcd(array[L//2:]))

a = [46, 28, 50, 12, 8, 50, 48, 38, 32, 52, 38, 36, 48, 10, 28, 28, 20, 50, 22, 38, 34]
print(multi_gcd(a))  

结果如下： 

---

总结

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

math.gcd(x，y) 

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数

math.lcm(54,24)

   求解多个数情况：思路（递归的方法）------就是把多个数当做数组，然后左右分半，把左半边数组的最大公约数和右半边数组的最大公约数，这两个数求一次最大公约数即可。（假定左半边的和右半边的是可求）。