Kiểm tra chuỗi nhị phân chia hết cho 3 bằng DFA trong Python

Cho mảng nums biểu diễn số nhị phân (bit cao đến thấp). Kiểm tra xem số đó có chia hết cho 3 hay không bằng cách dùng Đa thức tự động hữu hạn xác định (DFA).

DFA có 3 trạng thái tương ứng dư 0,1,2. Trạng thái 0 là trạng thái chấp nhận.

Ví dụ: [1,1,0,0] (12) → chia hết cho 3 → True.

Giải thuật

• Khởi tạo dfa_state = 0.
• Duyệt từng bit:
  • Tại trạng thái 0: nếu bit=1 → trạng thái 1.
  • Tại trạng thái 1: nếu bit=0 → trạng thái 2; nếu bit=1 → trạng thái 0.
  • Tại trạng thái 2: nếu bit=0 → trạng thái 1; nếu bit=1 → trạng thái 2 (giữ nguyên).
• Cuối cùng nếu dfa_state == 0 → True.

Mã ví dụ

def solve(nums):
    dfa_state = 0
    for i in range(len(nums)):
        digit = nums[i]
        if dfa_state == 0:
            if digit == 1:
                dfa_state = 1
        elif dfa_state == 1:
            if digit == 0:
                dfa_state = 2
            else:
                dfa_state = 0
        elif dfa_state == 2:
            if digit == 0:
                dfa_state = 1
        if dfa_state == 0:
            return True
    return False

n = [1, 1, 0, 0]
print(solve(n))

Đầu vào

[1, 1, 0, 0]

Đầu ra

True