Mục tiêu buổi học
- Học vòng lặp
whilevà biết khi nào dùngwhilethay chofor. - Hiểu khái niệm ước chung, ƯCLN, bội chung, BCNN, hai số nguyên tố cùng nhau (toán lớp 6).
- Cài đặt thuật toán tìm ƯCLN bằng cách duyệt và bằng thuật toán Euclid; suy ra BCNN.
- Biết viết hàm
ucln(a, b),bcnn(a, b)và áp dụng giải bài toán thực tế (chia kẹo, xếp lịch trự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:
17 % 5bằng bao nhiêu?20 % 5bằng bao nhiêu?- Nếu
a % b == 0thìbcó quan hệ gì vớia? - 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?
- Hàm có kiểu trả về
intkhác hàmvoidở đ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à b | Số 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à b | Số 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 nhau | a 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í | for | while |
|---|---|---|
| Dùng khi | Biết trước số lần lặp | Chư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ển | Nằm ngay trong ngoặc | Tự 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ước | a | b | a % b |
|---|---|---|---|
| Ban đầu | 48 | 18 | 12 |
| Lần 1 | 18 | 12 | 6 |
| Lần 2 | 12 | 6 | 0 |
| Lần 3 | 6 | 0 | – |
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ỗi | Ví dụ | Cách sửa |
|---|---|---|
while lặp vô hạn | Quên i++ trong thân | Luôn cập nhật biến trong điều kiện |
| Sai điều kiện dừng Euclid | while (b == 0) | Viết while (b != 0) |
| Tràn số khi tính BCNN | a * b / ucln(a, b) | Viết a / ucln(a, b) * b, dùng long long |
| Quên dùng biến tạm | a = b; b = a % b; | Lưu r = a % b trước rồi mới gán |
| Truyền số 0 hoặc số âm | ucln(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
- Nhập hai số nguyên dương
a,b. Tìm ƯCLN bằng cách duyệt (dùngfor). - Tìm ƯCLN của
a,bbằng thuật toán Euclid (dùngwhile). - Tìm BCNN của
a,b. - Kiểm tra
avàbcó nguyên tố cùng nhau hay không.
Mức 2 – Vận dụng (gắn với toán học)
- Viết hàm
ucln(a, b)vàbcnn(a, b), in cả hai kết quả. - Nhập mảng
nsố nguyên dương, tìm ƯCLN của cả mảng. - Nhập mảng
nsố nguyên dương, tìm BCNN của cả mảng (dùnglong long). - Nhập
a,b, liệt kê tất cả các ước chung củaavàb. Gợi ý: ước chung là ước của ƯCLN. - Bài toán chia kẹo: có
akẹo cam vàbkẹ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
- Bài toán xếp lịch: hai bạn trực nhật
angày vàbngà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 trongkngày tới (nhậpk) họ cùng trực mấy lần? - Nhập phân số
a / b, rút gọn về phân số tối giản bằng ƯCLN. - Nhập
n, đếm số cặp(a, b)với1 ≤ a < b ≤ nnguyên tố cùng nhau.
8. Tổng kết
while: dùng khi chưa biết trước số lần lặp; phải có lệnh làm thay đổi điều kiện.- Euclid: lặp
(a, b) → (b, a % b)đến khib = 0, kết quả làa. BCNN(a, b) = a / ƯCLN(a, b) * b;a,bnguyên tố cùng nhau khi ƯCLN bằng 1.
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ố.