Ở trường học và đại học, chúng ta đều đã học những kiến thức cơ bản về toán học. Trong số tất cả các khái niệm phức tạp về lượng giác và số học, một khái niệm được sử dụng thường xuyên nhất trong lập trình là GCD hoặc Số chia chung lớn nhất. Tương tự như tất cả các ngôn ngữ lập trình, Python cũng hỗ trợ việc tạo mã có thể tìm thấy GCD của hai số do người dùng cung cấp và trong bài viết này, chúng ta sẽ tìm hiểu cách thực hiện điều đó. Hãy để chúng tôi xem cách triển khai GCD bằng Python,
GCD là gì?
GCD là chữ viết tắt của Greatest Common Divisor, là một phương trình toán học để tìm số lớn nhất có thể chia cả hai số mà người dùng đưa ra. Đôi khi phương trình này cũng được coi là nhân tử chung lớn nhất. Ví dụ: thừa số chung lớn nhất của các số 20 và 15 là 5, vì cả hai số này đều có thể chia hết cho 5. Khái niệm này cũng có thể dễ dàng được mở rộng cho một tập hợp nhiều hơn 2 số, trong đó GCD sẽ là số chia tất cả các số do người dùng cung cấp.
Khái niệm GCD có rất nhiều ứng dụng trong lý thuyết số, đặc biệt là ứng dụng của công nghệ mã hóa RSA cũng như số học mô-đun. Nó cũng đôi khi được sử dụng để đơn giản hóa các phân số có trong một phương trình.
Bây giờ bạn đã biết khái niệm cơ bản về GCD, hãy xem cách chúng ta có thể viết mã một chương trình bằng Python để thực thi chương trình tương tự.
GCD bằng Python
Để tính toán GCD bằng Python, chúng ta cần sử dụng hàm toán học có sẵn trong thư viện Python. Hãy cùng chúng tôi khám phá một vài ví dụ để hiểu rõ hơn về điều này.
Hãy để chúng tôi xem cách tìm GCD trong Python bằng cách sử dụng đệ quy
GCD sử dụng đệ quy
1 2 3 4 5 6 7 8 9 10 11 12 | # Python code to demonstrate naive # method to compute gcd ( recursion ) def hcfnaive(a,b): if(b==0): return a else: return hcfnaive(b,a%b) a = 60 b= 48 # prints 12 print ("The gcd of 60 and 48 is : ",end="") print (hcfnaive(60,48)) |
Khi chương trình trên được chạy, đầu ra sẽ giống như thế này.
Gcd của 60 và 48 là: 12
Chúng tôi cũng có thể giới thiệu GCD bằng cách sử dụng các vòng lặp,
GCD sử dụng vòng lặp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # Python code to demonstrate naive # method to compute gcd ( Loops ) def computeGCD(x, y): if x > y: small = y else: small = x for i in range(1, small+1): if((x % i == 0) and (y % i == 0)): gcd = i return gcd a = 60 b= 48 # prints 12 print ("The gcd of 60 and 48 is : ",end="") print (computeGCD(60,48)) |
Khi chương trình trên được thực thi, kết quả đầu ra sẽ như thế này.
Gcd của 60 và 48 là: 12
Hãy để chúng tôi xem phương pháp tiếp theo,
GCD sử dụng thuật toán Euclid
1 2 3 4 5 6 7 8 9 10 11 | # Python code to demonstrate naive # method to compute gcd ( Euclidean algo ) def computeGCD(x, y): while(y): x, y = y, x % y return x a = 60 b= 48 # prints 12 print ("The gcd of 60 and 48 is : ",end="") print (computeGCD(60,48)) |
Đầu ra cho chương trình được đề cập ở trên sẽ là,
Gcd của 60 và 48 là: 12
Tiếp tục, dưới đây là phương pháp thứ tư để tìm GCD trong Python,
GCD Sử dụng Hàm GCD Toán học
Trước khi chúng ta có thể sử dụng hàm math.gcd () để tính toán GCD của các số trong Python, chúng ta hãy xem xét các tham số khác nhau của nó.
1 | Syntax: math.gcd( x,y) |
Thông số
X: là số nguyên không âm có gcd cần được tính.
Y: là số nguyên không âm thứ hai có gcd cần được tính.
Giá trị trả về: Tham số này sẽ trả về giá trị trả về dương tuyệt đối sau khi nó đã tính GCD của cả hai số do người dùng nhập vào.
Ngoại lệ: Nếu trong một tình huống nhất định, cả hai số được nhập bởi người dùng là 0, thì hàm sẽ trả về 0; và nếu đầu vào là một ký tự, thì hàm sẽ trả về một lỗi.
1 2 3 4 5 6 | # Python code to demonstrate gcd() # method to compute gcd import math # prints 12 print ("The gcd of 60 and 48 is : ",end="") print (math.gcd(60,48)) |
Đầu ra của chương trình trên sẽ là,
Gcd của 60 và 48 là: 12
Các trường hợp ngoại lệ chung
Dưới đây là các ngoại lệ phổ biến nhất để sử dụng chức năng này.
- Nếu một trong các số được nhập bởi người dùng là số 0, thì hàm sẽ trả về số không.
- Nếu một trong hai đầu vào là một ký tự thì hàm sẽ trả về lỗi kiểu.
Để hiểu rõ hơn điều này, hãy xem ví dụ dưới đây.
1 2 3 4 5 6 | # Python code to demonstrate gcd() # method to compute gcd import math # prints 12 print ("The gcd of 60 and 48 is : ",end="") print (math.gcd(60,48)) |
Đầu ra cho chương trình trên sẽ là,
Gcd của 60 và 48 là: 12
Các trường hợp ngoại lệ chung
Dưới đây là các ngoại lệ phổ biến nhất để sử dụng chức năng này.
- Nếu một trong các số được nhập bởi người dùng là số 0, thì hàm sẽ trả về số không.
- Nếu một trong hai đầu vào là một ký tự thì hàm sẽ trả về lỗi kiểu.
Để hiểu rõ hơn điều này, hãy xem ví dụ dưới đây.
# Python code to demonstrate gcd()
# method to compute gcd
import math
# prints 12
print ("The gcd of 60 and 48 is : ",end="")
print (math.gcd(60,48))
Đầu ra cho chương trình trên sẽ là,
Gcd của 0 và 0 là: 0
Gcd của a và 13 là:
Khi chạy chương trình trên cũng sẽ trả về lỗi thời gian chạy, có dạng như sau.
Traceback (cuộc gọi gần đây nhất cuối cùng):
Tệp “/home/94493cdfb3c8509146254862d12bcc97.py”, dòng 12, in
print (math.gcd (‘a’, 13))
TypeError: Đối tượng ‘str’ không thể được hiểu là một số nguyên
Vì vậy, điều này sẽ đưa chúng ta đến phần cuối của bài viết này về GCD trong Python.