Giải thuật Euclid

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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.

Ví dụ[sửa | sửa mã nguồn]

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).

Bổ đề[sửa | sửa mã nguồn]

Giả sử a = bq + r, với a, b, q, r là các số nguyên, ta có:

\mbox{UCLN}(a,b) = \begin{cases}\begin{matrix}b &\mbox{n}\acute{\hat{\mbox{e}}}\mbox{u} &r = 0 \\ \mbox{UCLN}(b,r)&\mbox{n}\acute{\hat{\mbox{e}}}\mbox{u}&r \ne 0\end{matrix}\end{cases}

Trong đó r = a mod b

Mã giải[sửa | sửa mã nguồn]

Var a,b:integer;
Function UCLN(x,y:integer):integer;
Begin
     if x mod y = 0 then UCLN:=y else UCLN:=UCLN(y,x mod y);
end;
Begin
     {Nhập 2 số a,b};
     If a>b then writeln(UCLN(a,b)) else writeln(UCLN(b,a));
     readln
end.

Chương trình con (thủ tục) dùng vòng lặp[sửa | sửa mã nguồn]

procedure USCLN(a, b : integer);
 
Begin
  x := a;
  y := b;
  while y <> 0 do
    begin
      r := x mod y;
      x := y;
      y := r;
    end;{x là ước số chung cần tìm}
End;

Chương trình con (hàm) dùng vòng lặp[sửa | sửa mã nguồn]

function UCLN(a, b : integer): integer;
 
var r:integer;
 
Begin
  while b <> 0 do
    begin
      r := a mod b;
      a := b;
      b := r;
    end;{a là ước số chung cần tìm}
  UCLN := a;
End;

Xem thêm[sửa | sửa mã nguồn]