C++中基于DFA的除法？

2023-06-21 12:30:02 212

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

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

createTransTable(intk,inttransTable[][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(intnum,int&state,inttransTable[][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(intnum,intk)函数计算被除数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 
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 <输出结果
上面的代码将产生以下输出。
67 不能被整除 5 and lefts remainder 2

C++中基于DFA的除法？

示例

热门推荐

随机推荐