Khóa học Python từ Cơ bản đến Nâng cao

Bài 16.1. GCD và LCM trong Python

Chào các bạn! Trong thế giới toán học và khoa học máy tính, có hai khái niệm cơ bản nhưng cực kỳ quan trọng mà chúng ta thường xuyên gặp phải: Ước Chung Lớn Nhất (GCD) và Bội Chung Nhỏ Nhất (LCM). Python, với sự hỗ trợ mạnh mẽ từ thư viện chuẩn, giúp chúng ta làm việc với chúng một cách dễ dàng.

Hãy cùng khám phá cặp đôi khái niệm này và cách triển khai chúng trong Python nhé!

1. Ước Chung Lớn Nhất (GCD - Greatest Common Divisor)

Định nghĩa

Ước Chung Lớn Nhất (ƯCLN), hay GCD, của hai hay nhiều số nguyên (khác không) là số nguyên dương lớn nhất mà tất cả các số đó đều chia hết.

Ví dụ đơn giản: Các ước của 12 là: 1, 2, 3, 4, 6, 12. Các ước của 18 là: 1, 2, 3, 6, 9, 18. Các ước chung của 12 và 18 là: 1, 2, 3, 6. Vậy, ước chung lớn nhất (GCD) của 12 và 18 là 6.

Cách tính GCD trong Python

a) Sử dụng math.gcd() (Khuyến nghị)

Từ Python 3.5 trở đi, mô-đun math cung cấp sẵn hàm gcd() cực kỳ tiện lợi.

import math

# Tính GCD của 54 và 24
a = 54
b = 24
greatest_common_divisor = math.gcd(a, b)

print(f"GCD của {a} và {b} là: {greatest_common_divisor}")
# Kết quả: GCD của 54 và 24 là: 6

Giải thích code:

1. import math: Nhập mô-đun math để sử dụng các hàm toán học.
2. math.gcd(a, b): Gọi hàm gcd với hai số a và b làm đối số. Hàm này sẽ trả về ước chung lớn nhất của chúng.

Lưu ý: Kể từ Python 3.9, math.gcd() có thể nhận nhiều hơn hai đối số để tính GCD của nhiều số cùng lúc.

import math

# Tính GCD của 72, 108 và 48 (Yêu cầu Python 3.9+)
result = math.gcd(72, 108, 48)
print(f"GCD của 72, 108, 48 là: {result}")
# Kết quả: GCD của 72, 108, 48 là: 12

b) Tự triển khai thuật toán Euclid

Nếu bạn muốn hiểu sâu hơn hoặc đang sử dụng phiên bản Python cũ hơn (trước 3.5), bạn có thể tự viết hàm GCD dựa trên Thuật toán Euclid nổi tiếng. Thuật toán này dựa trên nguyên tắc: gcd(a, b) = gcd(b, a % b) cho đến khi b bằng 0, lúc đó gcd chính là a.

Đây là cách triển khai bằng vòng lặp while:

def compute_gcd(x, y):
  """Tính GCD của x và y bằng thuật toán Euclid (vòng lặp)."""
  while(y): # Lặp cho đến khi y bằng 0
    # Phép gán đồng thời: x nhận giá trị cũ của y, y nhận phần dư của x chia cho y
    x, y = y, x % y
  return abs(x) # Trả về giá trị tuyệt đối của x (đảm bảo GCD là dương)

# Ví dụ
a = 54
b = 24
gcd_manual = compute_gcd(a, b)
print(f"GCD (tự tính) của {a} và {b} là: {gcd_manual}")
# Kết quả: GCD (tự tính) của 54 và 24 là: 6

# Ví dụ khác
print(f"GCD (tự tính) của 48 và 18 là: {compute_gcd(48, 18)}") # Kết quả: 6
print(f"GCD (tự tính) của 17 và 5 là: {compute_gcd(17, 5)}")   # Kết quả: 1 (Số nguyên tố cùng nhau)

Giải thích code compute_gcd:

1. while(y):: Vòng lặp tiếp tục chạy miễn là y khác 0.
2. x, y = y, x % y: Đây là trái tim của thuật toán Euclid. Trong mỗi bước lặp, x cũ được thay bằng y cũ, và y cũ được thay bằng phần dư của x cũ chia cho y cũ (x % y). Điều này liên tục làm giảm giá trị của các số nhưng vẫn bảo toàn GCD.
3. return abs(x): Khi vòng lặp kết thúc (nghĩa là y bằng 0), x sẽ chứa GCD. Chúng ta lấy abs(x) để đảm bảo kết quả luôn dương, theo định nghĩa của GCD.

