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ả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: