Trang bìa
Trang bìa
Ảnh
CHUYÊN ĐỀ 3: THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT DUYỆT
BÀI 3: THỰC HÀNH KĨ THUẬT QUAY LUI
Mở đầu
Kiến thức học được
Hình vẽ
Học xong bài này em sẽ: - Tìm hiểu được chương trình liệt kê các hoán vị của n phần tử bằng kĩ thuật đệ quy. - Tìm hiểu được một số bài toán sử dụng kĩ thuật quay lui - Nhận ra được mối liên quan giữa thiết kế thuật toán theo kĩ thuật quay lui và kĩ thuật đệ quy
Bài toán 1
Bài toán Trả tiền
BÀI TOÁN 1. TRẢ TIỀN Khi mua đồ giúp mẹ, Hồng phải trả tổng số tiền là s (nghìn đồng), hiện tại Hồng có n tờ tiền được đánh số từ 0 đến n-1 với mệnh giá tương ứng latex(t_0, t_1,..., t_(n-1)) ( nghìn đồng). Hồng muốn liệt kê tất cả các cách chọn tờ tiền mà tổng đúng bằng s (nghìn đồng)
Ví dụ
Với s - 130 ( nghìn đồng) và có 5 tờ tiền với mệnh giá tương ứng là 10, 20, 50, 50, 100 ( nghìn đồng) thì Hồng có cách trả sau đây. Gồm 3 tờ: tờ số 0, tờ số 1, tờ số 4 có mệnh giá tương ứng là 10, 20, 100 ( nghìn đồng), tổng là 10 + 20 + 100 = 130 ( nghìn đồng)
Ảnh
Bài toán 2
Bài toán
Một hoán vị của 0, 1, ...,n - 1 là m dãy latex(x_0, x_1, ...., x_(n-1)) mà latex(c le x_i le n-1) và latex(x_i) đôi một khác nhau. Ví dụ, n = 3 có 6 hoán vị của 0,1,2 là các hoán vị: (0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), (2,1,0). Trong nhiều bài toán, chúng ta cần liệt kê hết tất cả các hoán vị của n phần tử. Em hãy tìm hiểu chương trình liệt kê các hoán vị của n phần tử bằng kĩ thuật đệ quy và chạy thử nghiệm của chương trình
Bài toán 2. Liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy
Bài toán
Bài toán 2. Liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy
Ảnh
Yêu cầu
a, Cho biết số lượng hoán vị của 3, 4 hoặc 5 phần tử là bao nhiêu b, Em hãy so sánh chương trình liệt kê các dãy bit độ dài n với chương trình liệt kê các hoán vị của n phần tử c, cho biết ý nghĩa của lệnh x.append(v) và x.pop() trong chương trình
Bài toán 2. Liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy
Yêu cầu
d, Hình 2 mô tả quá trình gọi đệ quy để xây dựng các hoán vị 3 phần tử. Dãy ở hình chữ nhật là dãy hoán vị trong quá trình xây dưng, số trong hình ô van là thứ tự xây dựng. Em hãy cho biết các dãy trong hình chữ nhật chứa dấu ?
Bài toán 2. Liệt kê hoán vị của n phần tử bằng kĩ thuật đệ quy
Ảnh
Bài toán 3
Yêu cầu
Em hãy lập trình, nhập vào một từ gồm các chữ cái khác nhau, liệt kê ra tất cả các hoán vị của các chữ cái đó. Chạy thử nghiệm với các bộ dữ liệu ở Bảng dưới đây
Ảnh
Kết thúc
Tạm biệt
Ảnh