Giải các bài toán liệt kê bằng phương pháp sinh (TIN HỌC)
Phương pháp sinh thường dùng để giải một số bài toán liệt kê trong tin học. Ý tưởng chính của phương pháp sinh là từ cấu hình đầu tiên ta sinh ra các cấu hình tiếp theo theo một cách nào đó. Tuy nhiên không phải bài nào cũng có thể làm theo phương pháp sinh. Yêu cầu của bài toán để có thể làm theo phương pháp sinh là:
- Thứ nhất phải xác định được cấu hình đầu và cấu hình cuối
- Thứ hai phải xác định được cấu hình tiếp theo bằng 1 công thức nhất định
Ví dụ : Liệt kê các dãy nhị phân độ dài n.
với n =10, ta có cấu hình ban đầu là:
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Và cấu hình cuối sẽ là
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Giả sử ta đang có cấu hình hiện tại là
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
Thì cấu hình kế tiếp sẽ là:
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
Cấu hình này được sinh ra từ cấu hình trước đó bằng cách cộng 1 (từ phải sang trái)
Khi đã ở cấu hình cuối thì ta không có cấu hình kế tiếp.
Thuật toán để giải bài này như sau:
Bước 1:
Khởi tạo mảng A gồm n số 0 (tương ứng với chuỗi bit đầu tiên)
Bước 2:
Lặp
· In cấu hình hiện tại
· Nếu cấu hình hiện tại là cấu hình cấu hình cuối thì break;
Ngược lại cong(A,1)
Về thuật toán cộng mảng A cho 1, ta thực hiện như sau:
B1:
j=n
B2:
while(j>=1)
+ nếu gặp a[j] =0 thì ta thay bằng a[j]=1 và thay các giá trị từ a[j+1] đến a[n] bằng 0 và thoát
+ nếu gặp a[j] =1 thì không làm gì
Từ thuật toán cộng này ta thấy nếu không còn cấu hình thì j sẽ giảm đến 0 và đây là điều kiện để thoát cho thuật toán sinh ở trên.
Chi tiết chương trình như sau:
Các bạn có thể so sánh thời gian thực hiện nếu thực hiện bằng phương pháp sinh và bằng phương pháp quay lui để đánh giá hiệu quả của thuật toán.
Bài tập vận dụng:
Liệt kê các dãy nhị phân độ dài n trong đó không có hai bit 1 kề nhau.
Các gợi ý giải cho bài này sẽ bàn đến trong bài tới.
Huỳnh Bá Diệu (dieuhb@gmail.com)
» Tin mới nhất:
» Các tin khác: