Java 程序使用 DFA 检查二进制字符串是否为 3 的倍数

二进制字符串是仅包含 0 和 1 的数字序列。确定给定的二进制 字符串代表的数字是否是 3 的倍数是计算理论和有限自动机中的经典问题。

解决此问题最有效的方法之一是使用确定性有限自动机 (DFA)。DFA 逐个字符地处理二进制字符串，并维护一个状态，该状态确定相应的十进制值是否可被 3 整除。

问题陈述

给定一个二进制字符串，任务是检查二进制数的十进制表示是否是 3 的倍数。DFA 可以用有限数量的状态来构建，以有效地确定可整除性条件，而无需将整个二进制数显式转换为十进制。

示例

示例 1

输入 "110"

输出： 是

解释

对于二进制字符串“110”，十进制等效值计算为 1 × 2^2 + 1 × 2^1 + 0 × 2^0 = 4 + 2 + 0 = 6。由于 6 可被 3 整除，DFA 达到状态 0，该状态代表 3 的倍数的数字。因此，输出为“是”。

示例 2

输入 "101"

输出： 否

解释

对于二进制字符串“101”，十进制值确定为 1 × 2^2 + 0 × 2^1 + 1 × 2^0 = 4 + 0 + 1 = 5。由于 5 不能被 3 整除，DFA 不会终止于状态 0，这表明该数字不是 3 的倍数。因此，输出为“否”。

示例 3

输入 "1111"

输出： 是

解释

对于二进制字符串“1111”，十进制等效值计算为 1 × 2^3 + 1 × 2^2 + 1 × 2^1 + 1 × 2^0 = 8 + 4 + 2 + 1 = 15。由于 15 可被 3 整除，DFA 达到状态 0，确认该数字是 3 的倍数。因此，输出为“是”。

方法 1：使用 DFA（确定性有限自动机）

算法

步骤 1：将状态初始化为 0，代表可被 3 整除的数字。

步骤 2：通过将二进制字符串转换为字符数组以便于处理，来迭代二进制字符串的每一位。

步骤 3：根据当前位和状态之间的转换如下：

步骤 3.1：如果位是 0

步骤 3.1.1：如果已处于状态 0，则保持在状态 0。

步骤 3.1.2：如果在状态 1，则移至状态 2。

步骤 3.1.3：如果在状态 2，则移至状态 1。

步骤 3.2：如果位是 1

步骤 3.2.1：如果在状态 0，则移至状态 1。

步骤 3.2.2：如果在状态 1，则移至状态 0。

步骤 3.2.3：如果已处于状态 2，则保持在状态 2。

步骤 4：如果二进制字符串包含除 0 或 1 以外的任何字符，则立即返回 false。

步骤 5：处理完所有位后，检查最终状态。如果状态为 0，则返回 true，表示该数字可被 3 整除。否则，返回 false。

步骤 6：函数根据最终状态返回结果并完成过程。

实施

输出

 
Input: 110 -> Output: Yes
Input: 101 -> Output: No
Input: 1111 -> Output: Yes   

复杂度分析

时间复杂度

该算法的时间复杂度为 O(N)，其中 N 是二进制字符串的长度，因为每一位都恰好被处理一次。

空间复杂度

空间复杂度为 O(1)，因为只使用了几个整数变量，需要恒定的空间。

方法 2：使用递归计算余数

算法

步骤 1：首先定义一个递归函数，该函数计算二进制数除以 3 的余数。该函数以二进制字符串、当前索引和余数作为参数。如果索引达到字符串的长度，则返回最终余数。

步骤 2：通过将字符转换为整数（0 或 1），从二进制字符串中提取当前位。使用以下公式更新余数

此步骤确保余数根据迄今为止处理过的位不断更新。

步骤 3：进行递归调用以处理二进制字符串中的下一位，将索引加 1。它会一直进行，直到所有位都被处理完毕。

步骤 4：在主函数中，通过检查二进制字符串是否仅包含 0 和 1 来验证输入。如果输入包含无效字符，则返回 false。

步骤 5：以初始余数 0 和索引 0 调用递归函数。处理完所有位后，检查最终余数是否为 0。如果是，则返回 true，表示该数字是 3 的倍数；否则，返回 false。

步骤 6：打印多个测试用例的结果，然后演示该函数如何正确确定给定的二进制字符串是否代表一个可被 3 整除的数字。

实施

输出

 
Input: 110 -> Output: Yes
Input: 101 -> Output: No
Input: 1111 -> Output: Yes   

复杂度分析

时间复杂度

该算法的时间复杂度为 O(N)，其中 N 是二进制字符串的长度，因为每一位都恰好被处理一次。

空间复杂度

由于递归调用栈的长度与输入字符串的长度成线性关系，因此空间复杂度为 O(N)。

方法 3：使用分治技术

算法

步骤 1：如果二进制字符串为空，则返回 0 作为余数。如果它只包含一位，则计算其除以 3 的余数并返回该值。它作为递归的基准情况。

步骤 2：将二进制字符串分成两半。第一半由最左边的位组成，第二半由最右边的位组成。

步骤 3：使用相同的函数递归地分别计算左半部分和右半部分的余数。每次递归调用都会继续分割字符串，直到达到基准情况。

步骤 4：计算右半部分长度的 2 的幂模 3。它确保在合并两半的结果时，左半部分的影响在模算术中被正确缩放。

步骤 5：使用公式 (左余数 * 幂 + 右余数) % 3 组合左半部分和右半部分的余数。此步骤在保持模算术正确性的同时合并结果。

步骤 6：如果最终余数为 0，则二进制字符串表示一个可被 3 整除的数字，因此返回 true。否则，返回 false。

实施

输出

 
Input: 110 -> Output: Yes
Input: 101 -> Output: No
Input: 1111 -> Output: Yes   

复杂度分析

时间复杂度

此方法的时​​间复杂度为 O(N log N)，因为函数递归地分割二进制字符串，导致对数深度，并且每个级别都处理字符串的一部分。

空间复杂度

由于存储在调用栈中的递归函数调用，空间复杂度为 O(log N)。