C++ 中基于 DFA 的除法?
确定性有限自动机 (DFA) 用于检查某个数字是否能被另一个数字 k 整除。该算法很有用，因为如果数字不能整除，它还可以找到余数。
在基于 DFA 的除法中，我们构建了一个具有 k 个状态的 DFA 表。我们考虑数字的二进制表示，因此 DFA 中每个状态只有 0 和 1。
createTransTable(int k, int transTable[][2]) 函数用于创建 transTable 并在其中存储状态。它采用数字 k(数字能被其整除)和 transTable[][2](一个具有 2 列的数组)。然后我们声明两个变量 trans_0 和 trans_1，前者存储位 0 的下一个状态，后者存储位 1 的下一个状态。
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;
for 循环内部运行直到 state 小于 k。如果 trans_0 小于数字 k，则 transTable[state][0] 等于 trans_0，否则从 trans_0 中减去 k。
对于 trans_1，如果 trans_1 小于数字 k，则 transTable[state][1] 等于 trans_1，否则从 trans_1 中减去 k。
for (int state = 0; state < k; state++){
trans_0 = state << 1;
transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
trans_1 = (state << 1) + 1;
transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}
checkDivisible(int num, int &state, int transTable[][2]) 函数接受要除以的数字、引用的状态变量和 transTable[][2] 数组。它检查数字是否不等于 0，然后基本上使用按位右移 1 将数字从左向右移动，直到数字通过递归调用自身变为 0。通过右移，将数字除以 2，直到变为 0。然后将 transtable[state][num&1] 分配给 state 变量。
void checkDivisible(int num, int &state, int transTable[][2]){
if (num != 0){
checkDivisible(num >> 1, state, transTable);
state = transTable[state][num&1];
}
}
isDivisible (int num, int k) 函数采用被除数 num 和被除数 k。声明了具有 2 列和 k 行的转换表 transTable[k][2]。调用 createTransTable(k, transTable) 和 checkDivisible(num, state, transTable) 来修改状态变量。然后返回状态变量，它表示除法后的余数。
int isDivisible (int num, int k){
int transTable[k][2];
createTransTable(k, transTable);
int state = 0;
checkDivisible(num, state, transTable);
return state;
}
示例
让我们看看以下基于 DFA 的除法实现。
#include <bits/stdc++.h>
using namespace std;
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;
for (int state = 0; state < k; state++){
trans_0 = state << 1;
transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
trans_1 = (state << 1) + 1;
transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}
}
void checkDivisible(int num, int &state, int transTable[][2]){
if (num != 0){
checkDivisible(num >> 1, state, transTable);
state = transTable[state][num&1];
}
}
int isDivisible (int num, int k){
int transTable[k][2];
createTransTable(k, transTable);
int state = 0;
checkDivisible(num, state, transTable);
return state;
}
int main(){
int num = 67;
int k = 5;
int remainder = isDivisible (num, k);
if (remainder == 0)
cout <<num<< " is divisible by "<<k;
else
cout <<num<< " is not divisible by "<<k<<" and lefts remainder "<<remainder;
return 0;
}
输出
上述代码将产生以下输出。
67 is not divisible by 5 and lefts remainder 2
