确定性有限自动机（DFA） 可用于检查数字“num”是否可被“k”整除。如果这个数字不可除，那么也可以使用DFA获得余数。 我们考虑了“num”的二进制表示，并用k状态建立了一个DFA。DFA具有0和1的转换功能。一旦构建了DFA，我们就在DFA上处理’num’以获得余数。 让我们来看一个例子。假设我们想检查一个给定的数字’num’是否可以被3整除。任何数字都可以写成：num=3*a+b，其中a是商，b是余数。 对于3，DFA中可以有3个状态，每个状态对应于余数0、1和2。每个状态可以有两个对应于0和1的转换（考虑给定’num’的二进制表示）。 转换函数F（p，x）=q告诉我们，在读取字母x时，我们从状态p移动到状态q。让我们将状态命名为0、1和2。初始状态将始终为0。最终状态表示剩余状态。如果最终状态为0，则该数字是可除的。
![图片[1]-基于DFA的部门-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_dfadivision-1.jpg)
在上图中，双圈状态是最终状态。 1.当我们处于0状态并读取0时，我们保持在0状态。 2.当我们处于状态0并读取1时，我们会移动到状态1，为什么？这样形成的数字（1）在十进制中表示余数1。 3.当我们处于状态1并读取0时，我们会移动到状态2，为什么？这样形成的十进制数（10）为余数2。 4.当我们处于状态1并读取1时，我们会移动到状态0，为什么？这样形成的十进制数字（11）给出余数0。 5.当我们处于状态2并读取0时，我们会移动到状态1，为什么？这样形成的十进制数（100）得到余数1。 6.当我们处于状态2，读到状态1时，我们仍然处于状态2，为什么？这样形成的数字（101）用十进制GVE余数2表示。 转换表如下所示：
state 0 1_____________ 0 0 1 1 2 0 2 1 2
让我们检查一下6是否可以被3整除？ 6的二进制表示是110 状态=0 1.状态=0，我们读1，新状态=1 2.状态=1，我们读1，新状态=0 3.状态=0，我们读取0，新状态=0 因为最终状态是0，所以这个数字可以被3整除。 让我们再举一个例子，数字是4 状态=0 1.状态=0，我们读1，新状态=1 2.状态=1，我们读取0，新状态=2 3.状态=2，我们读取0，新状态=1 因为最终状态不是0，所以数字不能被3整除。剩下的是1。 请注意，最终状态给出了余数。 我们可以将上述解推广到任意k值。对于k值，状态为0，1，k-1。如果到目前为止看到的二进制位的十进制等价物超过范围k，如何计算转换？如果我们处于p状态，我们已经读取了p（十进制）。现在我们读0，新的读数变成2*p。如果我们读1，新的读数变成2*p+1。新状态可以通过从这些值（2p或2p+1）中减去k来获得，其中0<=p
C++
#include <bits/stdc++.h> using namespace std; // Function to build DFA for divisor k void preprocess( int k, int Table[][2]) { int trans0, trans1; // The following loop calculates the // two transitions for each state, // starting from state 0 for ( int state = 0; state < k; ++state) { // Calculate next state for bit 0 trans0 = state << 1; Table[state][0] = (trans0 < k) ? trans0 : trans0 - k; // Calculate next state for bit 1 trans1 = (state << 1) + 1; Table[state][1] = (trans1 < k) ? trans1 : trans1 - k; } } // A recursive utility function that // takes a 'num' and DFA (transition // table) as input and process 'num' // bit by bit over DFA void isDivisibleUtil( int num, int * state, int Table[][2]) { // process "num" bit by bit // from MSB to LSB if (num != 0) { isDivisibleUtil(num >> 1, state, Table); *state = Table[*state][num & 1]; } } // The main function that divides 'num' // by k and returns the remainder int isDivisible ( int num, int k) { // Allocate memory for transition table. // The table will have k*2 entries int (*Table)[2] = ( int (*)[2]) malloc (k* sizeof (*Table)); // Fill the transition table preprocess(k, Table); // Process ‘num’ over DFA and // get the remainder int state = 0; isDivisibleUtil(num, &state, Table); // Note that the final value // of state is the remainder return state; } // Driver Code int main() { int num = 47; // Number to be divided int k = 5; // Divisor int remainder = isDivisible (num, k); if (remainder == 0) cout << "Divisible" ; else cout << "Not Divisible: Remainder is " << remainder; return 0; } // This is code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> // Function to build DFA for divisor k void preprocess( int k, int Table[][2]) { int trans0, trans1; // The following loop calculates the two transitions for each state, // starting from state 0 for ( int state=0; state<k; ++state) { // Calculate next state for bit 0 trans0 = state<<1; Table[state][0] = (trans0 < k)? trans0: trans0-k; // Calculate next state for bit 1 trans1 = (state<<1) + 1; Table[state][1] = (trans1 < k)? trans1: trans1-k; } } // A recursive utility function that takes a 'num' and DFA (transition // table) as input and process 'num' bit by bit over DFA void isDivisibleUtil( int num, int * state, int Table[][2]) { // process "num" bit by bit from MSB to LSB if (num != 0) { isDivisibleUtil(num>>1, state, Table); *state = Table[*state][num&1]; } } // The main function that divides 'num' by k and returns the remainder int isDivisible ( int num, int k) { // Allocate memory for transition table. The table will have k*2 entries int (*Table)[2] = ( int (*)[2]) malloc (k* sizeof (*Table)); // Fill the transition table preprocess(k, Table); // Process ‘num’ over DFA and get the remainder int state = 0; isDivisibleUtil(num, &state, Table); // Note that the final value of state is the remainder return state; } // Driver program to test above functions int main() { int num = 47; // Number to be divided int k = 5; // Divisor int remainder = isDivisible (num, k); if (remainder == 0) printf ( "Divisible" ); else printf ( "Not Divisible: Remainder is %d" , remainder); return 0; } |
输出：
Not Divisible: Remainder is 2
时间复杂性： O（k）
如果我们有一个二进制流作为输入，并且希望随时检查流的十进制值的可整除性，那么基于DFA的除法可能很有用。 相关文章： 检查二进制流中的可除性 检查流是否是3的倍数 本文由 阿希什·巴恩瓦尔 并由Geeksforgeks团队审核。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
