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.