Kiến thức

Hướng dẫn-Euclidean algorithm-Tìm ước chung lớn nhất của hai số

IT Lover

IT Lover

Rìu Sắt Đôi
Former Moderator

  • 22/5/19

  • #1

NumberedEquation3.gif

Khi bắt đầu học về thuật toán (algorithm), có một số ví dụ căn bản và dễ học mà ace lập trình nên biết qua để có thể đơn giản hóa loạt các bài toàn phức tạp. Hôm nay mình xin giới thiệu một trong nhưng thuật toán căn bản đó là thuật toán Ơ-clít (Euclidean algorithm).

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.

Giải:

  1. Chúng ta gọi a = 31231, b = 15 và r = số dư sau khi chia a với b
  2. 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.
  3. Chúng ta thay a = 15 và b = 1 chia lại a với b và số dư lúc đó sẽ là 0.
  4. Từ đó suy ra ước chung lớn nhất của 31231 và 15 là 1.

Code (mình dùng python cho nó đơn giản):

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 :D) 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:

NgoHungCuong nói:

Có nên xét thêm trường hợp a hoặc b bằng 0 ko bạn?

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: 23/5/19

Bạn đang xem: Hướng dẫn-Euclidean algorithm-Tìm ước chung lớn nhất của hai số

Chủ đề tương tự

Đưa website của bạn lên Internet trong vòng nửa nốt nhạc

Đóng gói cài đặt kèm database trên Visual Studio 2019

Đóng gói cài đặt kèm database trên Visual Studio 2015

Đọc Nhiều File Excel Cùng Cấu Trúc Vào Gridview

[VBA] ACE lập trình giúp file Excel Nhập Kho này với!

  • Like
  • Love

Reactions:

wh1t3ch, giang375, chuixoixa and 2 others

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button
444 live app 444 live 444 live app 444live kisslive kiss live yy live yylive