Phương pháp sinh được áp dụng để giải các bài toán liệt kê tổ hợp thoả hai điều kiện:
- Có thể xác định thứ tự của các cấu hình.
- Có thuật toán từ một cấu hình chưa phải là cấu hình cuối và sinh ra được cấu hình kế tiếp đó.
Giả sử bạn có tập O = {1,2,3} và đề bài yêu cầu tìm các chỉnh hợp không lặp chập 3, bạn sẽ liệt kê được:
- {1,2,3} – Đây là một cấu hình
- {1,3,2} – Đây là một cấu hình
- {2,1,3} – Đây là một cấu hình
- {2,3,1} – Đây là một cấu hình
- {3,1,2} – Đây là một cấu hình
- {3,2,1} – Đây là một cấu hình
Vậy theo yêu cầu bài toán, ta có được 6 cấu hình.
Phương pháp sinh
Trước khi bước vào giải một bài toán bằng phương pháp sinh, bạn cần xác định cấu hình đầu tiên, cấu hình cuối cùng và thuật toán để sinh ra cấu hình tiếp theo từ một cấu hình đã có.
Bạn có thể hiểu từ sơ đồ sau:
Bài toán liệt kê dãy nhị phân có độ dài N
Phân tích:
Input: int N
Output: Liệt kê các cấu hình cần tìm
Cấu hình đầu tiên: 000……0
Cấu hình cuối cùng: 111……1
Ý tưởng: Tìm vị trí số 0 đầu tiên từ phải sang trái, cho số 0 đó thành số 1 và tất cả các số 1 phía sau sẽ thành số 0.
Tham khảo:
C++:
#include<iostream>
#include<string>
using namespace std;
int main(){
//Nhap so n
cout << "Input N: ";
short n;
cin >> n;
//cau hinh dau tien
string first_number;
//cau hinh cuoi cung
string last_number;
// Tao Cau hinh dau tien va cau hinh cuoi cung
for(int i = 0; i < n; i++){
first_number += "0";
last_number += "1";
}
//Sinh cau hinh
while(first_number != last_number){
for( unsigned int i = first_number.length() - 1; i >= 0; i--){
if(first_number[i] == '1'){
first_number[i] = '0';
}
else{
first_number[i] = '1';
break;
}
}
//In ra cau hinh
cout << first_number << endl;
}
return 0;
}Tổng kết
Vậy để giải bài toán sinh một cấu hình bạn có thể lựa chọn phương pháp sinh để giải. Khi dùng phương pháp sinh bạn cần xác định được: cấu hình đầu tiên, cấu hình cuối cùng, thuật toán để sinh ra cấu hình. Và dấu hiệu để áp dụng là: xác định được thứ tự của các cấu hình.
Tham khảo:
Giải thuật và lập trình – Lê Minh Hoàng
