Skip to content

Chuỗi nhị phân

Tóm lược nội dung

Bài này trình bày cách giải bài toán liệt kê chuỗi nhị phân bằng phương pháp quay lui.

Bài toán

Yêu cầu:

Viết chương trình liệt kê tất cả các chuỗi nhị phân có số lượng ký tự cho trước.

Đầu vào:

Số nguyên dương \(n\) biểu thị số ký tự của chuỗi nhị phân cần phát sinh.

Đầu ra:

Các chuỗi nhị phân có \(n\) ký tự.

Bộ kiểm thử:

Đầu vào Đầu ra
n = 3 000
001
010
011
100
101
110
111

Cách giải đề xuất

Ý tưởng chính

1. Đặt:

  • binary_option là mảng biểu thị cho một phương án chuỗi nhị phân. Từng vị trí trong binary_option sẽ được thử nạp số 0 hoặc số 1.
  • binary_strings là mảng kết quả gồm các chuỗi hoàn chỉnh sẽ được in ra.

Phương pháp quay lui được thực hiện như sau:

Bước 1: Thử

Thử nạp một trong hai số 0 hoặc 1 vào binary_option: binary_option.append(digit).

Bước 2: Tiến

Gọi đệ quy để tiếp tục nạp chữ số 0 hoặc 1 ở vị trí tiếp theo cho đến khi đủ n chữ số: len(binary_option) == n.

Bước 3: Quay lui

Gỡ bỏ số vừa nạp ở cuối ra khỏi binary_option: binary_option.pop().

Ví dụ:
Tại ví trị i của binary_option, nếu bước trước đó đã nạp 0 thì gõ bỏ 0 để chuẩn bị nạp 1.

Hình dưới đây minh hoạ phương pháp quay lui khi chọn 0 và 1 cho chuỗi nhị phân gồm 3 ký tự.

flowchart TD
    R[ø] --> 0[0] --> 00[0] --> 000[0]
    00 --> 001[1]

    0 --> 01[1] --> 010[0]
    01 --> 011[1]

    R[ø] --> 1[1] --> 10[0] --> 100[0]
    10 --> 101[1]

    1 --> 11[1] --> 110[0]
    11 --> 111[1]

2. Với số ký tự n = 3, số chuỗi nhị phân sẽ được tạo ra là: \(2^n = 2^3 = 8\).

Viết chương trình

1. Viết hàm generate_binary_string() dùng để phát sinh chuỗi nhị phân.

Hàm có một tham số là mảng binary_option biểu thị một phương án chuỗi nhị phân.

Hàm không có giá trị trả về.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# Hàm quay lui dùng để phát sinh chuỗi nhị phân
def generate_binary_string(binary_option):
    if len(binary_option) == n:
        # Nếu đã đủ số lượng thì ghép các phần tử của binary_option thành một chuỗi
        s = ''.join(map(str, binary_option))

        # Lưu chuỗi nhị phân hoàn chỉnh vào biến kết quả
        binary_strings.append(s)
        return

    # Duyệt các lựa chọn: 0 và 1
    for digit in [0, 1]:
        # Bước 1 - Thử: nạp số được chọn vào phương án
        binary_option.append(digit)

        # Bước 2 - Tiến: gọi đệ quy để nạp số ở vị trí tiếp theo
        generate_binary_string(binary_option)

        # Bước 3 - Quay lui: gỡ bỏ số vừa nạp ở cuối
        binary_option.pop()

2. Viết chương trình chính:

  • Cho người dùng nhập số lượng ký tự của chuỗi nhị phần cần phát sinh.
  • Khởi tạo mảng kết quả binary_strings là rỗng.
  • Khởi tạo phương án init_option là rỗng, dùng để truyền vào lời gọi hàm generate_binary_string().
  • Gọi hàm generate_binary_string() ra thực hiện.
  • Dùng vòng lặp để in ra các chuỗi nhị phân hoàn chỉnh có trong binary_strings.
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
if __name__ == '__main__':
    # Số lượng ký tự của chuỗi nhị phân
    n = int(input('Nhập số ký tự: '))

    # Khởi tạo mảng kết quả binary_strings
    binary_strings = []

    # Khởi tạo phương án rỗng
    init_option = []

    # Gọi hàm generate_binary_string()
    generate_binary_string(init_option)

    # In ra các chuỗi nhị phân trong mảng kết quả binary_strings
    for s in binary_strings:
        print(s)

Mã nguồn

Code đầy đủ được đặt tại:

Bao tôi ly cafe 🧋 nhé!