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

Giảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

Giải Chuyên đề Tin học 11 Bài 2: Kĩ thuật quay lui - Cánh diều

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.

Quảng cáo

Lời giải:

Dãy bit độ dài n có dạng X = (x₀, x₁...x_n-1), trong đó x_i 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 x_i 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 x_i+1... đến thành phần x_n-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 x_i mà x_i đã lần lượt nhận cả hai giá trị 0 và 1, khi đó thành phân x_i sẽ bị loại khỏi X và lùi về để xét khả năng tiếp theo cho thành phần x_i-1

Quảng cáo

Lời giải Chuyên đề Tin 11 Bài 2: Kĩ thuật quay lui hay, ngắn gọn khác:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Cánh diều hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 11 hay khác:

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Săn SALE shopee Tết:

ĐỀ THI, GIÁO ÁN, SÁCH LUYỆN THI DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 11

Bộ giáo án, bài giảng powerpoint, đề thi, sách dành cho giáo viên và gia sư dành cho phụ huynh tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official

Tổng đài hỗ trợ đăng ký : 084 283 45 85

Giáo án, bài giảng powerpoint Văn, Toán, Lí, Hóa....

4.5 (243)

799,000đs

199,000 VNĐ

Đề thi, chuyên đề Cánh diều, Kết nối tri thức, Chân trời sáng tạo...

4.5 (243)

799,000đ

99,000 VNĐ

Gia sư 1:1 bởi các thầy cô VietJack

4.5 (243)

299,000đ

199,000 VNĐ

xem tất cả

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.