Question

Viết CT tìm ƯCLN (Uớc chung lớn nhất) GCD bằng Pascal

Answer 1

var x,y,UCLN,BCNN:integer;

begin

readln(x,y);
BCNN:=x*y;

While x<>y do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;

write(UCLN,' ',BCNN);

end.

Answer 2

Có nhiều thuật toán để tìm ước chung lớn nhất (hay GCD), nhưng đơn giản nhất đó chính là thuật toán Euclid. Sau đây mình sẽ trình bày cách tư duy cho bài này

B1: Xác định đầu vào (input) là hai số a,b nguyên dương

B2: Viết thuật toán để có được đầu ra như đề bài yêu cầu là ƯCLN

Thuật toán Euclid

Trong khi b khác 0 thì:

   tạm = b

   b = a mod b

   a = tạm

kết quả sẽ là a

B3: Xuất kết quả (output) là ƯCLN

Đây là mã nguồn chương trình tìm ước chung lớn nhất bằng Pascal

uses crt;

var tam, a, b: integer;

begin

  clrscr;

 writeln("Nhap vao so a: ");

 readln(a);

 writeln("Nhap vao so b: ");

 readln(b):

 while a <> b do

 begin

   tam = b;

   b = a mod b;

   a = tam;

 end;

writeln("UCLN la: ", a);

 readln;

end.