Giải thuật Euclid
Bách khoa toàn thư mở Wikipedia
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.
Mục lục |
[sửa] 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(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).
[sửa] Bổ đề
Giả sử a = bq + r, với a, b, q, r là các số nguyên, ta có:
[sửa] Mã giả
[sửa] Chương trình đệ quy
procedure ƯSCLN(a, b : positive integers)
Begin
- if a mod b = 0 then ƯSCLN := b
- else ƯSCLN := ƯSCLN(b; a mod b);
End
[sửa] Chương trình dùng vòng lặp
procedure ƯSCLN(a, b : positive integers)
Begin
- x := a
- y := b
- while y ≠ 0
- begin
- r := x mod y
- x := y
- y := r
- end {x là ƯSCLN(a, b)}
End
