Bài 8.5. Bài tập Python: sinh dãy nhị phân

Chào mừng các bạn trở lại với series bài tập Python! Hôm nay, chúng ta sẽ cùng nhau giải quyết một bài toán kinh điển trong lập trình: sinh tất cả các dãy nhị phân có độ dài cho trước. Đây là một bài toán thú vị, giúp chúng ta làm quen với các kỹ thuật như vòng lặp, chuyển đổi cơ số, và đặc biệt là đệ quy (hay còn gọi là backtracking).

Một dãy nhị phân độ dài n là một chuỗi gồm n ký tự, trong đó mỗi ký tự chỉ có thể là '0' hoặc '1'. Ví dụ, với n=3, các dãy nhị phân có thể là: "000", "001", "010", "011", "100", "101", "110", "111".

Có bao nhiêu dãy nhị phân độ dài n? Đơn giản thôi, mỗi vị trí có 2 lựa chọn ('0' hoặc '1'), và có n vị trí độc lập. Do đó, tổng số dãy là 2^n. Với n=3, số dãy là 2^3 = 8, đúng như ví dụ trên.

Trong bài viết này, chúng ta sẽ khám phá hai phương pháp chính để sinh các dãy nhị phân này trong Python.

Phương pháp 1: Sử dụng Vòng lặp và Chuyển đổi Nhị phân

Ý tưởng của phương pháp này khá đơn giản:

Chúng ta biết có tổng cộng 2^n dãy nhị phân có độ dài n.
Các dãy nhị phân này có thể được xem là biểu diễn nhị phân của các số nguyên từ 0 đến 2^n - 1.
Ví dụ với n=3:
- 0 (hệ 10) -> 000 (hệ 2)
- 1 (hệ 10) -> 001 (hệ 2)
- 2 (hệ 10) -> 010 (hệ 2)
- ...
- 7 (hệ 10) -> 111 (hệ 2)
Như vậy, chúng ta chỉ cần lặp qua các số nguyên từ 0 đến 2^n - 1, chuyển mỗi số sang dạng nhị phân và đảm bảo rằng chuỗi nhị phân đó có đủ n ký tự (bằng cách thêm các số 0 đằng trước nếu cần).

Hãy xem đoạn mã Python minh họa cho phương pháp này:

def generate_binary_iterative(n):
    """
    Sinh tất cả các dãy nhị phân có độ dài n bằng vòng lặp
    và chuyển đổi từ số nguyên.
    """
    # Tính tổng số dãy cần sinh (từ 0 đến 2^n - 1)
    num_sequences = 2**n
    binary_sequences = [] # Danh sách để lưu trữ kết quả

    print(f"--- Sinh dãy nhị phân độ dài {n} bằng phương pháp Lặp ---")
    # Lặp qua các số nguyên từ 0 đến 2^n - 1
    for i in range(num_sequences):
        # Bước 1: Chuyển số nguyên i sang dạng nhị phân.
        # Hàm bin(i) trong Python trả về một chuỗi có tiền tố '0b'.
        # Ví dụ: bin(3) trả về '0b11'.
        binary_str = bin(i)

        # Bước 2: Loại bỏ tiền tố '0b'
        # Chúng ta chỉ lấy phần chuỗi nhị phân sau '0b'.
        clean_binary_str = binary_str[2:]

        # Bước 3: Đảm bảo chuỗi nhị phân có đủ độ dài n
        # Nếu chuỗi ngắn hơn n, thêm các số '0' vào phía trước
        # cho đến khi đủ độ dài.
        # Phương thức zfill(n) thực hiện chính xác điều này.
        padded_binary_str = clean_binary_str.zfill(n)

        # Bước 4: Thêm dãy nhị phân đã xử lý vào danh sách kết quả
        binary_sequences.append(padded_binary_str)

        # In ra từng dãy khi được sinh ra (hoặc có thể chỉ in ra sau cùng)
        print(padded_binary_str)

    # Có thể trả về danh sách các dãy
    # return binary_sequences

# --- Ví dụ sử dụng Phương pháp 1 ---
print("Ví dụ 1:")
generate_binary_iterative(3)

print("\nVí dụ 2:")
generate_binary_iterative(4)

