数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法学研究使用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
- 如果 digit 等于 1，则：
- 否则，如果 dfa_state 为 1，则：
- 如果 digit 等于 0，则：
- dfa_state := 2
- 否则：
- dfa_state := 0
- 如果 digit 等于 0，则：
- 否则，如果 dfa_state 为 2，则：
- 如果 digit 等于 0，则：
- dfa_state := 1
- 如果 digit 等于 0，则：
- 如果 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
更新于：2020-12-30
浏览量 1K+
广告