Thuật toán là phương pháp hay công thức giải quyết vấn đề bằng cách đi theo một tập hợp các quy tắc. Thuật toán Euclid là ví dụ tiên khởi, được xây dựng vào khoảng 300 trước Công nguyên. Nó được thiết kế để tìm ước số chung lớn nhất (greatest common divisor, GCD) của hai số. Thuật toán này đóng vai trò cơ bản trong khoa học điện toán (computer science), và hầu hết thiết bị điện tử đều dùng thuật toán để cho ra kết quả hữu ích.
Phiên bản đơn giản (simple algorithm) của thuật toán Euclid dùng dữ kiện là GCD của hai số thì tương tự GCD của số nhỏ hơn và hiệu giữa chúng. Điều này cho phép ta liên tục loại bỏ số lớn hơn trong cặp số, giảm kích thước các số tham gia cho đến khi một số bằng 0. Số khác không cuối cùng là GCD của cặp số ban đầu.
Phương pháp này có thể phải lặp nhiều lần để được kết quả. Một phương pháp hiệu quả hơn, tức thuật toán chuẩn (standard algorithm), sẽ thay số lớn hơn bằng phần dư nhận được nhờ chia số đó cho số nhỏ hơn, cho tới khi không còn số dư.
-- Nguồn: Paul Glendinning (2013) Toán học trong vài phút: 200 khái niệm được diễn giải tức thì, Quercus.
-- Bài được tập hợp tại Toán học trong vài phút
Không có nhận xét nào:
Đăng nhận xét