Tiếp tục chuỗi bài viết về CTDL & Thuật toán, hôm nay chúng ta sẽ cùng tìm hiểu về thuật toán tìm UCLN và BCNN trong lập trình C/C++. Bài viết này sẽ giúp bạn hiểu rõ hơn về cách tìm ước chung lớn nhất và bội chung nhỏ nhất của hai số nguyên trong lập trình.
Giới thiệu bài toán UCLN và BCNN
Bài toán tìm ước chung lớn nhất và bội chung nhỏ nhất trong lập trình C/C++ là một bài toán rất thú vị và quan trọng. Bài toán này có thể được nêu dưới dạng: "Tìm ước chung lớn nhất hoặc bội chung nhỏ nhất của hai số nguyên A và B".
Ước của một số X là số Y mà X có thể chia hết cho Y, ví dụ 2 là ước của 4. UCLN của hai số A và B là ước lớn nhất của cả hai số đó (tức là số lớn nhất mà cả A và B đều chia hết). UCLN có thể là chính số A hoặc B, 1 hoặc bất kỳ số nguyên nào khác.
Tương tự, bội của một số X là số Y mà Y có thể chia hết cho X, ví dụ 4 là bội của 2. BCNN của hai số A và B là bội nhỏ nhất của cả hai số đó (tức là số nhỏ nhất mà có thể chia hết cho cả A và B). BCNN có thể là chính số A hoặc B, hoặc bất kỳ số nguyên nào khác, tuy nhiên BCNN không thể nhỏ hơn A hoặc B.
Có 3 cách thường dùng để tìm UCLN trong lập trình:
Cách 1: Kiểm tra tuần tự
Cách này dựa trên ý tưởng kiểm tra từng số tuần tự để tìm UCLN. Cụ thể, chúng ta thực hiện các bước sau:
- Bước 1: Tìm số minab = min(A,B) - Tìm số nhỏ hơn giữa 2 số A và B.
- Bước 2: Duyệt vòng lặp i chạy ngược từ minAB tới 1 (tính cả số 1 và minAB).
- Bước 3: Nếu cả 2 số A, B đều chia hết i dừng thuật toán, và i chính là UCLN cần tìm.
Cách 2: Tìm UCLN sử dụng phép trừ
Thuật toán này dựa trên ý tưởng lấy số lớn hơn trừ đi số nhỏ hơn, sau đó gán lại giá trị bằng chính hiệu vừa tính được. Khi hai số bằng nhau thì đó chính là ước chung lớn nhất.
Cách 3: Tìm UCLN sử dụng phép chia (giải thuật Euclid)
Thuật toán này sử dụng công thức toán học a = b*x + r, trong đó a chia b sẽ được x lần và dư r. Với thuật toán này, bạn có thể hiểu đơn giản như sau: Lấy a%b được r, gắn lại a = b, b=r, lúc này bài toán quay lại tìm UCLN của b và r. Thực hiện lặp cho tới khi r = 0 thì b chính là kết quả ta cần tìm. Thuật toán này có độ phức tạp rất thấp nên thường được ưu tiên trong các bài toán thực tế.
Để tìm BCNN, sau khi đã có UCLN ta chỉ việc lấy tích A, B chia cho UCLN.
Cảm ơn bạn đã đọc bài viết này. Chúc bạn thành công trong việc học lập trình!
