LẬP TRÌNH CẤU TRÚC C++
LEVEL 2
BUỔI 4. ƯỚC CHUNG, BỘI CHUNG – VÒNG LẶP while
Họ và tên: ............................................................Ngày học: .......................

Mục tiêu buổi học

Thời lượng: 90 phút (15 phút ôn bài cũ, 30 phút lý thuyết và ví dụ, 35 phút thực hành, 10 phút tổng kết).

1. Khởi động – ôn bài cũ

Trả lời nhanh:

  1. 17 % 5 bằng bao nhiêu? 20 % 5 bằng bao nhiêu?
  2. Nếu a % b == 0 thì b có quan hệ gì với a?
  3. Biến cộng dồn khởi tạo bằng mấy, biến nhân dồn khởi tạo bằng mấy?
  4. Hàm có kiểu trả về int khác hàm void ở điểm nào? (Level 1, Bài 9)

2. Kiến thức toán: ước chung và bội chung

Khái niệmÝ nghĩa
Ước chung của a và bSố chia hết cho cả a và b
ƯCLN(a, b)Ước chung lớn nhất của a và b
Bội chung của a và bSố chia hết cho cả a và b
BCNN(a, b)Bội chung nhỏ nhất (khác 0) của a và b
Nguyên tố cùng nhaua và b có ƯCLN(a, b) = 1

Ví dụ: ƯCLN(12, 18) = 6; BCNN(12, 18) = 36; 7 và 13 là hai số nguyên tố cùng nhau.

Công thức liên hệ: ƯCLN(a, b) × BCNN(a, b) = a × b, suy ra BCNN(a, b) = a × b / ƯCLN(a, b).

3. Vòng lặp while

while lặp lại khối lệnh khi điều kiện còn đúng. Điều kiện được kiểm tra trước mỗi lần lặp.

while (dieu_kien) {
    // than vong lap
    // phai co lenh lam thay doi dieu kien
}
Tiêu chíforwhile
Dùng khiBiết trước số lần lặpChưa biết trước số lần lặp
Ví dụIn 1 → 100, nhập 10 sốNhập lại đến khi hợp lệ, thuật toán Euclid
Biến điều khiểnNằm ngay trong ngoặcTự khai báo và tự cập nhật trong thân

3.1. Ví dụ 1 – Nhập số nguyên dương, nhập lại đến khi hợp lệ

int n;
cout << "Nhap n (n > 0): ";
cin >> n;
while (n <= 0) {
    cout << "Sai! Nhap lai n (n > 0): ";
    cin >> n;
}
cout << "Ban da nhap n = " << n << endl;

3.2. Ví dụ 2 – In các số từ 1 đến n bằng while

int i = 1;                 // khoi tao
while (i <= n) {           // dieu kien
    cout << i << " ";
    i++;                   // buoc nhay - khong duoc quen
}

Lưu ý: nếu quên i++ thì điều kiện i <= n luôn đúng và chương trình lặp vô hạn (nhấn Ctrl + C để dừng).

4. Tìm ƯCLN và BCNN

4.1. Cách 1 – Duyệt từ số nhỏ nhất xuống 1

Ý tưởng: ƯCLN không thể lớn hơn min(a, b). Thử i từ min(a, b) giảm dần, số đầu tiên chia hết cho cả hai chính là ƯCLN.

int ucln_duyet(int a, int b) {
    int nho = (a < b) ? a : b;
    for (int i = nho; i >= 1; i--) {
        if (a % i == 0 && b % i == 0)
            return i;           // gap so dau tien -> la UCLN
    }
    return 1;
}

4.2. Cách 2 – Thuật toán Euclid

Ý tưởng: ƯCLN(a, b) = ƯCLN(b, a % b). Lặp đến khi b = 0 thì ƯCLN chính là a.