print("\nVí dụ 3:")
generate_binary_iterative(1)

Giải thích code:

generate_binary_iterative(n): Hàm nhận vào độ dài n cần sinh dãy.
num_sequences = 2**n: Tính toán tổng số lượng dãy cần sinh, bằng 2 mũ n.
for i in range(num_sequences):: Vòng lặp này sẽ chạy từ i = 0 đến num_sequences - 1. Mỗi giá trị của i tương ứng với một dãy nhị phân.
binary_str = bin(i): Hàm bin() tích hợp sẵn của Python chuyển đổi số nguyên i thành chuỗi biểu diễn nhị phân. Kết quả bắt đầu với tiền tố "0b" để chỉ rõ đây là dạng nhị phân (ví dụ: bin(5) là "0b101").
clean_binary_str = binary_str[2:]: Sử dụng slicing để cắt bỏ hai ký tự đầu tiên "0b", chỉ giữ lại phần chuỗi nhị phân thực sự.
padded_binary_str = clean_binary_str.zfill(n): Đây là bước quan trọng. Phương thức zfill(n) của chuỗi sẽ thêm các ký tự "0" vào phía bên trái của chuỗi clean_binary_str cho đến khi tổng độ dài của chuỗi đạt đến n. Ví dụ, nếu n=3 và clean_binary_str là "10" (tương ứng với số 2), zfill(3) sẽ biến nó thành "010".
binary_sequences.append(padded_binary_str): Thêm dãy nhị phân hoàn chỉnh (đã được đệm) vào danh sách kết quả.
print(padded_binary_str): In ra dãy vừa sinh được.

Phương pháp lặp này rất trực quan và hiệu quả cho bài toán sinh dãy nhị phân, đặc biệt là khi độ dài n không quá lớn.

Phương pháp 2: Sử dụng Đệ quy (Backtracking)

Phương pháp đệ quy (hay backtracking) tiếp cận bài toán theo một cách khác: xây dựng dãy nhị phân từng ký tự một.

Ý tưởng là:

Ta bắt đầu với một dãy rỗng.
Ở mỗi vị trí từ 0 đến n-1, ta có hai lựa chọn: đặt '0' hoặc đặt '1'.
Với mỗi lựa chọn, ta lại tiếp tục xây dựng phần còn lại của dãy bằng cách gọi đệ quy.
Khi dãy xây dựng được đạt đến độ dài n, đó là một dãy nhị phân hoàn chỉnh, và ta lưu lại kết quả này.
Sau khi xử lý một lựa chọn (ví dụ đặt '0'), ta cần "quay lui" (backtrack) để loại bỏ ký tự vừa thêm vào và thử lựa chọn khác (đặt '1').

Đây là một kỹ thuật mạnh mẽ thường dùng trong các bài toán tìm kiếm tất cả các cấu hình có thể (như xếp hậu, giải sudoku, hoán vị...).

Hãy cùng xem code đệ quy:

def generate_binary_recursive(n):
    """
    Sinh tất cả các dãy nhị phân có độ dài n bằng đệ quy (backtracking).
    """
    binary_sequences = [] # Danh sách để lưu trữ kết quả

    # Hàm đệ quy "backtrack" để xây dựng dãy
    # current_sequence là danh sách các ký tự hiện tại của dãy đang được xây dựng
    def backtrack(current_sequence):
        # Điều kiện dừng (base case): Nếu dãy đã đủ độ dài n
        if len(current_sequence) == n:
            # Nếu đủ độ dài, chuyển danh sách ký tự thành chuỗi và thêm vào kết quả
            binary_sequences.append("".join(current_sequence))
            # print("".join(current_sequence)) # Có thể in ra ngay tại đây
            return # Kết thúc nhánh đệ quy hiện tại, quay lui

        # Lựa chọn 1: Thêm '0' vào cuối dãy hiện tại
        current_sequence.append('0')
        # Gọi đệ quy để tiếp tục xây dựng phần còn lại của dãy
        backtrack(current_sequence)
        # Quay lui (backtrack): Xóa '0' vừa thêm vào để thử lựa chọn khác
        current_sequence.pop()

        # Lựa chọn 2: Thêm '1' vào cuối dãy hiện tại
        current_sequence.append('1')
        # Gọi đệ quy để tiếp tục xây dựng phần còn lại của dãy
        backtrack(current_sequence)
        # Quay lui (backtrack): Xóa '1' vừa thêm vào
        current_sequence.pop()

    print(f"--- Sinh dãy nhị phân độ dài {n} bằng phương pháp Đệ quy ---")
    # Bắt đầu quá trình backtrack với một danh sách rỗng
    backtrack([])

    # Sau khi hàm backtrack hoàn thành, binary_sequences sẽ chứa tất cả các dãy
    # In ra tất cả các dãy đã thu thập được
    for seq in binary_sequences:
         print(seq)

    # Có thể trả về danh sách các dãy
    # return binary_sequences


