Link tải luận văn miễn phí cho ae Kết nối
Mục tiêu
Giải thích được sinh dữ liệu là gì.
Biết sử dụng một số giải thuật sinh.
Biết sử dụng giải thuật quay lui để giải một số bài toán.
Nội dung
Ôn tập
Bài toán tổ hợp
Phương pháp sinh
Thuật toán quay lui
Ôn tập
Hàm đệ quy là hàm mà trong thân hàm lại gọi chính nó.
Hàm đệ quy kém hiệu qủa vì: tốn bộ nhớ va gọi hàm qúa nhiều lần. Tuy nhiên viết hàm đệ quy rất ngắn gọn.Tuy nhiên nhiều giải thuật vẫn phải dùng kỹ thuật đệ quy vì việc khử đệ quy không dễ dàng.
Vòng lặp và stack là những kỹ thuật giúp khử giải thuật đệ quy.
8.1- Bài toán tổ hợp
Có n biến x1, x2, x3, ..., xn
Mỗi biến xi có thể mang trị thuộc về 1 tập hợp Pi  Miền của bài toán là tập tích
P1 x P2 x P3 x ... x Pn
Phép gán trị (assignment): Là một bộ trị
a1, a2, a3, ..., an
Trong đó a1  ai ∈ Pi
Một lời giải của bài toán là 1 phép gán trị.
Một phép gán trị được gọi là một cấu hình.
Bài toán tổ hợp
Ví dụ: Có 3 nhân viên bảo vệ làm 3 ca sáng, chiều tối. Trong 1 ca chỉ có 1 bảo vệ. Hỏi các cách bố trí các bảo vệ?
Mã hóa bài toán:
{x, y, z} là tập biến có thứ tự mô tả cho 3 ca :sáng, chiều, tối theo thứ tự.
Miền trị của 3 biến là
{ a,b,c } mô tả cho 3 bảo vệ.
Bài toán tổ hợp
Ví dụ: Tìm số chuỗi có độ dài 3 ký tự xyz với
x ∈ { a,b,c},
y ∈ { d,e},
z ∈ { m,n,t}
Nhận xét: 3 biến có 3 miền trị khác nhau


l2BFmGv7917vc34

---