Thuật toán Euclid tìm UCLN với Pascal

198
Lập trình Pascal

Bài toán. Viết chương trình tìm ước chung lớn nhất (UCLN) của hai số với yêu cầu sử dụng thuật toán Euclid.

Thuật toán Euclid: 

           – Nếu a chia hết cho b (a chia b dư 0) thì UCLN(a,b) bằng b

           – Nếu a chia b dư r thì UCLN(a,b) = UCLN(b,r)

Thuật toán

          – Nhập a, b và gán r = a mod b.

          – Lặp với điều kiện r <> 0: b = r, a = b, r = a mod b.

Code tham khảo:

Program UCLN;
uses crt;
var a,b,r:byte;
begin
     clrscr;
     writeln('CHUONG TRINH TIM UCLN CUA HAI SO');
     write('Nhap a: ');readln(a);
     write('Nhap b: ');readln(b);
     r:=a mod b;
     while r<> 0 do
     begin
         b:=r;
         a:=b;
         r:=a mod b;
     end;
     write('UCLN cua hai so la: ',b);
     readln
end.