Với giải Hoạt động 2 trang 56 Chuyên đề Tin học 11 Cánh diều chi tiết trong Bài 2: Kĩ thuật quay lui giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:
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
Hoạt động 2 trang 56 Chuyên đề Tin học 11: 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.
Lời giải:
Dãy bit độ dài n có dạng X = (x0, x1...xn-1), trong đó xi 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 X. 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 xn-1).
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 khi đang xây dựng thành phần xi mà xi đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phân xi 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
Xem thêm các bài giải Chuyên đề Tin học 11 Cánh diều hay, chi tiết khác:
Hoạt động 1 trang 55 Chuyên đề Tin học 11: Cho 5 đồ dùng với giá và mức độ yêu thích tương ứng...
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
2021 © All Rights Reserved.
