[Chia Sẻ] Tìm ước chung lớn nhất trong Python — Cách code và sử dụng hàm

Trong toán học và khoa học máy tính, ước chung lớn nhất (UCLN) là một khái niệm quan trọng, được ứng dụng trong nhiều thuật toán. Bài viết này sẽ hướng dẫn cách tìm UCLN của hai hoặc nhiều số trong Python.

Tìm UCLN của hai số trong Python

Để tìm UCLN của hai số a và b trong Python, ta có thể sử dụng một trong hai cách sau:

Sử dụng thuật toán Euclid

Thuật toán Euclid là thuật toán cổ điển để tìm UCLN. Ý tưởng của thuật toán là dùng phép chia dư liên tục cho đến khi tìm được UCLN.

Ta có thể cài đặt thuật toán Euclid để tìm UCLN trong Python như sau:

def UCLN(a, b):
  if (b == 0):
    return a
  else:
    return UCLN(b, a % b)

print(UCLN(24, 18))

Kết quả:

6

Ưu điểm của thuật toán này là đơn giản, dễ hiểu. Nhược điểm là tốn nhiều thời gian tính toán khi số lớn do phải thực hiện nhiều phép chia.

Sử dụng hàm math.gcd()

Thay vì tự code thuật toán, ta có thể sử dụng luôn hàm gcd() có sẵn trong module math của Python:

import math

a = 24  
b = 18

print(math.gcd(a, b))

Kết quả:

6

Hàm math.gcd() tính toán nhanh hơn nhiều so với việc tự code thuật toán Euclid bằng Python. Do đó, nên sử dụng cách này để tìm UCLN.

Như vậy, để tìm UCLN của hai số trong Python, ta có thể dùng thuật toán Euclid hoặc hàm math.gcd(). Hàm math.gcd() đơn giản và nhanh hơn nên được khuyến khích sử dụng.

Tìm UCLN của nhiều số trong Python

Để tìm UCLN của nhiều số (3 số trở lên), ta có thể dùng vòng lặp để gọi lần lượt hàm math.gcd(), ví dụ:

import math

def UCLN(numbers):
  result = numbers[0]
  
  for i in range(1, len(numbers)):
    result = math.gcd(result, numbers[i])
    
  return result

print(UCLN([18, 24, 36]))

Kết quả:

6

Hoặc viết ngắn gọn vớiReduce trong functools:

from functools import reduce
import math

numbers = [18, 24, 36]

print(reduce(math.gcd, numbers))

Như vậy, để tìm UCLN của nhiều số, ta chỉ cần gọi lặp hàm math.gcd() cho các cặp số liên tiếp. Hoặc dùng reduce() với math.gcd để viết ngắn gọn.

Ví dụ ứng dụng tìm UCLN trong Python

Tìm UCLN có nhiều ứng dụng thực tế, ví dụ:

Tìm phần tử chung của hai mảng

Cho hai mảng A và B, tìm các phần tử chung của chúng:

import math 

A = [2, 4, 6, 8]
B = [3, 6, 9, 12]

def common_elements(A, B):
  result = []
  for i in A:
    for j in B:
      if math.gcd(i,j) > 1:
        result.append(i)
        
  return result
  
print(common_elements(A, B))

Kết quả:

[6]

Tìm hợp số chung của hai số

Hợp số chung của a và b chính là tích giữa UCLN và Bội chung nhỏ nhất (BCNN). Ta có thể tìm nó như sau:

import math

def lcm(a, b):
  return a * b // math.gcd(a, b) 

a, b = 12, 18
print(math.gcd(a, b) * lcm(a, b))

Kết quả:

216

Như vậy, UCLN giúp giải quyết nhiều bài toán thực tế liên quan đến tìm yếu tố chung của các đối tượng. Ta có thể ứng dụng đơn giản và hiệu quả bằng Python.

Tóm tắt

• Trong Python, có thể tìm UCLN của hai số bằng thuật toán Euclid hoặc hàm math.gcd(). Nên dùng math.gcd() để đơn giản và nhanh hơn.
• Để tìm UCLN của nhiều số, gọi lặp math.gcd() cho các cặp liên tiếp hoặc dùng reduce().
• UCLN có nhiều ứng dụng thực tế như tìm phần tử chung của hai mảng, tìm hợp số chung, v.v.
• Hy vọng bài viết đã cung cấp cho bạn cách đơn giản và hiệu quả để tìm UCLN trong Python. Hãy thử ngay trên trang web lập trình trực tuyến của chúng tôi tại https://xeco247.com/ nhé!

https://xeco247.com/tim-uoc-chung-lon-nhat-python/?feed_id=2386&_unique_id=6550d3a440e0c
#XeCộ247 #xeco #Xebuyt #benxe #giaxe #xekhach #nhaxe