Link tải luận văn miễn phí cho ae Kết nối

PHƯƠNG PHÁP HÀM SINH
TÁP DỤNG THUẬT TOÁN PHƯƠNG PHÁP SINH ĐỂ GIẢI QUYẾT CÁC BÀI TOÁN LIỆT KÊ TỔ HỢP
I. Giới thiệu về phương pháp sinh
Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau thoả mãn:
1. Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đã xác định
2. Xây dựng được thuật toán từ cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó.
Phương pháp sinh có thể mô tả như sau:
<Xây dựng cấu hình đầu tiên>;
Repeat
<Đưa ra cấu hình đang có>;
<Từ cấu hình đang có sinh ra cấu hình kế tiếp nếu còn>;
Until <hết cấu hình>;
II. Một số bài toán cơ bản được cài đặt bằng phương pháp sinh
1. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ
Ta sẽ lập chương trình liệt kê các tập con k phần tử của tập {1, 2, ..., n} theo thứ tự từ điển
Ví dụ: với n = 5, k = 3, ta phải liệt kê đủ 10 tập con:
1. {1, 2, 3}
2. {1, 2, 4}
3. {1, 2, 5}
4. {1, 3, 4}
5. {1, 3, 5}
6. {1, 4, 5}
7. {2, 3, 4}
8. {2, 3, 5}
9. {2, 4, 5}
10. {3, 4, 5}
rong bài viết này mình muốn giới thiệu với các bạn một phương pháp đếm các cấu hình ổ hợp rất đắc lực , đó là phương pháp hàm sinh. Vì kiến thức có hạn và chủ yếu là do mình cóp nhặt được từ một số tài liệu nên có gì sai sót mong quý bạn thông cảm hen.
Phương pháp hàm sinh là một phương pháp hiện đại, sử dụng các kiến thức về chuỗi, chuỗi hàm (đặc biệt là công thức Taylor). Trước hết ta có định nghĩa sau
Định nghĩa 1: Cho dãy số .
Chuỗi hình thức gọi là hàm sinh của dãy
Ta gọi đó là chuỗi hình thức vì ta không xét đến tính hội tụ hay tính giá trị của chuỗi mà ta chỉ xem đó như là một cách viết thuận tiện vậy. Ta đưa vào một số phép toán trên các chuỗi để xác định các hệ số cho các lũy thừa biến .


fZYzcD8XZNf9OnI

---