Câu hỏi:
03/07/2023 287
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.
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.
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 !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
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
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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.
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 »
03/07/2023
243
Câu 2:
Hồng có n tệp dữ liệu được đánh số từ 0 đến n - 1 và có kích thước tương ứng là S0, S1..... Sn-1 (Mb). Hồng muốn tìm cách lưu trữ được nhiều tệp dữ liệu nhất bằng hai đĩa ô cứng, mỗi ô có dung lượng D(Mb). Em hãy lập trình giúp Hồng giải quyết bài toán trên, chương trình sẽ nhập vào số nguyên 2 và dãy số S0, S1, ...Sn-1, sau đó đưa ra phương án lưu trữ là một dãy số X0, X1, ...Xn-1. trong đó Xi(0 < i< n-1) nhận một trong ba giá trị 0 (không được lưu trữ). 1 (lưu trên ô cứng thứ nhất) hoặc 2 (lưu trên ô cứng thứ hai). Xem Hình 5 mô tả quá trình xây dựng các dãy X. Chạy thử nghiệm với các bộ dữ liệu trong Bảng 3.
Xem đáp án »
03/07/2023
196
Câu 3:
Em hãy tìm hiểu, soạn thảo chương trình giải bài toán mua đồ đồ tổng quát trong Hình 4 bằng kĩ thuật quay lui và chạy thử nghiệm với các bộ dữ liệu trong Bảng 2.
Em hãy tìm hiểu, soạn thảo chương trình giải bài toán mua đồ đồ tổng quát trong Hình 4 bằng kĩ thuật quay lui và chạy thử nghiệm với các bộ dữ liệu trong Bảng 2.
Xem đáp án »
03/07/2023
163
Câu 4:
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.
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 đáp án »
03/07/2023
159
Câu 5:
Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1. Nếu T= 20 (nghìn đồng) thì Hồng cần chọn mua những đồ dùng nào để tổng mức độ yêu thích là lớn nhất
Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng như trong Bảng 1. Nếu T= 20 (nghìn đồng) thì Hồng cần chọn mua những đồ dùng nào để tổng mức độ yêu thích là lớn nhất
Xem đáp án »
03/07/2023
139
về câu hỏi!