[Chia Sẻ] Hướng dẫn cách tìm ước chung lớn nhất của 2 số trong Pascal

Trong lập trình Pascal, tìm ước chung lớn nhất (UCLN) của 2 số nguyên là một bài toán cơ bản. Bài viết sau đây sẽ hướng dẫn các bạn cách giải quyết bài toán tìm UCLN của 2 số trong Pascal thông qua các ví dụ và code minh họa.

Giới thiệu về UCLN

UCLN – viết tắt của Ước chung lớn nhất, là số nguyên dương lớn nhất chia hết cho cả hai số a và b.

Ví dụ:

• UCLN của 12 và 18 là 6
• UCLN của 25 và 50 là 25

Tìm UCLN có ứng dụng trong nhiều lĩnh vực như toán học, mật mã, xử lý ảnh, v.v. nên đây là một kỹ năng cần thiết trong lập trình.

Cách tìm UCLN trong Pascal

Để tìm UCLN của 2 số trong Pascal, ta có thể sử dụng một trong các cách sau:

Sử dụng vòng lặp

Ý tưởng là dùng vòng lặp while để liên tục trừ số lớn hơn cho số nhỏ hơn cho đến khi dư bằng 0. Lúc đó số còn lại chính là UCLN.

function UCLN(a, b: integer): integer;  
begin
  while (a <> b) do
  begin
    if (a > b) then 
       a := a - b
    else
       b := b - a;
  end;
  
  UCLN := a;  
end;

Ưu điểm của cách này là đơn giản, dễ hiểu. Nhược điểm là tốc độ chậm hơn các thuật toán tối ưu khác.

Sử dụng thuật toán Euclid

Thuật toán Euclid tìm UCLN dựa trên định lý:

UCLN(a, b) = UCLN(b, a mod b)

Code Pascal implement thuật toán Euclid:

function UCLN(a, b: integer): integer;
begin
  if (b = 0) then
    UCLN := a  
  else 
    UCLN := UCLN(b, a mod b);
end;

Ưu điểm của Euclid là loại bỏ được vòng lặp nên tốc độ nhanh hơn. Đây là một trong những thuật toán tốt nhất để tìm UCLN.

Sử dụng hàm có sẵn

Pascal cung cấp sẵn hàm GCD để tìm UCLN của 2 số:

GCD(a, b: integer): integer;

Đây là cách đơn giản và nhanh chóng nhất để tìm UCLN mà không cần phải viết code từ đầu.

Như vậy, tùy từng trường hợp mà chúng ta có thể lựa chọn cách phù hợp để tìm UCLN trong Pascal.

Chương trình tìm UCLN trong Pascal

Dưới đây là chương trình Pascal tìm UCLN của 2 số nguyên dương a và b mà người dùng nhập vào từ bàn phím:

program UCLN;

function GCD(a, b: integer): integer;  
begin
  if (b = 0) then
    GCD := a
  else
    GCD := GCD(b, a mod b);
end;

var
  a, b: integer;

begin
  Write('Nhap so nguyen duong a: ');
  Readln(a);
   
  Write('Nhap so nguyen duong b: '); 
  Readln(b);
   
  Writeln('UCLN cua ', a, ' va ', b, ' la: ', GCD(a, b));
   
  Readln;  
end.

Chương trình sẽ yêu cầu người dùng nhập vào 2 số nguyên dương, sau đó gọi hàm GCD để tính và in ra UCLN của chúng.

Như vậy, bạn đã biết cách giải quyết bài toán tìm UCLN của 2 số trong Pascal. Hãy thực hành nhiều hơn để nắm chắc kỹ năng này nhé!

Một số lưu ý khi tìm UCLN trong Pascal

Dưới đây là một số lưu ý quan trọng khi viết chương trình tìm UCLN trong Pascal:

• Kiểm tra kỹ đầu vào, báo lỗi nếu người dùng nhập số âm hoặc bằng 0
• Sử dụng kiểu dữ liệu phù hợp (ví dụ integer thay vì byte) tránh tràn số
• Đảm bảo luôn a >= b trước khi gọi đệ quy để tối ưu thuật toán
• Xử lý trường hợp đặc biệt khi a = 0 hoặc b = 0 ngay từ đầu
• Viết code ngắn gọn, rõ ràng, tránh lặp lại code không cần thiết
• Bổ sung comment giải thích ý nghĩa các đoạn code chính

Hy vọng những lưu ý trên sẽ giúp các bạn viết được chương trình tìm UCLN đúng chuẩn và hiệu quả trong Pascal. Hãy không ngừng trau dồi và rèn luyện kỹ năng lập trình của mình nhé!