TÌM USCLN VÀ BSCNN CỦA SỐ A,B BẰNG PASCAL

·        Thuật toán tìm UCLN của 2 số nguyên dương:

Cho 2 số nguyên dương m, n. Tìm UCLN(m,n)

Học sinh thường dùng một trong 2 thuật toán

Thuật toán 1: Sử dụng phép trừ liên tục cho đến khi 2 số bằng nhau:

                     + Nhập m, n

                     + While m<>n do

                             If m>n then m:=m-n

                             Else n:=n-m;

                     +UCNN:=n;

           Thuật toán này chạy chậm: Ví dụ với  m=1000000000, n=1 phải chạy 1 tỷ phép toán.

Thuật toán 2: (Đối với HSG nên hướng các em sử dụng thuật toán này)

                    + Nhập m, n

                    + While n <> 0 do

                         Begin

                           r:= m mod n

                           m:=n;                                             

                           n:=r;

                       End;

                             +UCLN:=m

Với thuật toán này khi m=1000000000, n=1, chỉ mất vài phép toán để tính được UCLN(m,n).

•  Thuật toán tìm UCLN của dãy số

Để tìm UCLN của dãy a1, a2,…,an, cần lập hàm:

 FUNCTION UCLN(a, b: longint): longint;

 Khi đó  + d:=a[1];

               + for i:=2 to n do  Begin b:=a[i]; d:=UCLN(d, b);End;

 ·        Thuật toán tìm BCNN của 2 số:

Ta có BCNN(m,n)= (m * n) div UCLN(m, n).

Ở đây học sinh thường mắc 2 sai lầm sau :

Sai lầm 1 : d :=UCLN(m, n) ;

                   BCNN :=m*n div d ;

               Đúng ra phải là :

               BCNN :=m * n (lưu tích m.n)

                d := UCLN(m, n) ;

              BCNN := BCNN div d

Sai lầm 2 : BCNN(m, n, k) = m*n*k div UCLN(m, n k)

•    Để tìm BCNN của dãy số nguyên dương a1, a2, …,an (n>=2)

   BCNN:=a[1]; d:=a[1];

 For i:=2 to n do n do

   Begin

      b:=a[i];      

      BCNN:=BCNN*b;

      d:=UCLN(BCNN,b);

     BCNN:=BCNN div d ;

  End ;

- Hàm tìm USCLN;

function uscln(a,b:integer):integer;

begin

while a<>b do

begin

if a>b then a:=a-b else b:=b-a;

end;

uscln:=a;

end;