Trong những câu sau đây, câu nào đúng khi nói về kĩ thuật quay lui?

a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.

b) Khi cài đặt kĩ thuật quay lui, bắt buộc phải sử dụng kĩ thuật đệ quy.

c) Kĩ thuật quay lui là một kĩ thuật theo ý tưởng của kĩ thuật duyệt.

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 11 Cánh diều Bài 2. Phương pháp quay lui có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

Trong những câu sau đây, câu sau đúng khi nói về kĩ thuật quay lui:

a) Kĩ thuật quay lui không thể, liệt kê tất cả các trường hợp có thể xảy ra để tìm được nghiệm của bài toán.

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

Em hãy tìm hiểu chương trình liệt kê dãy bit độ dài n bằng kĩ thuật đệ quy trong Hình 1 và chạy thử nghiệm chương trình. Cho biết số lượng dãy bit nhị phân độ dài 3, 5, 10 tương ứng là bao nhiêu.

Xem đáp án

Lời giải

Dãy bit độ dài n có dạng X = (x0,x1...xn-1), trong đó x1 bằng 0 hoặc 1 (0 <i<n-1) có thể mô tả theo cách đệ quy như sau:

- Nếu n > 0 thì phần tử đầu tiên của dãy bằng 0 hoặc 1 và n - 1 phần tử sau là dãy bit độ dài n - 1

- Ngược lại, nếu n = 0 thì dãy bit độ dài n là dãy rỗng

Việc xây dựng các dãy nhị phân theo thuật toán đệ quy như sau:
1. Bắt đầu từ X rỗng, lệnh x = [] và gọi thủ tục đệ quy backtrack(0) để xây dựng bắt đầu phần tử 0.

2. Thành phần i (0<i<n-1) sẽ lần lượt nhận giá trị 0 và 1 bằng lệnh for v in range(2): Với mỗi giá trị của v, thành phần i được ghi nhận vào xi của X bằng lệnh x.append(v). lệnh này đây v vào cuối ÀV Sau đó tiếp tục gợi để quy để xây dựng các thành phần còn lại (từ thành phần Xi+1... đến thành phần x.)

3. Để xét được khả năng tiếp theo, hành động quay lui được thực hiện bằng cách loại bỏ nhị phân thành phần cuối cùng của X bằng lệnh x.pop(). Việc quay lui cũng được diễn ra khí đang xây dựng thành phần x mà x, đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phân x sẽ bị loại khỏi X và lùi về để xét khả năng tiếp theo cho thành phần Xi-1

Câu 2

Trong bài học trước, các em đã tìm hiểu bài toán Chọn mua đồ dùng học tập với các tình huống mua một đồ dùng hoặc hai đồ dùng. Nếu bài toán không cố định số lượng đổ dùng cần mua mà có thể mua một số đồ dùng với tổng giá không vượt quá T (đồng) và tổng mức độ yêu thích của các đồ dùng đó là lớn nhất, em hãy trình bày ý tưởng giải quyết bài toán.

Xem đáp án

Lời giải

Đề giải quyết bài toán mua đồ bằng kĩ thuật duyệt ta có thể xét toàn bộ dãy bit độ dài n, với mỗi dãy bịt tương ứng với một phương án mua, ta tiến hành tính tổng giá để kiểm tra ràng buộc không vượt quá T (đồng) và tính tổng mức độ yêu thích để chọn phương án tối ưu.

Câu 3