Trong hầu hết các trường hợp, các bài toán liệt kê được giải quyết bằng cách liệt kê đệ quy. Thật không may, không có cách tiếp cận chung, bởi vì thông thường, các phương pháp lặp lại phụ thuộc nhiều vào chính tác vụ đó.
Tuy nhiên, người ta có thể nhận thấy một số điểm tương đồng giữa các phương pháp liệt kê các đối tượng tổ hợp khác nhau. Do đó, để có một ví dụ minh họa, hãy xem xét một mã tạo ra tất cả các tổ hợp từ n đến k.
int n, k;
// Một mảng hỗ trợ các tiền tố kết hợp.
//
// Tiền tố trong trường hợp này có nghĩa là chúng ta đã chọn một số đối tượng trong tổ hợp.
//
// Sau đó, chúng sẽ được hoàn thành theo đúng tổ hợp,
// hoặc đệ quy sẽ cắt nhánh khi nhận ra rằng tiền tố đó không thể hoàn thành chính xác
véc tơ mảng;
// chính hàm lặp đệ quy
//
// pos - số lượng đối tượng kết hợp mà chúng ta sẽ xác định tại thời điểm hiện tại (từ 0 đến k - 1)
//
// prev - giá trị của đối tượng được lấy ở bước trước
//
// Trong các kết hợp, thứ tự của các đối tượng không quan trọng ([1, 2] và [2, 1] được coi là giống nhau và tương tự nhau),
// vì vậy chúng tôi chỉ muốn tạo các bộ có giá trị đối tượng theo thứ tự tăng dần.
//
// Điều này là cần thiết để các tùy chọn tương tự như [1, 2] và [2, 1] chỉ được lặp lại một lần
// (trong trường hợp của chúng tôi, chúng tôi sẽ chỉ xem xét [1, 2] chứ không phải [2, 1] vì nó không phải là một tập hợp có thứ tự).
//
// Đó là lý do tại sao chúng ta giữ biến prev để giảm số lần lặp
void rec(int pos, int prev) {
// nếu số phần tử được chọn bằng k thì ta đã chọn hết phần tử
// bởi vì số của chúng là từ 0 đến k - 1
nếu (pos == k) {
// nếu điều kiện được đáp ứng, thì tổ hợp chính xác hiện có trong mảng arr
// và chúng ta có thể xử lý nó bằng cách nào đó (trong trường hợp này, chỉ cần in nó ra bàn điều khiển)
for (int i = 0; i < k; i++)
cout << mảng[i] + 1 << ' ';
cout << '\n';
trở lại; // cắt nhánh đệ quy, vì đã có một sự kết hợp và không cần phải tiếp tục thêm
}
// ở đây chúng tôi kiểm tra xem chúng tôi có thể kết hợp đúng từ các phần tử còn lại không
// nếu không đủ phần tử còn lại thì ta cắt bỏ nhánh đệ quy này
nếu (k - vị trí > n - trước - 1)
trở lại;
// lặp lại đối tượng mà chúng ta đặt vào vị trí với chỉ số pos
// nhưng bởi vì chúng tôi muốn một tập hợp có thứ tự, thì giá trị tối thiểu có thể là prev + 1
for (int i = prev + 1; i < n; i++) {
mảng.push_back(i); // Thêm một phần tử vào mảng toàn cục. Bây giờ chúng tôi dường như đã chọn anh ấy
rec(pos + 1, i); // chạy đệ quy để thiết lập các mục sau
arr.pop_back(); // sau khi quay lại từ đệ quy, phần tử đang được chọn của chúng ta không còn phù hợp nữa,
// bởi vì bên trong đệ quy, chúng tôi đã xem xét tất cả các tùy chọn với tiền tố như vậy,
// vì vậy phần tử này cần được loại bỏ
}
}
int chính ()
{
cin>> n>> k;
// ban đầu chúng ta sẽ đặt phần tử ở vị trí thứ 0
// chúng tôi giả sử rằng phần tử -1 đã được chọn trước đó, do đó, bước lặp ban đầu bắt đầu từ một đối tượng null
rec(0, -1);
trả về 0;
}
Mã giống nhau, nhưng không có chú thích:
int n, k;
véc tơ mảng;
void rec(int pos, int prev) {
nếu (pos == k) {
for (int i = 0; i < k; i++)
cout << mảng[i] + 1 << ' ';
cout << '\n';
trở lại;
}
nếu (k - vị trí > n - trước - 1)
trở lại;
for (int i = prev + 1; i < n; i++) {
mảng.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
int main() {
cin>> n>> k;
rec(0, -1);
trả về 0;
}
Trong các phép lặp đệ quy, luôn luôn phải đặc biệt chú ý đến việc cắt đệ quy. Trong thực tế, họ có thể tăng tốc chương trình rất nhiều.
|