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

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

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:

- 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.

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