使用Python中的確定性有限自動機 (DFA) 檢查二進位制字串是否為 3 的倍數

假設我們有一個數組 n，它表示任何數字的二進位制表示。我們必須使用確定性有限自動機 (DFA) 來檢查其二進位制表示是否可以被三整除。

因此，如果輸入類似於 n = [1, 1, 0, 0]（12 的二進位制數），則輸出將為 True。

為了解決這個問題，我們可以構建如下所示的 DFA：

方法很簡單：如果一個數字可以被 3 整除，則餘數為 0；否則，餘數為 1 或 2。這三個餘數對應三個狀態。初始狀態也是最終狀態，因為當餘數為 0 時，表示該數字可以被整除。

為了解決這個問題，我們將遵循以下步驟：

• dfa_state := 0
• 對於 i 從 0 到 nums 的大小減 1，執行以下操作：
  • digit := nums[i]
  • 如果 dfa_state 為 0，則：
    • 如果 digit 等於 1，則：
      • dfa_state := 1
  • 否則，如果 dfa_state 為 1，則：
    • 如果 digit 等於 0，則：
      • dfa_state := 2
    • 否則：
      • dfa_state := 0
  • 否則，如果 dfa_state 為 2，則：
    • 如果 digit 等於 0，則：
      • dfa_state := 1
• 如果 dfa_state 為 0，則：
  • 返回 True
• 返回 False

讓我們來看下面的實現，以便更好地理解：

示例

 線上演示

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

輸入

[1, 1, 0, 0]

輸出

True

Arnab Chakraborty

更新於：2020-12-30

瀏覽量 1K+

開啟你的職業生涯

透過完成課程獲得認證

開始