Bài toán: Cho hai số nguyên bất kỳ, tìm ước chung lớn nhất. Ví dụ 31231 và 15.
Nhìn qua thì có vẻ rất dễ tại mình cá chắc ace đã học qua cái này khi ở cấp 1 và cấp 2. Tuy nhiên, nếu giả sử chúng ta muốn tìm ước chung lớn nhất của 31231 và 15 thì sẽ phải làm sao? Giải bằng tay thì sẽ khá là lâu và phức tạp. Đây là lúc thuật toán Ơ-clít sẽ trở thành một trợ thủ đắc lực.
Thuật toán Ơ-clít nói như sau:
- Khi có hai số a và b với a > b, chúng ta sẽ chia b cho a (a / b).
- Nếu số dư bằng 0 thì b sẽ lập tức là ước chung lớn nhất của hai số.
- Nếu số dư không bằng 0, thay a = b, thay b = số dư vừa tìm và tiếp tục chia a với b cho đến khi số dư bằng 0 thì b lúc đó là ước số lớn nhất.
- Chúng ta gọi a = 31231, b = 15 và r = số dư sau khi chia a với b
- Sau đó dùng modulo (trong python sẽ là %) để tìm mỗi số dư tại chúng ta không quan tâm đến kết quả của việc a / b. Kết quả là 1.
- Chúng ta thay a = 15 và b = 1 chia lại a với b và số dư lúc đó sẽ là 0.
- Từ đó suy ra ước chung lớn nhất của 31231 và 15 là 1.
Mã:
a = 31231
b = 15
def gcd(a, b):
while True:
r = a % b
if r == 0:
break
else:
a = b
b = r
return b
print("Ước lớn nhất là", gcd(a, b))Mình xin giải thích qua về code của mình. Mình tạo một function gọi là gcd (greatest common denominator hay ước chung lớn nhất) và nó lấy hai giá trị a và b. Mình cho chạy qua một loop vĩnh viễn để function liên tục làm nhưng bước mình nêu trên cho đến khi số dư bằng 0 thì mình thoát khỏi loop ngay lập tức và trả về giá trị mới nhất của b. Cái hay của đoạn code này là nó không quan tâm a hay b là số lớn hơn (cái này mình viết xong mới tình cờ phát hiện
) và đều sẽ cho ra kết quả giống nhau. Nếu ace có cách nào hay hơn mong được chỉ giáo thêm.Kết: Nói tóm lại thì thuật toán nói chung và thuật toán Ơ-clít nói riêng đều là những công cụ rất căn bản (và cũng rất rất phức tạp nếu đi chuyên sâu) mà lại khiến việc giải nhiều bài toán học búa trở nên nhanh và thuận tiện hơn rất nhiều. Mình mong muốn nếu ace chưa có điều kiện tìm hiểu thêm về một số các thuật toán căn bản nên học qua không chỉ để có thêm kiến thức trong học tập cũng như công việc mà cũng giúp các ace có một cuộc sống đơn giản hơn.
Thêm:
Cám ơn bác đã nói thêm về trường hợp này. Nếu là 0 thì bác có thể nói ước chung lớn nhất là a (hay số lớn hơn 0). Code trên của em đúng là sẽ tạch nếu b = 0 tại vì không thể chia cho 0 cho nên em có thể dùng try except nếu cần thiết.
Sửa lần cuối:
Junior Moderator
