Chương trình Python đếm số chuỗi nhị phân không có 1 liên tiếp

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho số nguyên dương N, cần đếm tất cả chuỗi nhị phân khác nhau độ dài N sao cho không có hai số 1 liên tiếp.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# đếm số chuỗi
def countStrings(n):
    a = [0 for i in range(n)]
    b = [0 for i in range(n)]
    a[0] = b[0] = 1
    for i in range(1, n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
    return a[n-1] + b[n-1]

# main
n = 5
print("Số chuỗi:", countStrings(n))

Kết quả

Số chuỗi: 13

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python đếm số chuỗi nhị phân không có 1 liên tiếp.