# --- Ví dụ sử dụng Phương pháp 2 ---
print("\nVí dụ 4:")
generate_binary_recursive(3)

print("\nVí dụ 5:")
generate_binary_recursive(4)

print("\nVí dụ 6:")
generate_binary_recursive(1)

Giải thích code:

generate_binary_recursive(n): Hàm chính, khởi tạo danh sách binary_sequences để lưu kết quả và định nghĩa hàm đệ quy backtrack.
backtrack(current_sequence): Đây là trái tim của giải thuật đệ quy. Nó nhận vào một danh sách current_sequence chứa các ký tự đã được chọn cho các vị trí đầu tiên của dãy.
if len(current_sequence) == n:: Đây là điều kiện dừng (base case) của đệ quy. Nếu độ dài của current_sequence bằng với độ dài n mong muốn, điều đó có nghĩa là ta đã xây dựng xong một dãy nhị phân hoàn chỉnh. Ta nối các ký tự trong danh sách lại thành một chuỗi ("".join(current_sequence)) và thêm vào danh sách kết quả binary_sequences. Lệnh return kết thúc lời gọi đệ quy hiện tại, quay trở lại điểm gọi trước đó.
current_sequence.append('0'): Nếu dãy chưa đủ độ dài, ta thử lựa chọn đầu tiên: thêm ký tự '0' vào cuối danh sách current_sequence.
backtrack(current_sequence): Sau khi thêm '0', ta gọi đệ quy để tiếp tục xây dựng phần còn lại của dãy (từ vị trí tiếp theo) dựa trên dãy hiện tại.
current_sequence.pop(): Đây là bước quay lui (backtrack). Sau khi lời gọi đệ quy backtrack(current_sequence) (với '0' đã được thêm vào) kết thúc (tức là đã duyệt xong tất cả các khả năng bắt đầu bằng chuỗi đó), ta xóa ký tự '0' vừa thêm vào. Điều này đưa current_sequence về trạng thái trước khi ta thử lựa chọn '0', sẵn sàng để thử lựa chọn khác.
Các bước tương tự (append, backtrack, pop) được thực hiện cho lựa chọn '1'.
backtrack([]): Lời gọi đầu tiên để bắt đầu quá trình đệ quy với một dãy rỗng.
Vòng lặp for seq in binary_sequences: cuối cùng dùng để in ra tất cả các dãy đã được thu thập trong quá trình đệ quy.

Phương pháp đệ quy này có vẻ phức tạp hơn một chút so với phương pháp lặp đối với bài toán cụ thể này, nhưng kỹ thuật backtracking mà nó sử dụng là cực kỳ quan trọng và áp dụng được cho rất nhiều bài toán tổ hợp phức tạp khác. Việc hiểu rõ luồng đi của đệ quy và thao tác append/pop (thêm và xóa để quay lui) là chìa khóa.

Cả hai phương pháp đều cho ra kết quả tương tự nhau, chỉ khác về cách triển khai. Phương pháp lặp có thể dễ hiểu hơn cho người mới bắt đầu, trong khi phương pháp đệ quy giới thiệu một kỹ thuật giải quyết vấn đề mạnh mẽ hơn cho các bài toán phức tạp hơn.

Chúc các bạn thực hành vui vẻ với bài tập này! Hãy thử thay đổi giá trị của n trong các ví dụ để thấy kết quả nhé.

Comments

There are no comments at the moment.