Ước chung lớn nhất [GCD] là một thuật ngữ toán học để tìm thừa số chung lớn nhất có thể chia hai số một cách hoàn hảo. GCD còn được gọi là Yếu tố chung cao nhất [HCF]. Ví dụ HCF/GCD của 2 số 54 và 24 là 6. Vì 6 là ước chung lớn nhất chia hết 54 và 24
GCD Sử dụng chức năng gcd[]
Trong python, gcd[] là một hàm sẵn có được cung cấp bởi mô-đun toán học để tìm ước chung lớn nhất của hai số
cú pháp
Trong đó a và b là hai số nguyên được truyền làm đối số cho hàm gcd[]
Hãy tạo một chương trình để in GCD của hai số bằng hàm toán học có sẵn. gcd[] trong trăn
toán_vui. py
đầu ra
Trong ví dụ trên, phép toán. hàm gcd[] tạo GCD của hai số đã cho. Trong hàm gcd[], a và b chuyển thành đối số trả về ước chung lớn nhất của hai số nguyên, chia hết các số
GCD Sử dụng đệ quy
Đệ quy là một hàm tiêu thụ bộ nhớ được xác định trong python, gọi chính nó thông qua biểu thức tự tham chiếu. Nghĩa là hàm sẽ liên tục gọi và lặp lại cho đến khi thỏa mãn điều kiện xác định để trả về ước chung lớn nhất của một số
Mã giả của thuật toán
Bước 1. Lấy hai đầu vào, x và y, từ người dùng
Bước 2. Truyền số đầu vào làm đối số cho hàm đệ quy
Bước 3. Nếu số thứ hai bằng không [0], nó sẽ trả về số đầu tiên
Bước 4. Mặt khác, nó gọi đệ quy hàm với số thứ hai làm đối số cho đến khi nó nhận được phần còn lại, số này chia số thứ hai cho số thứ nhất
Bước 5. Gọi hoặc gán gcd_fun[] cho một biến
Bước 6. Hiển thị GCD của hai số
Bước 7. Thoát khỏi chương trình
Tìm hiểu chương trình tìm ƯCLN của hai số bằng đệ quy
gcdRecur. py
đầu ra
GCD Sử dụng Vòng lặp
Hãy tạo chương trình tìm GCD của hai số trong python bằng vòng lặp
gcdFile. py
đầu ra
Như chúng ta có thể thấy trong chương trình trên, chúng ta lấy hai giá trị làm đầu vào và chuyển các số này cho hàm GCD_Loop[] để trả về một GCD
GCD Sử dụng thuật toán Euclid hoặc Thuật toán Euclide
Thuật toán Euclid là một phương pháp hiệu quả để tìm ước chung lớn nhất của hai số. Đây là thuật toán lâu đời nhất chia số lớn hơn thành các số nhỏ hơn và lấy phần còn lại. Một lần nữa, nó chia số nhỏ hơn từ phần còn lại và thuật toán này liên tục chia số cho đến khi phần còn lại trở thành 0
Ví dụ, giả sử chúng ta muốn tính H. C. F của hai số, 60 và 48. Sau đó, chúng tôi chia 60 cho 48; . Bây giờ chúng ta lại chia số 24 cho 12 và sau đó nó trả về phần còn lại là 0. Vì vậy, theo cách này, chúng tôi nhận được H. C. f là 12
Một ví dụ thú vị hơn về việc sử dụng vòng lặp while
được đưa ra khi triển khai thuật toán Euclid để tìm ước chung lớn nhất của hai số, $\mathrm{gcd}[a,b]$
>>> a, b = 1071, 462
>>> while b:
.. a, b = b, a % b
...
>>> print[a]
21
Vòng lặp tiếp tục cho đến khi b
chia chính xác cho a
; . Nhớ lại rằng số nguyên 0 đánh giá là boolean False
nên
a = int[input['Insert the first number: ']]
b = int[input['Insert the second number: ']]
while b > 0:
r = a % b
a, b = b, r
print [a]
0 tương đương với while
0 Thuật toán Euclide bao gồm chia hai số và xem xét phần còn lại. Thủ tục kết thúc khi phần còn lại được tìm thấy bằng không
Hãy lấy một số ví dụ
Thuật toán Euclide Python – Ví dụ đầu tiên
Hãy lấy hai số ví dụ 20 và 15 và tiến hành theo thuật toán của Euclid
Đầu tiên vượt qua. một / b tôi. e. 20/15 = 1 dư 5 – số dư khác không, vì vậy tôi tiếp tục chia
Do đó, bước thứ hai sẽ là đổi a với b và b với r, nghĩa là 15/5 = 3 dư 0
Chúng tôi tìm thấy phần còn lại bằng 0, vì vậy GCD là 5
Thuật toán Euclide Python – Ví dụ thứ hai
Hãy tạo một ví dụ thứ hai để hiểu cách thức hoạt động của thuật toán Euclid
Vì vậy, hãy lấy số 64 và 30
64/30 = 2 dư 4 – số dư khác không, vì vậy chúng tôi tiếp tục chia
30/4 = 7 dư 2 – dư khác 0 nên ta tiếp tục chia
4/2 = 2 dư 0
Phần còn lại bằng 0, vì vậy GCD là 2
Thuật toán Euclide trong Python
Bây giờ hãy thực hiện thuật toán này trong Python
Trước hết chúng ta lấy hai số a và b làm đầu vào. Sau đó, miễn là b lớn hơn 0, chúng tôi tính phần còn lại của phép chia của a chia cho b và trao đổi a với b và b với r. Vì vậy, hãy in một
Vì vậy, đây là mã hoàn chỉnh đại diện cho thuật toán Euclide trong Python
a = int[input['Insert the first number: ']]
b = int[input['Insert the second number: ']]
while b > 0:
r = a % b
a, b = b, r
print [a]
Bạn cũng có thể kiểm tra mã trong trình biên dịch Python trực tuyến trong liên kết đó. Trình biên dịch Python trực tuyến
Đây là một triển khai khả thi của thuật toán Euclide, trong bài tiếp theo chúng ta sẽ làm các ví dụ khác về vòng lặp trong Python