Trong ví dụ này, bạn sẽ học cách tìm GCD của hai số bằng hai phương pháp khác nhau: hàm và vòng lặp và, thuật toán Euclide
Để hiểu ví dụ này, bạn nên có kiến thức về các chủ đề lập trình Python sau:
- Các hàm Python
- Đệ quy Python
- Đối số hàm trong Python
Nhân tử chung cao nhất (HCF) hoặc ước chung lớn nhất (GCD) của hai số là số nguyên dương lớn nhất chia hoàn toàn hai số đã cho. Ví dụ, HCF của 12 và 14 là 2.
Mã nguồn: Sử dụng vòng lặp
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Đầu ra
HCF là 6
Ở đây, hai số nguyên được lưu trữ trong các biến num1 và num2 được chuyển cho compute_hcf()hàm. Hàm tính toán HCF hai số này và trả về nó.
Trong hàm, trước tiên chúng ta xác định số nhỏ hơn trong hai số vì HCF chỉ có thể nhỏ hơn hoặc bằng số nhỏ nhất. Sau đó, chúng tôi sử dụng một forvòng lặp để đi từ 1 đến số đó.
Trong mỗi lần lặp, chúng tôi kiểm tra xem số của chúng tôi có chia hoàn hảo cho cả hai số đầu vào hay không. Nếu vậy, chúng tôi lưu trữ số dưới dạng HCF Khi hoàn thành vòng lặp, chúng tôi kết thúc với số lớn nhất chia hoàn toàn cả hai số.
Phương pháp trên dễ hiểu và dễ thực hiện nhưng không hiệu quả. Một phương pháp hiệu quả hơn nhiều để tìm HCF là thuật toán Euclide.
Thuật toán Euclide
Thuật toán này dựa trên thực tế là HCF của hai số cũng chia cho hiệu số của chúng.
Trong thuật toán này, chúng tôi chia số lớn hơn cho nhỏ hơn và lấy phần dư. Bây giờ, chia nhỏ hơn cho phần còn lại này. Lặp lại cho đến khi phần còn lại là 0.
Ví dụ, nếu chúng ta muốn tìm HCF của 54 và 24, chúng ta chia 54 cho 24. Số dư là 6. Bây giờ, chúng ta chia 24 cho 6 và số dư là 0. Do đó, 6 là HCF cần thiết
Mã nguồn: Sử dụng thuật toán Euclide
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Ở đây chúng ta lặp lại cho đến khi y trở thành 0. Câu lệnh x, y = y, x % ythực hiện hoán đổi các giá trị trong Python. Nhấp vào đây để tìm hiểu thêm về hoán đổi các biến trong Python.
Trong mỗi lần lặp, chúng ta đồng thời đặt giá trị của y theo x và giá trị còn lại (x % y)trong y. Khi y trở thành 0, chúng ta có HCF theo x.
