C ++でのDFAベースの除算？

決定性有限オートマトン（DFA）は、ある数が別の数kで割り切れるかどうかを確認するために使用されます。このアルゴリズムは、数値が割り切れない場合でも余りを見つけることができるので便利です。

DFAベースの除算では、k個の状態を持つDFAテーブルを作成します。数値の2進表現を考慮しているため、DFAの各状態には0と1しかありません。

createTransTable（int k、int transTable [] [2]）関数は、transTableを作成し、その中に状態を格納するために使用されます。除算可能な数kと、2列の配列であるtransTable[][2]を使用します。次に、ビット0の次の状態を格納する2つの変数trans_0と、ビット1の次の状態を格納するtrans_1を宣言します。

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

内部のforループは、状態がk未満になるまで実行されます。 trans_0が数値kより小さい場合、transTable [state] [0]はtrans_0に等しくなります。それ以外の場合、kはtrans_0から減算されます。

trans_1の場合trans_1が数値kより小さい場合、transTable [state] [1]はtrans_1と等しくなります。それ以外の場合、kは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;
}

checkDivisible（int num、int＆state、int transTable [] [2]）関数は、分割される数値、参照による状態変数、およびtransTable[][2]配列を受け取ります。数値が0に等しくないかどうかをチェックし、基本的に、ビット単位の右シフトを使用して数値を左から右に1シフトし、再帰的に呼び出して数値が0になるまでシフトします。右にシフトすると、数値は0になるまで2で除算されます。次に、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<< " 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