1. Khai báo và sử dụng hàm tự định nghĩa trong C++
1.1. Tại sao cần hàm tự định nghĩa?
Khi chương trình phức tạp, việc viết tất cả mã trong main() sẽ gây khó khăn:
- Khó đọc, khó bảo trì
- Lặp lại mã nhiều lần
- Khó tái sử dụng
Hàm tự định nghĩa giúp chia chương trình thành các phần nhỏ, mỗi phần thực hiện một nhiệm vụ cụ thể.
1.2. Cấu trúc hàm cơ bản
// Cú pháp tổng quát
kiểu_trả_về tên_hàm(danh_sách_tham_số) {
// Thân hàm
return giá_trị; // (nếu kiểu trả về khác void)
}
Ví dụ 1: Hàm tính giai thừa
#include <iostream>
using namespace std;
// Khai báo hàm (prototype)
int tinhGiaiThua(int n);
int main() {
int n = 5;
int ketQua = tinhGiaiThua(n);
cout << n << "! = " << ketQua << endl;
return 0;
}
// Định nghĩa hàm
int tinhGiaiThua(int n) {
int giaiThua = 1;
for (int i = 1; i <= n; i++) {
giaiThua *= i;
}
return giaiThua;
}
1.3. Các loại hàm thường gặp
| Loại hàm |
Mô tả |
Ví dụ |
| Không trả về |
Dùng void, không có return |
void inMenu() |
| Có trả về |
Trả về giá trị xác định |
int tong(int a, int b) |
| Không tham số |
Không nhận đầu vào |
int nhapSo() |
| Có tham số |
Nhận giá trị đầu vào |
double tinhDienTich(double r) |
1.4. Truyền tham số
Bảng so sánh truyền tham trị và tham chiếu:
| Đặc điểm |
Truyền tham trị |
Truyền tham chiếu |
| Cú pháp |
void ham(int x) |
void ham(int &x) |
| Bản sao |
Tạo bản sao của giá trị |
Không tạo bản sao |
| Thay đổi |
Không ảnh hưởng biến gốc |
Ảnh hưởng trực tiếp biến gốc |
| Hiệu suất |
Chậm với kiểu dữ liệu lớn |
Nhanh với kiểu dữ liệu lớn |
| Ứng dụng |
Khi không cần thay đổi giá trị gốc |
Khi cần thay đổi giá trị gốc |
Ví dụ 2: So sánh truyền tham trị và tham chiếu
#include <iostream>
using namespace std;
// Truyền tham trị - KHÔNG thay đổi giá trị gốc
void tangGiaTriThamTri(int x) {
x = x + 10;
cout << "Trong ham (tham tri): x = " << x << endl;
}
// Truyền tham chiếu - CÓ thay đổi giá trị gốc
void tangGiaTriThamChieu(int &x) {
x = x + 10;
cout << "Trong ham (tham chieu): x = " << x << endl;
}
int main() {
int a = 5;
cout << "Truoc khi goi ham:" << endl;
cout << "a = " << a << endl << endl;
// Gọi hàm tham trị
tangGiaTriThamTri(a);
cout << "Sau khi goi ham tham tri:" << endl;
cout << "a = " << a << endl << endl;
// Gọi hàm tham chiếu
tangGiaTriThamChieu(a);
cout << "Sau khi goi ham tham chieu:" << endl;
cout << "a = " << a << endl;
return 0;
}
Kết quả:
Truoc khi goi ham:
a = 5
Trong ham (tham tri): x = 15
Sau khi goi ham tham tri:
a = 5
Trong ham (tham chieu): x = 15
Sau khi goi ham tham chieu:
a = 15
1.5. Hàm trả về nhiều giá trị (sử dụng tham chiếu)
#include <iostream>
using namespace std;
// Hàm trả về nhiều giá trị qua tham chiếu
void tinhToan(int a, int b, int &tong, int &hieu, int &tich) {
tong = a + b;
hieu = a - b;
tich = a * b;
}
int main() {
int x = 10, y = 4;
int tong, hieu, tich;
tinhToan(x, y, tong, hieu, tich);
cout << "x = " << x << ", y = " << y << endl;
cout << "Tong: " << tong << endl;
cout << "Hieu: " << hieu << endl;
cout << "Tich: " << tich << endl;
return 0;
}
1.6. Quy tắc đặt tên hàm tốt
- Mô tả rõ ràng: Tên hàm nên nói lên chức năng
- Sử dụng động từ:
calculate, display, find, validate
- Quy tắc lạc đà:
tinhTongHaiSo()
- Nhất quán: Cùng một phong cách đặt tên
1.7. Lưu đồ hoạt động của hàm
┌─────────────────────────────────────────┐
│ Chương trình chính │
│ ┌───────────────────────────────────┐ │
│ │ Gọi hàm: ketQua = tinhTong(a, b) │ │
│ └───────────────────────────────────┘ │
│ ↓ │
│ ┌───────────────────────────────────┐ │
│ │ Thực thi hàm tinhTong() │ │
│ │ 1. Nhận tham số a, b │ │
│ │ 2. Tính tổng = a + b │ │
│ │ 3. Trả về tổng │ │
│ └───────────────────────────────────┘ │
│ ↑ │
│ ┌───────────────────────────────────┐ │
│ │ Nhận kết quả và tiếp tục xử lý │ │
│ └───────────────────────────────────┘ │
└─────────────────────────────────────────┘
1.8. Bài tập thực hành
Bài tập 1: Viết hàm kiểm tra số nguyên tố
#include <iostream>
#include <cmath>
using namespace std;
bool laSoNguyenTo(int n) {
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cout << "Nhap so can kiem tra: ";
cin >> n;
if (laSoNguyenTo(n)) {
cout << n << " la so nguyen to" << endl;
} else {
cout << n << " khong la so nguyen to" << endl;
}
return 0;
}
Bài tập 2: Viết hàm đổi chỗ hai số
#include <iostream>
using namespace std;
void doiCho(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int main() {
int x = 5, y = 10;
cout << "Truoc khi doi: x = " << x << ", y = " << y << endl;
doiCho(x, y);
cout << "Sau khi doi: x = " << x << ", y = " << y << endl;
return 0;
}
Tổng kết phần 1
Hàm tự định nghĩa là công cụ mạnh mẽ giúp:
- Tổ chức mã nguồn rõ ràng, dễ đọc
- Tái sử dụng mã nhiều lần
- Giảm lỗi và dễ bảo trì
- Chia nhỏ vấn đề phức tạp thành các phần đơn giản
Mẹo nhớ:
- Khai báo hàm trước khi sử dụng (hoặc đặt prototype)
- Chọn kiểu trả về phù hợp
- Phân biệt rõ tham trị và tham chiếu
- Đặt tên hàm rõ ràng, dễ hiểu
2. Phương pháp đệ quy và bài toán sinh/duyệt cấu hình tổ hợp
2.1. Đệ quy là gì?
Đệ quy là kỹ thuật mà một hàm gọi chính nó để giải quyết bài toán. Mỗi lần gọi sẽ xử lý một phiên bản nhỏ hơn của bài toán ban đầu.
Ví dụ thực tế về đệ quy:
- Matryoshka dolls (búp bê Nga): Búp bê lớn chứa búp bê nhỏ hơn, cứ thế tiếp tục
- Hình ảnh phản chiếu trong gương: Gương chiếu vào gương tạo ra hình ảnh lặp vô hạn
- Tìm đường ra mê cung: Tại mỗi ngã rẽ, áp dụng cùng chiến lược
2.2. Cấu trúc cơ bản của hàm đệ quy
Một hàm đệ quy cần có 2 phần:
- Phần cơ sở (base case): Điều kiện dừng
- Phần đệ quy (recursive case): Gọi chính hàm đó với bài toán nhỏ hơn
void hamDeQuy(thamsố) {
// 1. Kiểm tra điều kiện dừng
if (điều_kiện_dừng) {
return;
}
// 2. Xử lý công việc hiện tại
// 3. Gọi đệ quy với bài toán nhỏ hơn
hamDeQuy(thamsố_mới);
}
2.3. Ví dụ 1: Tính giai thừa bằng đệ quy
Công thức toán học:
~
n! = \begin{cases}
1 & \text{nếu } n = 0 \\
n \times (n-1)! & \text{nếu } n > 0
\end{cases}
~
Mã nguồn:
#include <iostream>
using namespace std;
// Hàm đệ quy tính giai thừa
int giaiThua(int n) {
// Phần cơ sở
if (n == 0 || n == 1) {
return 1;
}
// Phần đệ quy
return n * giaiThua(n - 1);
}
int main() {
int n = 5;
cout << n << "! = " << giaiThua(n) << endl;
// Hiển thị quá trình đệ quy
cout << "\nQua trinh de quy:" << endl;
for (int i = 0; i <= n; i++) {
cout << "giaiThua(" << i << ") = " << giaiThua(i) << endl;
}
return 0;
}
Sơ đồ thực thi giaiThua(5):
giaiThua(5)
│
├─ return 5 * giaiThua(4)
│ │
│ ├─ return 4 * giaiThua(3)
│ │ │
│ │ ├─ return 3 * giaiThua(2)
│ │ │ │
│ │ │ ├─ return 2 * giaiThua(1)
│ │ │ │ │
│ │ │ │ └─ return 1
│ │ │ │
│ │ │ └─ return 2 * 1 = 2
│ │ │
│ │ └─ return 3 * 2 = 6
│ │
│ └─ return 4 * 6 = 24
│
└─ return 5 * 24 = 120
2.4. Ví dụ 2: Dãy Fibonacci
Công thức toán học:
~
F_n = \begin{cases}
0 & \text{nếu } n = 0 \\
1 & \text{nếu } n = 1 \\
F_{n-1} + F_{n-2} & \text{nếu } n > 1
\end{cases}
~
#include <iostream>
using namespace std;
int fibonacci(int n) {
// Phần cơ sở
if (n == 0) return 0;
if (n == 1) return 1;
// Phần đệ quy
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 6;
cout << "Day Fibonacci den phan tu thu " << n << ":" << endl;
for (int i = 0; i <= n; i++) {
cout << "F(" << i << ") = " << fibonacci(i) << endl;
}
return 0;
}
2.5. Call Stack (Ngăn xếp gọi hàm)
Khi hàm đệ quy được gọi, mỗi lần gọi được lưu vào call stack:
Thời gian →
↓
┌─────────────┐
│ giaiThua(1) │ ← Trả về 1
├─────────────┤
│ giaiThua(2) │ ← Chờ giaiThua(1)
├─────────────┤
│ giaiThua(3) │ ← Chờ giaiThua(2)
├─────────────┤
│ giaiThua(4) │ ← Chờ giaiThua(3)
├─────────────┤
│ giaiThua(5) │ ← Chờ giaiThua(4)
├─────────────┤
│ main() │ ← Chờ giaiThua(5)
└─────────────┘
2.6. Bài toán sinh/duyệt cấu hình tổ hợp
2.6.1. Sinh dãy nhị phân độ dài n
Bài toán: Liệt kê tất cả dãy nhị phân có độ dài n
#include <iostream>
using namespace std;
int n;
int x[100]; // Mảng lưu dãy nhị phân
// Hàm in dãy nhị phân
void inKetQua() {
for (int i = 1; i <= n; i++) {
cout << x[i];
}
cout << endl;
}
// Hàm đệ quy sinh dãy nhị phân
void sinhNhiPhan(int i) { // i là vị trí đang xét
// Duyệt tất cả khả năng cho vị trí thứ i
for (int j = 0; j <= 1; j++) {
x[i] = j; // Thử đặt bit thứ i = j
if (i == n) {
// Nếu đã xét hết n vị trí thì in kết quả
inKetQua();
} else {
// Nếu chưa xét hết thì tiếp tục đệ quy
sinhNhiPhan(i + 1);
}
}
}
int main() {
cout << "Nhap n: ";
cin >> n;
cout << "\nCac day nhi phan do dai " << n << ":" << endl;
sinhNhiPhan(1); // Bắt đầu từ vị trí thứ 1
return 0;
}
Khi n = 3, cây đệ quy sẽ như sau:
sinhNhiPhan(1)
├─ x[1]=0
│ ├─ sinhNhiPhan(2)
│ │ ├─ x[2]=0
│ │ │ ├─ sinhNhiPhan(3)
│ │ │ │ ├─ x[3]=0 → In: 000
│ │ │ │ └─ x[3]=1 → In: 001
│ │ │ └─ ...
│ │ └─ x[2]=1
│ │ ├─ sinhNhiPhan(3)
│ │ │ ├─ x[3]=0 → In: 010
│ │ │ └─ x[3]=1 → In: 011
│ └─ ...
└─ x[1]=1
├─ sinhNhiPhan(2)
│ ├─ x[2]=0
│ │ ├─ sinhNhiPhan(3)
│ │ │ ├─ x[3]=0 → In: 100
│ │ │ └─ x[3]=1 → In: 101
│ │ └─ ...
│ └─ x[2]=1
│ ├─ sinhNhiPhan(3)
│ │ ├─ x[3]=0 → In: 110
│ │ └─ x[3]=1 → In: 111
└─ ...
2.6.2. Sinh hoán vị (Permutations)
Bài toán: Liệt kê tất cả hoán vị của n phần tử (1, 2, ..., n)
#include <iostream>
using namespace std;
int n;
int x[100]; // Mảng lưu hoán vị hiện tại
bool used[100]; // Mảng đánh dấu phần tử đã dùng
void inKetQua() {
for (int i = 1; i <= n; i++) {
cout << x[i] << " ";
}
cout << endl;
}
void sinhHoanVi(int i) {
for (int j = 1; j <= n; j++) {
if (!used[j]) { // Nếu số j chưa được dùng
x[i] = j; // Chọn j cho vị trí i
used[j] = true; // Đánh dấu đã dùng
if (i == n) {
inKetQua(); // Đủ n phần tử thì in
} else {
sinhHoanVi(i + 1); // Tiếp tục đệ quy
}
used[j] = false; // Quay lui (bỏ đánh dấu)
}
}
}
int main() {
cout << "Nhap n: ";
cin >> n;
cout << "\nCac hoan vi cua " << n << " phan tu:" << endl;
sinhHoanVi(1);
return 0;
}
2.6.3. Sinh tổ hợp (Combinations)
Bài toán: Liệt kê tất cả tổ hợp chập k của n phần tử
#include <iostream>
using namespace std;
int n, k;
int x[100]; // Mảng lưu tổ hợp hiện tại
void inKetQua() {
for (int i = 1; i <= k; i++) {
cout << x[i] << " ";
}
cout << endl;
}
void sinhToHop(int i) {
// Giá trị thử cho x[i] từ x[i-1] + 1 đến n-k+i
for (int j = x[i-1] + 1; j <= n - k + i; j++) {
x[i] = j;
if (i == k) {
inKetQua(); // Đủ k phần tử thì in
} else {
sinhToHop(i + 1); // Tiếp tục đệ quy
}
}
}
int main() {
cout << "Nhap n, k: ";
cin >> n >> k;
x[0] = 0; // Khởi tạo giá trị cho x[0]
cout << "\nCac to hop chap " << k << " cua " << n << " phan tu:" << endl;
sinhToHop(1);
return 0;
}
2.7. Mô hình backtracking (Quay lui)
Backtracking là kỹ thuật duyệt tất cả khả năng có thể xảy ra:
procedure backtrack(c):
if c là cấu hình đầy đủ then:
xử_lý(c)
else:
for each khả_năng cho vị_trí_tiếp_theo do:
if khả_năng này chấp_nhận_được then:
chọn khả_năng này
backtrack(cập_nhật_c)
bỏ_chọn (quay lui)
2.8. Bài tập ứng dụng: Bài toán 8 hậu
Bài toán: Đặt 8 quân hậu trên bàn cờ 8×8 sao cho không có 2 quân nào ăn nhau.
#include <iostream>
using namespace std;
int n = 8;
int x[100]; // x[i] = cột đặt hậu ở hàng i
bool cot[100], cheoXuoi[100], cheoNguoc[100];
int dem = 0;
void inBanCo() {
cout << "\nCach dat thu " << ++dem << ":" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (x[i] == j) {
cout << "Q ";
} else {
cout << ". ";
}
}
cout << endl;
}
}
void datHau(int i) { // Đặt hậu ở hàng thứ i
for (int j = 1; j <= n; j++) {
// Kiểm tra có thể đặt hậu ở hàng i, cột j không
if (!cot[j] && !cheoXuoi[i - j + n] && !cheoNguoc[i + j]) {
x[i] = j; // Đặt hậu hàng i vào cột j
// Đánh dấu
cot[j] = true;
cheoXuoi[i - j + n] = true;
cheoNguoc[i + j] = true;
if (i == n) {
inBanCo(); // Đã đặt đủ 8 hậu
} else {
datHau(i + 1); // Đặt hậu tiếp theo
}
// Quay lui (bỏ đánh dấu)
cot[j] = false;
cheoXuoi[i - j + n] = false;
cheoNguoc[i + j] = false;
}
}
}
int main() {
cout << "Cac cach dat 8 quan hau tren ban co 8x8:" << endl;
datHau(1);
cout << "\nTong so cach: " << dem << endl;
return 0;
}
2.9. Ưu điểm và nhược điểm của đệ quy
Ưu điểm:
| Ưu điểm |
Mô tả |
| Mã ngắn gọn |
Giải quyết bài toán phức tạp bằng ít dòng mã |
| Dễ hiểu |
Phản ánh trực tiếp cấu trúc tự nhiên của bài toán |
| Phù hợp CTDL đệ quy |
Lý tưởng cho cây, đồ thị, chia để trị |
Nhược điểm:
| Nhược điểm |
Mô tả |
Giải pháp |
| Tốn bộ nhớ |
Mỗi lần gọi đệ quy tốn stack frame |
Dùng vòng lặp hoặc đệ quy có nhớ |
| Hiệu suất |
Có thể tính lại cùng giá trị nhiều lần |
Memoization (phần 4) |
| Khó debug |
Khó theo dõi luồng thực thi |
In log, dùng debugger |
| Tràn stack |
Gọi đệ quy quá sâu gây stack overflow |
Tăng kích thước stack hoặc đổi sang vòng lặp |
2.10. Khi nào nên dùng đệ quy?
- Bài toán có cấu trúc đệ quy tự nhiên
- Duyệt cây/thư mục
- Bài toán chia để trị
- Quay lui, sinh cấu hình
- Định nghĩa toán học đệ quy (Fibonacci, giai thừa)
2.11. Bài tập thực hành
Bài 1: Đếm số cách bước cầu thang
Có n bậc thang, mỗi bước có thể đi 1 hoặc 2 bậc. Đếm số cách đi.
#include <iostream>
using namespace std;
int demCach(int n) {
if (n <= 1) return 1;
return demCach(n - 1) + demCach(n - 2);
}
int main() {
int n;
cout << "Nhap so bac thang: ";
cin >> n;
cout << "So cach di: " << demCach(n) << endl;
return 0;
}
Bài 2: Tìm ước số chung lớn nhất (USCLN)
#include <iostream>
using namespace std;
int USCLN(int a, int b) {
if (b == 0) return a;
return USCLN(b, a % b);
}
int main() {
int a, b;
cout << "Nhap hai so: ";
cin >> a >> b;
cout << "USCLN(" << a << ", " << b << ") = " << USCLN(a, b) << endl;
return 0;
}
Tổng kết phần 2
Đệ quy là công cụ mạnh mẽ với đặc điểm:
- Tư duy chia để trị: Chia bài toán lớn thành bài toán nhỏ tương tự
- Cần điều kiện dừng rõ ràng: Tránh đệ quy vô hạn
- Phù hợp với bài toán tổ hợp: Sinh hoán vị, tổ hợp, chỉnh hợp
Lưu ý quan trọng:
- Luôn xác định điều kiện dừng trước khi viết hàm đệ quy
- Đảm bảo mỗi lần đệ quy tiến gần đến điều kiện dừng
- Cẩn thận với tràn stack khi đệ quy quá sâu
- Với bài toán tính toán, xem xét đệ quy có nhớ để tối ưu
3. Phương pháp chia để trị (Divide and Conquer)
3.1. Tổng quan về chia để trị
Chia để trị là phương pháp thiết kế thuật toán bằng cách chia bài toán lớn thành các bài toán nhỏ hơn, giải quyết từng bài toán nhỏ, rồi kết hợp kết quả để giải bài toán ban đầu.
Quy trình 3 bước:
CHIA ĐỂ TRỊ
│
┌───────┴────────┐
│ │
1. CHIA 3. TRỊ
Chia bài toán Kết hợp
thành các lời giải
phần nhỏ từ các
│ phần nhỏ
└───────┬────────┘
│
2. TRỊ
Giải quyết
từng phần
nhỏ (đệ quy)
3.2. Mô hình tổng quát
KiểuDữLiệu chiaDeTri(DữLiệu đầu_vào) {
// 1. Kiểm tra điều kiện dừng (trường hợp cơ sở)
if (kích_thước(đầu_vào) đủ_nhỏ) {
return giải_trực_tiếp(đầu_vào);
}
// 2. CHIA: Chia bài toán thành k phần nhỏ hơn
DữLiệu phần_1 = chia(đầu_vào, 1);
DữLiệu phần_2 = chia(đầu_vào, 2);
// ...
DữLiệu phần_k = chia(đầu_vào, k);
// 3. TRỊ: Giải quyết đệ quy từng phần
KếtQuả kq_1 = chiaDeTri(phần_1);
KếtQuả kq_2 = chiaDeTri(phần_2);
// ...
KếtQuả kq_k = chiaDeTri(phần_k);
// 4. KẾT HỢP: Tổng hợp kết quả
return kết_hợp(kq_1, kq_2, ..., kq_k);
}
3.3. Ví dụ 1: Tìm kiếm nhị phân (Binary Search)
Mô tả:
Cho một mảng đã sắp xếp, tìm vị trí của phần tử x.
Ý tưởng:
- So sánh x với phần tử giữa mảng
- Nếu bằng → tìm thấy
- Nếu x nhỏ hơn → tìm trong nửa trái
- Nếu x lớn hơn → tìm trong nửa phải
Sơ đồ hoạt động:
Tìm số 23 trong mảng [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Bước 1: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
↑ ↑ ↑
left=0 mid=4 right=9
arr[mid] = 16 < 23 → tìm bên phải
Bước 2: [23, 38, 56, 72, 91]
↑ ↑ ↑
left=5 mid=7 right=9
arr[mid] = 56 > 23 → tìm bên trái
Bước 3: [23, 38]
↑ ↑ ↑
l=5 m=6 r=7
arr[mid] = 38 > 23 → tìm bên trái
Bước 4: [23]
↑
Tìm thấy tại vị trí 5
Mã nguồn:
#include <iostream>
#include <vector>
using namespace std;
// Hàm tìm kiếm nhị phân (đệ quy)
int binarySearch(vector<int>& arr, int left, int right, int x) {
// Điều kiện dừng: khoảng tìm kiếm không hợp lệ
if (left > right) {
return -1; // Không tìm thấy
}
// Tìm phần tử giữa
int mid = left + (right - left) / 2;
// So sánh
if (arr[mid] == x) {
return mid; // Tìm thấy
} else if (arr[mid] > x) {
// Tìm bên trái
return binarySearch(arr, left, mid - 1, x);
} else {
// Tìm bên phải
return binarySearch(arr, mid + 1, right, x);
}
}
// Hàm tìm kiếm nhị phân (không đệ quy - vòng lặp)
int binarySearchIterative(vector<int>& arr, int x) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
int main() {
vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x = 23;
// Sử dụng đệ quy
int result = binarySearch(arr, 0, arr.size() - 1, x);
if (result != -1) {
cout << "Tim thay " << x << " tai vi tri (de quy): " << result << endl;
} else {
cout << "Khong tim thay " << x << endl;
}
// Sử dụng vòng lặp
result = binarySearchIterative(arr, x);
if (result != -1) {
cout << "Tim thay " << x << " tai vi tri (vong lap): " << result << endl;
}
return 0;
}
3.4. Ví dụ 2: Sắp xếp trộn (Merge Sort)
Nguyên lý hoạt động:
[38, 27, 43, 3, 9, 82, 10]
CHIA
┌───────────────────────┐
[38, 27, 43, 3] [9, 82, 10]
CHIA CHIA
┌─────────────┐ ┌─────────┐
[38, 27] [43, 3] [9, 82] [10]
CHIA CHIA CHIA │
┌─────┐ ┌─────┐ ┌─────┐ │
[38] [27] [43] [3] [9] [82] [10]
│ │ │ │ │ │ │
TRỘN │ TRỘN │ TRỘN │ │
└─────┘ └─────┘ └─────┘ │
[27, 38] [3, 43] [9, 82] │
│ │ │ │
└───────────┼───────────┘ │
TRỘN │ │
┌──────┘ │
[3, 27, 38, 43] │
│ │
└──────────────┼──────────-─┘
TRỘN │
[3, 9, 10, 27, 38, 43, 82]
Mã nguồn:
#include <iostream>
#include <vector>
using namespace std;
// Hàm trộn hai mảng đã sắp xếp
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // Kích thước mảng trái
int n2 = right - mid; // Kích thước mảng phải
// Tạo mảng tạm
vector<int> L(n1), R(n2);
// Copy dữ liệu vào mảng tạm
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// Trộn hai mảng vào arr
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy phần còn lại của L (nếu có)
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy phần còn lại của R (nếu có)
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Hàm sắp xếp trộn (đệ quy)
void mergeSort(vector<int>& arr, int left, int right) {
// Điều kiện dừng: chỉ còn 1 phần tử
if (left >= right) {
return;
}
// Tìm điểm giữa
int mid = left + (right - left) / 2;
// Sắp xếp nửa trái
mergeSort(arr, left, mid);
// Sắp xếp nửa phải
mergeSort(arr, mid + 1, right);
// Trộn hai nửa đã sắp xếp
merge(arr, left, mid, right);
}
// Hàm in mảng
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
cout << "Mang ban dau: ";
printArray(arr);
mergeSort(arr, 0, arr.size() - 1);
cout << "Mang sau khi sap xep: ";
printArray(arr);
return 0;
}
3.5. Ví dụ 3: Sắp xếp nhanh (Quick Sort)
Nguyên lý:
- Chọn pivot (phần tử chốt)
- Phân hoạch: Đưa các phần tử nhỏ hơn pivot về bên trái, lớn hơn về bên phải
- Đệ quy áp dụng cho hai mảng con
Mã nguồn:
#include <iostream>
#include <vector>
using namespace std;
// Hàm phân hoạch: chọn pivot, sắp xếp và trả về vị trí pivot
int partition(vector<int>& arr, int low, int high) {
// Chọn pivot là phần tử cuối cùng
int pivot = arr[high];
// Chỉ số của phần tử nhỏ hơn pivot
int i = low - 1;
for (int j = low; j < high; j++) {
// Nếu phần tử hiện tại nhỏ hơn hoặc bằng pivot
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// Đưa pivot vào đúng vị trí
swap(arr[i + 1], arr[high]);
return i + 1;
}
// Hàm sắp xếp nhanh
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
// pi là chỉ số nơi pivot đã đúng vị trí
int pi = partition(arr, low, high);
// Sắp xếp đệ quy các phần bên trái và bên phải pivot
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Hàm in mảng
void printArray(const vector<int>& arr) {
for (int num : arr) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
cout << "Mang ban dau: ";
printArray(arr);
int n = arr.size();
quickSort(arr, 0, n - 1);
cout << "Mang sau khi sap xep nhanh: ";
printArray(arr);
return 0;
}
3.6. Đánh giá độ phức tạp
Bảng so sánh thuật toán chia để trị:
| Thuật toán |
Chia |
Trị (đệ quy) |
Kết hợp |
Độ phức tạp |
| Merge Sort |
O(1) |
2T(n/2) |
O(n) |
O(n log n) |
| Quick Sort |
O(n) |
T(k) + T(n-k-1) |
O(1) |
O(n log n) trung bình |
| Binary Search |
O(1) |
T(n/2) |
O(1) |
O(log n) |
Công thức tổng quát:
Nếu bài toán kích thước n được chia thành a bài toán con kích thước n/b, và việc chia/kết hợp tốn D(n)/C(n) thời gian, thì:
~
T(n) = \begin{cases}
\Theta(1) & \text{nếu } n \leq n_0 \\
aT(n/b) + D(n) + C(n) & \text{nếu } n > n_0
\end{cases}
~
3.9. Ưu điểm và nhược điểm
Ưu điểm:
| Ưu điểm |
Mô tả |
| Hiệu quả |
Giảm độ phức tạp từ O(n²) xuống O(n log n) |
| Song song hóa |
Dễ chia để xử lý song song |
| Tư duy rõ ràng |
Phản ánh cách tiếp cận tự nhiên |
| Tối ưu cache |
Làm việc tốt với bộ nhớ đệm |
Nhược điểm:
| Nhược điểm |
Giải pháp |
| Overhead đệ quy |
Có thể dùng vòng lặp hoặc stack |
| Khó cài đặt |
Cần xác định đúng cách chia/kết hợp |
| Không phải lúc nào cũng tốt nhất |
Tùy bài toán có thể có thuật toán tốt hơn |
3.10. Mẹo thiết kế thuật toán chia để trị
- Xác định trường hợp cơ sở: Bài toán nhỏ nhất có thể giải trực tiếp
- Chia đều nếu có thể: Chia thành các phần bằng nhau
- Tránh trùng lặp: Đảm bảo không giải cùng bài toán nhiều lần
- Kết hợp hiệu quả: Thiết kế bước kết hợp tối ưu
3.11. Bài tập thực hành
Bài 1: Tìm phần tử lớn nhất trong mảng
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Phương pháp chia để trị
int findMaxDivideConquer(vector<int>& arr, int left, int right) {
// Trường hợp cơ sở: chỉ có 1 phần tử
if (left == right) {
return arr[left];
}
// Trường hợp cơ sở: có 2 phần tử
if (right == left + 1) {
return max(arr[left], arr[right]);
}
// Chia mảng thành hai nửa
int mid = left + (right - left) / 2;
// Tìm max trong mỗi nửa
int maxLeft = findMaxDivideConquer(arr, left, mid);
int maxRight = findMaxDivideConquer(arr, mid + 1, right);
// Kết hợp kết quả
return max(maxLeft, maxRight);
}
int main() {
vector<int> arr = {3, 7, 2, 9, 1, 5, 8, 4};
cout << "Mang: ";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
int maxVal = findMaxDivideConquer(arr, 0, arr.size() - 1);
cout << "Phan tu lon nhat: " << maxVal << endl;
return 0;
}
Bài 2: Tính lũy thừa a^n
#include <iostream>
using namespace std;
// Tính a^n bằng chia để trị
double power(double a, int n) {
// Trường hợp cơ sở
if (n == 0) return 1;
if (n == 1) return a;
// Chia bài toán
double half = power(a, n / 2);
// Kết hợp kết quả
if (n % 2 == 0) {
return half * half; // a^n = a^(n/2) * a^(n/2)
} else {
return half * half * a; // a^n = a^(n/2) * a^(n/2) * a
}
}
int main() {
double a = 2;
int n = 10;
cout << a << "^" << n << " = " << power(a, n) << endl;
// So sánh với cách tính thông thường
double result = 1;
for (int i = 0; i < n; i++) {
result *= a;
}
cout << "Kiem tra: " << result << endl;
return 0;
}
Tổng kết phần 3
Chia để trị là kỹ thuật mạnh mẽ với các đặc điểm:
Các bước cơ bản:
- CHIA: Chia bài toán thành các bài toán con nhỏ hơn
- TRỊ: Giải quyết từng bài toán con (thường bằng đệ quy)
- KẾT HỢP: Tổng hợp lời giải từ các bài toán con
Ứng dụng điển hình:
- Sắp xếp: Merge Sort, Quick Sort
- Tìm kiếm: Binary Search
- Bài toán hình học: Tìm cặp điểm gần nhất
- Tính toán: Nhân ma trận Strassen, tính lũy thừa
Lưu ý quan trọng:
- Chọn điểm chia hợp lý: Thường chia đôi hoặc chia theo tỷ lệ cố định
- Hiệu quả bước kết hợp: Quyết định độ phức tạp của thuật toán
- Cân nhắc overhead: Đệ quy có thể tốn bộ nhớ, cân nhắc dùng vòng lặp
Quy tắc ngón tay cái:
- Nếu bài toán có thể chia thành các phần độc lập → chia để trị
- Nếu kích thước giảm theo cấp số nhân (n → n/2 → n/4...) → hiệu quả cao
- Nếu bước kết hợp đơn giản (O(1) hoặc O(n)) → khả thi
4. Phương pháp đệ quy có nhớ (Memoization)
4.1. Khái niệm về đệ quy có nhớ
Đệ quy có nhớ (Memoization) là kỹ thuật tối ưu hóa đệ quy bằng cách lưu trữ kết quả của các bài toán con đã được tính toán để tránh tính lại nhiều lần.
4.2. Vấn đề của đệ quy thông thường
Xét lại bài toán Fibonacci với đệ quy thông thường:
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
Cây đệ quy cho fibonacci(5):
fibonacci(5)
/ \
fibonacci(4) fibonacci(3)
/ \ / \
fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)
/ \ / \ / \
fibonacci(2) f(1) f(1) f(0) f(1) f(0)
/ \
f(1) f(0)
Nhận xét:
fibonacci(3) được tính 2 lầnfibonacci(2) được tính 3 lầnfibonacci(1) được tính 5 lần- Độ phức tạp: O(2^n) - rất kém hiệu quả
4.3. Nguyên lý hoạt động của đệ quy có nhớ
- Tạo bảng nhớ (thường là mảng hoặc bảng băm) để lưu kết quả
- Trước khi tính toán, kiểm tra xem kết quả đã có trong bảng nhớ chưa
- Nếu đã có, trả về kết quả từ bảng nhớ
- Nếu chưa có, tính toán, lưu vào bảng nhớ, rồi trả về
4.4. Cài đặt Fibonacci với đệ quy có nhớ
#include <iostream>
#include <vector>
using namespace std;
// Biến toàn cục để lưu kết quả đã tính
vector<long long> memo(100, -1); // -1 nghĩa là chưa được tính
long long fibonacciMemo(int n) {
// Nếu đã tính trước đó, trả về kết quả từ bảng nhớ
if (memo[n] != -1) {
return memo[n];
}
// Trường hợp cơ sở
if (n <= 1) {
memo[n] = n;
return n;
}
// Tính toán và lưu vào bảng nhớ
memo[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2);
return memo[n];
}
int main() {
int n;
cout << "Nhap n: ";
cin >> n;
// Khởi tạo bảng nhớ
fill(memo.begin(), memo.end(), -1);
cout << "Fibonacci(" << n << ") = " << fibonacciMemo(n) << endl;
// Hiển thị bảng nhớ
cout << "\nBang nho sau khi tinh:" << endl;
for (int i = 0; i <= n; i++) {
cout << "memo[" << i << "] = " << memo[i] << endl;
}
return 0;
}
4.5. So sánh hiệu suất
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
// Đệ quy thông thường
int fibNormal(int n) {
if (n <= 1) return n;
return fibNormal(n-1) + fibNormal(n-2);
}
// Đệ quy có nhớ
vector<long long> memo(100, -1);
long long fibMemo(int n) {
if (memo[n] != -1) return memo[n];
if (n <= 1) {
memo[n] = n;
return n;
}
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
int n = 40;
// Đo thời gian đệ quy thông thường
auto start1 = high_resolution_clock::now();
long long result1 = fibNormal(n);
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
// Đo thời gian đệ quy có nhớ
fill(memo.begin(), memo.end(), -1);
auto start2 = high_resolution_clock::now();
long long result2 = fibMemo(n);
auto stop2 = high_resolution_clock::now();
auto duration2 = duration_cast<milliseconds>(stop2 - start2);
cout << "So sanh hieu suat voi n = " << n << ":" << endl;
cout << "----------------------------------------" << endl;
cout << "De quy thong thuong:" << endl;
cout << " Ket qua: " << result1 << endl;
cout << " Thoi gian: " << duration1.count() << " ms" << endl;
cout << "\nDe quy co nho:" << endl;
cout << " Ket qua: " << result2 << endl;
cout << " Thoi gian: " << duration2.count() << " ms" << endl;
return 0;
}
4.6. Bài toán cái túi (Knapsack) với đệ quy có nhớ
Bài toán: Cho n đồ vật, mỗi đồ vật có trọng lượng w[i] và giá trị v[i]. Túi có sức chứa tối đa W. Tìm cách chọn các đồ vật để tổng giá trị lớn nhất mà không vượt quá trọng lượng W.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 100;
const int MAX_W = 1000;
int memo[MAX_N][MAX_W]; // Bảng nhớ
// Khởi tạo bảng nhớ với -1
void initializeMemo() {
for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_W; j++) {
memo[i][j] = -1;
}
}
}
// Hàm đệ quy có nhớ
int knapsackMemo(int W, vector<int>& weight, vector<int>& value, int n) {
// Trường hợp cơ sở
if (n == 0 || W == 0) {
return 0;
}
// Nếu đã tính trước đó, trả về kết quả
if (memo[n][W] != -1) {
return memo[n][W];
}
// Nếu trọng lượng vật thứ n lớn hơn sức chứa, bỏ qua
if (weight[n-1] > W) {
memo[n][W] = knapsackMemo(W, weight, value, n-1);
return memo[n][W];
}
// Trường hợp 1: Không lấy vật thứ n
int notTake = knapsackMemo(W, weight, value, n-1);
// Trường hợp 2: Lấy vật thứ n
int take = value[n-1] + knapsackMemo(W - weight[n-1], weight, value, n-1);
// Lấy giá trị lớn hơn và lưu vào bảng nhớ
memo[n][W] = max(notTake, take);
return memo[n][W];
}
// Hàm truy vết để biết cần lấy những vật nào
void traceSolution(int W, vector<int>& weight, vector<int>& value, int n) {
cout << "\nCac vat duoc chon:" << endl;
int i = n, w = W;
int totalWeight = 0, totalValue = 0;
while (i > 0 && w > 0) {
if (memo[i][w] != memo[i-1][w]) {
cout << "Vat " << i << " (trong luong: " << weight[i-1]
<< ", gia tri: " << value[i-1] << ")" << endl;
totalWeight += weight[i-1];
totalValue += value[i-1];
w -= weight[i-1];
}
i--;
}
cout << "\nTong trong luong: " << totalWeight << endl;
cout << "Tong gia tri: " << totalValue << endl;
}
int main() {
vector<int> value = {60, 100, 120};
vector<int> weight = {10, 20, 30};
int W = 50; // Sức chứa túi
int n = value.size();
initializeMemo();
int maxValue = knapsackMemo(W, weight, value, n);
cout << "Bai toan cai tui:" << endl;
cout << "Suc chua: " << W << endl;
cout << "So vat: " << n << endl;
cout << "\nGia tri lon nhat co the dat duoc: " << maxValue << endl;
// Truy vết
traceSolution(W, weight, value, n);
return 0;
}
4.7. Bài toán đường đi ngắn nhất (Grid Path)
Bài toán: Tìm số đường đi từ góc trên bên trái đến góc dưới bên phải trong lưới m×n, chỉ được di chuyển xuống hoặc sang phải.
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100;
long long memo[MAX][MAX];
// Khởi tạo bảng nhớ
void initializeGridMemo(int m, int n) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
memo[i][j] = -1;
}
}
}
// Đệ quy có nhớ
long long countPathsMemo(int m, int n) {
// Trường hợp cơ sở
if (m == 0 || n == 0) {
return 1; // Chỉ có 1 cách đi trên biên
}
// Kiểm tra bảng nhớ
if (memo[m][n] != -1) {
return memo[m][n];
}
// Số đường đi = đường đi từ ô trên + đường đi từ ô trái
memo[m][n] = countPathsMemo(m-1, n) + countPathsMemo(m, n-1);
return memo[m][n];
}
// Hiển thị bảng nhớ
void printMemo(int m, int n) {
cout << "\nBang nho:" << endl;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
cout << memo[i][j] << "\t";
}
cout << endl;
}
}
int main() {
int m = 3, n = 3;
initializeGridMemo(m, n);
cout << "So duong di trong luoi " << m << "x" << n << ": ";
cout << countPathsMemo(m, n) << endl;
printMemo(m, n);
return 0;
}
4.8. Các dạng bài toán phù hợp với đệ quy có nhớ
- Bài toán có cấu trúc con trùng lặp: Fibonacci, tổ hợp C(n,k)
- Bài toán tối ưu: Cái túi, đường đi ngắn nhất
- Bài toán đếm: Số cách bước thang, số đường đi
- Bài toán chuỗi: Xâu con chung dài nhất (LCS)
4.9. Bài tập thực hành
Bài 1: Tính tổ hợp C(n, k) với đệ quy có nhớ
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100;
vector<vector<long long>> combMemo(MAX, vector<long long>(MAX, -1));
long long combinationMemo(int n, int k) {
// Trường hợp cơ sở
if (k == 0 || k == n) {
return 1;
}
// Kiểm tra bảng nhớ
if (combMemo[n][k] != -1) {
return combMemo[n][k];
}
// Công thức: C(n,k) = C(n-1,k-1) + C(n-1,k)
combMemo[n][k] = combinationMemo(n-1, k-1) + combinationMemo(n-1, k);
return combMemo[n][k];
}
int main() {
int n = 10, k = 5;
// Khởi tạo trường hợp cơ sở
for (int i = 0; i <= n; i++) {
combMemo[i][0] = combMemo[i][i] = 1;
}
cout << "C(" << n << ", " << k << ") = " << combinationMemo(n, k) << endl;
return 0;
}
Bài 2: Bài toán đổi tiền (Coin Change)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int MAX = 1000;
vector<int> coinMemo(MAX, -1);
// Đổi số tiền amount bằng các đồng xu coins
int coinChangeMemo(vector<int>& coins, int amount) {
// Trường hợp cơ sở
if (amount == 0) return 0;
if (amount < 0) return -1;
// Kiểm tra bảng nhớ
if (coinMemo[amount] != -1) {
return coinMemo[amount];
}
int minCoins = INT_MAX;
// Thử từng đồng xu
for (int coin : coins) {
int subResult = coinChangeMemo(coins, amount - coin);
if (subResult >= 0) {
minCoins = min(minCoins, subResult + 1);
}
}
// Lưu kết quả vào bảng nhớ
coinMemo[amount] = (minCoins == INT_MAX) ? -1 : minCoins;
return coinMemo[amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
fill(coinMemo.begin(), coinMemo.end(), -1);
int result = coinChangeMemo(coins, amount);
cout << "Doi " << amount << " dong bang cac dong xu {1, 2, 5}" << endl;
cout << "So dong xu it nhat: " << result << endl;
return 0;
}
4.10. Bảng tổng hợp ứng dụng
| Bài toán |
Phương pháp tốt nhất |
Độ phức tạp |
Ghi chú |
| Tính Fibonacci |
Đệ quy có nhớ |
O(n) |
Tránh dùng đệ quy thường (O(2^n)) |
| Sắp xếp mảng |
Chia để trị (Merge/Quick Sort) |
O(n log n) |
Nhanh hơn sắp xếp chọn (O(n²)) |
| Tìm kiếm |
Chia để trị (Binary Search) |
O(log n) |
Yêu cầu mảng đã sắp xếp |
| Bài toán cái túi |
Đệ quy có nhớ/Quy hoạch động |
O(n×W) |
W là sức chứa túi |
| Sinh hoán vị |
Đệ quy quay lui |
O(n!) |
Duyệt toàn bộ |
| Tìm đường đi |
Đệ quy có nhớ |
O(m×n) |
m×n là kích thước lưới |
4.11. Lời khuyên thực hành
- Bắt đầu đơn giản: Luôn viết giải pháp đệ quy đơn giản trước
- Phân tích tính trùng lặp: Xác định xem bài toán con có bị tính lại không
- Chọn cấu trúc lưu trữ:
- Mảng 1D cho bài toán 1 tham số
- Mảng 2D cho bài toán 2 tham số
- Bảng băm cho tham số phức tạp
- Khởi tạo giá trị đặc biệt: Dùng -1, INT_MIN, v.v. để đánh dấu "chưa tính"
- Kiểm tra bảng nhớ trước: Luôn kiểm tra trước khi tính toán
4.12. Công thức chuyển đổi từ đệ quy thường sang đệ quy có nhớ
- Bước 1: Thêm tham số bảng nhớ vào hàm
- Bước 2: Kiểm tra bảng nhớ ở đầu hàm
- Bước 3: Lưu kết quả vào bảng nhớ trước khi return
- Bước 4: Khởi tạo bảng nhớ ở hàm gọi