int ucln(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Chạy tay với ucln(48, 18):

Bướcaba % b
Ban đầu481812
Lần 118126
Lần 21260
Lần 360–

Khi b = 0 vòng lặp dừng, ƯCLN(48, 18) = a = 6. Thuật toán Euclid chỉ cần vài vòng lặp ngay cả với số rất lớn, nhanh hơn cách duyệt nhiều.

4.3. Tìm BCNN và kiểm tra nguyên tố cùng nhau

long long bcnn(long long a, long long b) {
    return a / ucln(a, b) * b;   // chia truoc, nhan sau de tranh tran so
}

bool nguyenToCungNhau(int a, int b) {
    return ucln(a, b) == 1;
}

Lưu ý: viết a / ucln(a, b) * b thay vì a * b / ucln(a, b) để tích không vượt quá giới hạn kiểu dữ liệu.

4.4. Ví dụ 3 – Chương trình hoàn chỉnh

#include <iostream>
using namespace std;

int ucln(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    cout << "Nhap a, b (duong): ";
    cin >> a >> b;

    int u = ucln(a, b);
    long long b_chung = (long long)a / u * b;
    cout << "UCLN = " << u << endl;
    cout << "BCNN = " << b_chung << endl;
    if (u == 1)
        cout << "a va b nguyen to cung nhau" << endl;
    return 0;
}

4.5. Ví dụ 4 – ƯCLN của một mảng

Ý tưởng: ƯCLN(a₁, a₂, a₃, …) = ƯCLN(ƯCLN(a₁, a₂), a₃, …). Dùng một biến kq và cập nhật dần.

int a[100], n;
cin >> n;
for (int i = 0; i < n; i++)
    cin >> a[i];

int kq = a[0];
for (int i = 1; i < n; i++)
    kq = ucln(kq, a[i]);
cout << "UCLN cua mang = " << kq << endl;

5. Ứng dụng thực tế

Bài toán chia kẹo: có 24 kẹo cam và 36 kẹo chanh, chia vào các túi giống nhau (mỗi túi đủ cả hai loại, không thừa kẹo). Chia được nhiều nhất bao nhiêu túi?

Số túi phải là ước chung của 24 và 36, nhiều nhất là ƯCLN(24, 36) = 12 túi. Mỗi túi có 24 / 12 = 2 kẹo cam và 36 / 12 = 3 kẹo chanh.

Bài toán xếp lịch: An trực nhật 4 ngày một lần, Bình 6 ngày một lần. Hôm nay cả hai cùng trực, sau ít nhất bao nhiêu ngày nữa lại cùng trực? Đáp số: BCNN(4, 6) = 12 ngày.

6. Lỗi thường gặp

LỗiVí dụCách sửa
while lặp vô hạnQuên i++ trong thânLuôn cập nhật biến trong điều kiện
Sai điều kiện dừng Euclidwhile (b == 0)Viết while (b != 0)
Tràn số khi tính BCNNa * b / ucln(a, b)Viết a / ucln(a, b) * b, dùng long long
Quên dùng biến tạma = b; b = a % b;Lưu r = a % b trước rồi mới gán
Truyền số 0 hoặc số âmucln(0, 0)Kiểm tra a, b dương trước khi gọi

7. Bài tập thực hành

Mức 1 – Cơ bản

  1. Nhập hai số nguyên dương a, b. Tìm ƯCLN bằng cách duyệt (dùng for).
  2. Tìm ƯCLN của a, b bằng thuật toán Euclid (dùng while).
  3. Tìm BCNN của a, b.
  4. Kiểm tra a và b có nguyên tố cùng nhau hay không.

Mức 2 – Vận dụng (gắn với toán học)

  1. Viết hàm ucln(a, b) và bcnn(a, b), in cả hai kết quả.
  2. Nhập mảng n số nguyên dương, tìm ƯCLN của cả mảng.
  3. Nhập mảng n số nguyên dương, tìm BCNN của cả mảng (dùng long long).
  4. Nhập a, b, liệt kê tất cả các ước chung của a và b. Gợi ý: ước chung là ước của ƯCLN.
  5. Bài toán chia kẹo: có a kẹo cam và b kẹo chanh. Chia được nhiều nhất bao nhiêu túi giống nhau, mỗi túi có bao nhiêu kẹo mỗi loại?

Mức 3 – Nâng cao

  1. Bài toán xếp lịch: hai bạn trực nhật a ngày và b ngày một lần, hôm nay cùng trực. Sau bao nhiêu ngày thì lại cùng trực? Hỏi trong k ngày tới (nhập k) họ cùng trực mấy lần?
  2. Nhập phân số a / b, rút gọn về phân số tối giản bằng ƯCLN.
  3. Nhập n, đếm số cặp (a, b) với 1 ≤ a < b ≤ n nguyên tố cùng nhau.

8. Tổng kết

Bài tập về nhà: hoàn thành bài 5, 6, 8, 9 (bắt buộc), bài 10 – 12 (khuyến khích).

Chuẩn bị cho Buổi 5: ôn hàm laNguyenTo (Level 1, Bài 9), nhớ khái niệm số nguyên tố và hợp số.