2. Bội Chung Nhỏ Nhất (LCM - Least Common Multiple)

Định nghĩa

Bội Chung Nhỏ Nhất (BCNN), hay LCM, của hai hay nhiều số nguyên (khác không) là số nguyên dương nhỏ nhất mà chia hết cho tất cả các số đó.

Ví dụ đơn giản: Các bội dương của 4 là: 4, 8, 12, 16, 20, 24, ... Các bội dương của 6 là: 6, 12, 18, 24, 30, ... Các bội chung dương của 4 và 6 là: 12, 24, ... Vậy, bội chung nhỏ nhất (LCM) của 4 và 6 là 12.

Cách tính LCM trong Python

a) Sử dụng math.lcm() (Khuyến nghị - Python 3.9+)

Tin vui là từ Python 3.9, mô-đun math cũng cung cấp hàm lcm()!

import math

# Tính LCM của 12 và 18 (Yêu cầu Python 3.9+)
a = 12
b = 18
least_common_multiple = math.lcm(a, b)

print(f"LCM của {a} và {b} là: {least_common_multiple}")
# Kết quả: LCM của 12 và 18 là: 36

# Tính LCM của nhiều số
result_lcm = math.lcm(4, 6, 8)
print(f"LCM của 4, 6, 8 là: {result_lcm}")
# Kết quả: LCM của 4, 6, 8 là: 24

Giải thích code:

1. import math: Nhập mô-đun math.
2. math.lcm(a, b, ...): Gọi hàm lcm với các số cần tính làm đối số. Hàm trả về bội chung nhỏ nhất.

b) Sử dụng công thức qua GCD

Nếu bạn đang dùng Python < 3.9 hoặc muốn hiểu bản chất, bạn có thể tính LCM thông qua GCD bằng công thức toán học sau:

$LCM(a, b) = \frac{|a \times b|}{GCD(a, b)}$

Trong đó |a * b| là giá trị tuyệt đối của tích a và b. Công thức này hoạt động vì nó loại bỏ các thừa số chung (đã được tính trong GCD) khỏi tích của hai số.

import math # Vẫn cần math cho hàm gcd()

def compute_lcm(x, y):
  """Tính LCM của x và y sử dụng công thức qua GCD."""
  if x == 0 or y == 0:
      return 0 # LCM của bất kỳ số nào với 0 là 0
  # Tính GCD trước
  gcd_val = math.gcd(x, y)
  # Áp dụng công thức LCM
  lcm_val = abs(x * y) // gcd_val # Dùng // để đảm bảo kết quả là số nguyên
  return lcm_val

# Ví dụ
a = 12
b = 18
lcm_manual = compute_lcm(a, b)
print(f"LCM (tự tính) của {a} và {b} là: {lcm_manual}")
# Kết quả: LCM (tự tính) của 12 và 18 là: 36

# Ví dụ khác
print(f"LCM (tự tính) của 7 và 5 là: {compute_lcm(7, 5)}")   # Kết quả: 35
print(f"LCM (tự tính) của 6 và 9 là: {compute_lcm(6, 9)}")   # Kết quả: 18

Giải thích code compute_lcm:

1. import math: Cần thiết để gọi math.gcd(). Nếu bạn đã tự định nghĩa hàm compute_gcd ở trên, bạn có thể dùng hàm đó thay thế.
2. if x == 0 or y == 0: return 0: Xử lý trường hợp đặc biệt khi một trong hai số là 0.
3. gcd_val = math.gcd(x, y): Tính GCD của x và y.
4. lcm_val = abs(x * y) // gcd_val: Áp dụng công thức. abs(x * y) đảm bảo tích là dương, và // là phép chia lấy phần nguyên, rất quan trọng để kết quả LCM luôn là số nguyên.

Kết luận

GCD và LCM là những viên gạch nền tảng trong toán học số và có nhiều ứng dụng thực tế trong lập trình. Python cung cấp các công cụ mạnh mẽ và tiện lợi trong mô-đun math (đặc biệt từ Python 3.9) để tính toán chúng một cách dễ dàng.

• Sử dụng math.gcd() và math.lcm() là cách đơn giản và hiệu quả nhất khi phiên bản Python của bạn hỗ trợ.
• Hiểu và tự triển khai Thuật toán Euclid cho GCD và công thức tính LCM qua GCD giúp bạn nắm vững bản chất vấn đề và linh hoạt hơn trong các tình huống khác nhau.

#HappyCoding cùng FullhouseDev! 🚀