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 4. THỰC HÀNH TỔNG HỢP KĨ THUẬT DUYỆT
Bài toán 1
Bài toán
Có n quả cam, n quả táo và n quả lê (latex(n le 1000)). Em hãy lập chương trình nhập vào số nguyên dương n, sau đó đưa ra các cách lấy n quả, hai cách được gọi là khác nhau nếu tồn tại một loại quả trong cách này có số lượng khác với trong cách kia. Chạy thử nghiệm với các dữ liệu trong Bảng dưới đây.
Ảnh
Gợi ý
Hình vẽ
Gọi x là số quả cam, y là số quả táo, z là số quả lê được lấy ra. Khi đó, số cách chọn là số nghiệm nguyên không âm của phương trình: x + y + z = n
Bài toán 2
Bài toán
M nhóm học sinh gồm n (latex(n le 10)) bạn, cần chọn k (latex( k le n)), bạn tham gia một trò chơi. Em hãy lập chương trình nhập vào hai số nguyên dương n, k và danh sách gồn n tên học sinh, sau đó liệt kê tất cả các cách chọn k học sinh trong n học sinh. Chạy thử nghiệm với bộ dữ liệu ở Bảng dưới đây
Ảnh
Gợi ý
Hình vẽ
Sử dụng kĩ thuật quay lui để xây dựng tất cả các dãy bit độ dài n, với mỗi dãy bit tương ứng với một cách chọn, kiểm tra số lượng bit 1 bằng đúng k hay không?
Luyện tập
Bài tập
Một lớp học nhảy có n (latex(n le 10) bạn nam và n bạn nữ. Bạn nam thứ i (latex(0 le i le n-1)) có chiều cao là latex(b_i) (cm), bạn nữa thứ j (latex(0 le j le n-1)) có chiều cao là latex(g_j) (cm). Trong buổi học, thầy giáo muốn ghép các bạn nam với các bạn nữ tạo thành n đội nhảy để trình diễn, mỗi đôi gồm một bạn nam và một bạn nữ mà chênh lệch chiều cao của hai bạn không vượt quá d(cm). Em hãy lập chương trình đếm số cách ghép thỏa mãn, chương trình nhập vào số nguyên d cùng với hai dãy số latex(b_0,b_1,...,b_(n-1)) và latex(g_0,g_1,...,g_(n-1)) sau đó đưa ra số cách ghép thỏa mãn. Chạy thử nghiệm với các bộ dữ liệu ở Bảng 3
Gợi ý
Gợi ý: Sử dụng kĩ thuật quay lui để xây dựng tất cả các hoán vị của n phần tử, với mỗi hoán vị tương ứng với một cách ghép, kiểm tra và đếm
Ảnh
Kết thúc
Tạm biệt
Ảnh