Đầu tiên chúng ta cần tìm hiểu vấn đề sau:
- Ước chung lớn nhất là gì? Nếu một số nguyên a bất kỳ chia hết cho số nguyên c được gọi là ước của số nguyên a và a được gọi là bội của c. Nếu 2 số dương a và b bất kỳ cùng chia hết cho một số nguyên c lớn nhất thì c được gọi là ước chung lớn nhất của a và b. Nếu a và b đều = 0 thì chúng không có ước chung.
- Bội chung nhỏ nhất là gì? c được gọi là bội chung nhỏ nhất của a và b khi c là số nguyên nhỏ nhất chia hết cho a và b.
[*]Công thức: UCLN[a,b] = [a*b]/BCNN[a,b]
Bài tập pascal tim ước chung lớn nhất và BCNN
Cách 1: Lấy số lớn hơn trong 2 số đã cho trừ đi nhau. Lặp lại thao tác cho đến khi 2 số bằng nhau thì ngừng => UCLN. Và làm theo công thức [*] chúng ta được BCNN.var x,y,UCLN,BCNN:integer;
begin
write['Nhap vao 2 so x va y'];
readln[x,y];
BCNN:=x*y;
While xy do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write[UCLN,' ',BCNN];
end.
begin
write['Nhap vao 2 so x va y'];
readln[x,y];
BCNN:=x*y;
While xy do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write[UCLN,' ',BCNN];
end.
Cách 2: Sử dụng thuật toán Euclide bằng cách chia lấy dư [mod]. Ưu điểm của thuật toán này là xử lý nhanh hơn vì phép tính ít hơn so với cách 1.
var a,b,UCLN, BCNN, temp:integer; {temp là biến tạm}
begin
write['Nhap vao so a: '];
readln[a];
write['Nhap vao so b: '];
readln[b];
BCNN:= a*b;
temp:= b mod a;
while temp0 do
begin
temp:= a mod b;
a:=b;
b:=temp;
end;
UCLN:=a;
BCNN:= BCNN div UCLN;
write['UCLN = ',UCLN,' BCNN = ',BCNN];
readln;
end.
begin
write['Nhap vao so a: '];
readln[a];
write['Nhap vao so b: '];
readln[b];
BCNN:= a*b;
temp:= b mod a;
while temp0 do
begin
temp:= a mod b;
a:=b;
b:=temp;
end;
UCLN:=a;
BCNN:= BCNN div UCLN;
write['UCLN = ',UCLN,' BCNN = ',BCNN];
readln;
end.
Chương trình hoàn chỉnh đã tách thành thuật toán con
uses crt;
function UCLN[a,b:integer]:integer;
begin
while[ab] do
if a > b then
a:=a-b
else
b:=b-a
if a = b then
UCLN :=a
end;
var a,b:integer;
begin
clrscr;
write['Nhap vao so a: '];
readln[a];
write['Nhap vao so b: '];
readln[b];
writeln['UCLN := ',UCLN[a,b]];
write['BCNN := ', [a*b] div UCLN[a,b]];
readln;
end.
function UCLN[a,b:integer]:integer;
begin
while[ab] do
if a > b then
a:=a-b
else
b:=b-a
if a = b then
UCLN :=a
end;
var a,b:integer;
begin
clrscr;
write['Nhap vao so a: '];
readln[a];
write['Nhap vao so b: '];
readln[b];
writeln['UCLN := ',UCLN[a,b]];
write['BCNN := ', [a*b] div UCLN[a,b]];
readln;
end.
Chúc các bạn làm tốt bài tập của mình nhé!
Thương Lee