C++中基于DFA的除法？

确定性有限Automaton(DFA)用于检查一个数是否可以被另一个数 k 整除。该算法很有用，因为如果数字不可整除，它也可以找到余数。

在基于 DFA 的划分中，我们构建了一个包含 k 个状态的 DFA 表。我们考虑数字的二进制表示，因此 DFA 中每个状态只有 0 和 1。

createTransTable(int k, int transTable[][2]) 函数用于创建 transTable 并在其中存储状态。它需要数字 k 和 transTable[][2] 是一个有 2 列的数组。然后，我们声明两个变量 trans_0 存储位 0 下一个状态和 trans_1 存储位 1 下一个状态。

void createTransTable(int k, int transTable[][2]){
   int trans_0, trans_1;

内部的 for 循环运行直到状态小于 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] 分配给状态变量。

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<< " 可被整除 "<<k;
   else
      cout <<num<< " 不能被整除 "<<k<<" and lefts remainder "<<remainder;
   return 0;
}

上面的代码将产生以下输出。

67 不能被整除 5 and lefts remainder 2