CodeUtility
Lập trình thông minh, làm việc hiệu quả!
Thuật toán Python

Thuật toán Euclid tìm UCLN trong Python

Thuật toán liên tục thay cặp số bằng số chia và phần dư.

Thuật toán Euclid tìm UCLN trong Python là gì?

Thuật toán liên tục thay cặp số bằng số chia và phần dư.

Tính ước chung lớn nhất của hai số.

Khi nào nên sử dụng?

  • Rèn luyện tư duy giải quyết vấn đề và cấu trúc dữ liệu.
  • Xử lý dữ liệu khi cần kiểm soát rõ từng bước của thuật toán.
  • Chuẩn bị cho bài tập, kỳ thi và phỏng vấn lập trình.

Code ví dụ

Chạy code →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))

Kết quả dự kiến

6

Cách hoạt động

Khi phần dư bằng 0, giá trị còn lại là UCLN; độ phức tạp logarithmic.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.

  1. Kiểm tra trường hợp rỗng, một phần tử và giá trị trùng lặp.
  2. In trạng thái sau từng bước để quan sát thuật toán.
  3. Đo thời gian với 100, 1.000 và 10.000 phần tử rồi so sánh cách giải khác.
Chạy trong Python IDE →