Giải thuật Euclid, hay thuật toán
Euclid, là một giải thuật giúp tính ước số chung lớn nhất (ƯSCLN) của hai số
một cách hiệu quả. Giải thuật này đã được biết đến từ khoảng năm 300 trước Công
Nguyên. Nhà toán học Hy Lạp cổ Euclid đã viết giải thuật này trong cuốn sách
toán nổi tiếng Elements.
Ở dạng đơn giản nhất, thuật toán Euclid bắt đầu với cặp
số nguyên dương, và tạo ra một cặp số nguyên dương mới bao gồm số nhỏ hơn và
phần dư của của phép chia hai số ban đầu. Quá trình được tiếp tục cho đến khi
hai số trong cặp bằng nhau, giá trị lúc đó sẽ trở thành ước số chung lớn nhất
của cặp số ban đầu.
Hình
minh họa thuật toán Euclid để tìm ước số chung lớn nhất
(ƯSCLN) của hai đoạn thẳng BA và DC, độ dài của cả hai đều là bội số của một đơn
vị độ dài chung. Vì độ dài của DC ngắn hơn nên nó được dùng để đo cho BA, nhưng
việc này chỉ làm được một lần do phần còn lại là đoạn EA ngắn hơn DC. Bây giờ EA
lại được dùng để đo độ dài đoạn DC hai lần. Cuối cùng đoạn FC được dùng để đo độ
dài đoạn EA ba lần. Vì không còn đoạn nào dư ra nên quá trình này kết thúc với
FC trở thành ƯSCLN. Phía bên phải là ví dụ của Nicomachus với hai số 49 và 21 có
kết quả ƯSCLN là 7.
Nguyên lí chính của thuật toán là ước số chung lớn nhất
của một cặp số không thay đổi với hiệu của hai số đó. Ví dụ như ƯSCLN của 252 và
105 chính bằng ƯSCLN của 147 (= 252 − 105) và 105. Vì số lớn hơn trong cặp số bị
giảm giá trị nên việc lặp đi lặp lại thuật toán này giúp tạo ra những số ngày
càng nhỏ và đến một lúc nào đó quá trình này sẽ kết thúc — khi cặp số còn lại
hai số bằng nhau (nếu quá trình được thực hiện thêm một bước nữa, sẽ có một
trong hai số trở thành số 0).
Bổ đề:
Giả
sử a = bq + r, với a, b, q,
r là các số nguyên, ta có:
Trong
đó r = a mod b
Ví dụ:
Tính
ước số chung lớn nhất của 91 và 287.
Trước
hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
-
287 = 91*3
+ 14 (91 & 14 sẽ được dùng cho vòng lặp
kế)
Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ
chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết
bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm
ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như
sau:
-
91 = 14*6
+ 7 (14 & 7 sẽ được dùng cho vòng lặp
kế)
-
14 = 7*2 (không còn số dư, kết thúc,
nhận 7 làm kết quả)
Cuối
cùng ta có: 7 = ƯSCLN(7,0) = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
Chương trình
Scilab:
disp("+---+---+---+---+---+---+---+---+---+---+---+")
disp(" TÌM ƯCLN CỦA HAI SỐ") // Theo thuật toán Euclide
disp(" ")
//
clear
// Hàm tìm số dư của x chia y
function d=sodu(x, y)
d=x-floor(x/y)*y
endfunction
// Hàm tìm UCLN
function u=ucln(x, y)
while y>0
t=sodu(x,y)
x=y
y=t
end
u=x // x là ƯCLN cần tìm
endfunction
a=input("Nhập số thứ nhất: ")
b=input("Nhập số thứ hai: ")
disp(ucln(a,b))
Tham khảo Giải thuật Euclid - Wikipedia
