Bộ phận dựa trên DFA

Tự động hóa hữu hạn xác định (DFA) được sử dụng để kiểm tra xem một số có chia hết cho một số k khác hay không. Nếu nó không chia hết, thì thuật toán này cũng sẽ tìm phần còn lại.

Đối với phân chia dựa trên DFA, đầu tiên, chúng ta phải tìm bảng chuyển tiếp của DFA, sử dụng bảng đó, chúng ta có thể dễ dàng tìm ra câu trả lời. Trong DFA, mỗi trạng thái chỉ có hai chuyển tiếp 0 và 1.

Đầu vào và Đầu ra

Input:
The number: 50 and the divisor 3
Output:
50 is not divisible by 3 and remainder is: 2

Thuật toán

dfaDivision(num, k)

Đầu vào: Một số num và ước số k.

Đầu ra: Kiểm tra phần chia hết và phần còn lại.

Begin
   create transition table of size k * 2 //2 for transition 0 and 1
   state = 0
   checkState(num, state, table)
   return state
End

checkState (num, trạng thái, bảng)

Đầu vào: Một số, trạng thái và bảng chuyển tiếp.

Đầu ra: Cập nhật trạng thái sau khi thực hiện phân chia.

Begin
   if num ≠ 0, then
      tempNum := right shift number for i bit
      checkState(tempNum, state, table)
      index := number AND 1 //perform logical and with number and 1
      state := table[state][index]
End

Ví dụ

#include <iostream>
using namespace std;

void makeTransTable(int n, int transTable[][2]) {
   int zeroTrans, oneTrans;

   for (int state=0; state<n; ++state) {
      zeroTrans = state<<1;   //next state for bit 0
      transTable[state][0] = (zeroTrans < n)? zeroTrans: zeroTrans-n;

      oneTrans = (state<<1) + 1;    //next state for bit 1
      transTable[state][1] = (oneTrans < n)? oneTrans: oneTrans-n;
   }
}

void checkState(int num, int &state, int Table[][2]) {
   if (num != 0) {    //shift number from right to left until 0
      checkState(num>>1, state, Table);
      state = Table[state][num&1];
   }
}

int isDivisible (int num, int k) {
   int table[k][2];    //create transition table
   makeTransTable(k, table);    //fill the table
   int state = 0;    //initially control in 0 state
   checkState(num, state, table);
   return state;    //final and initial state must be same
}

int main() {
   int num;
   int k;
   cout << "Enter Number, and Divisor: "; cin >> num>> k;
   int rem = isDivisible (num, k);
   if (rem == 0)
      cout<<num<<" is divisible by "<<k;
   else
      cout<<num<<" is not divisible by "<<k<<" and remainder is: " << rem;
}

Đầu ra

Enter Number, and Divisor: 50 3
50 is not divisible by 3 and remainder is: 2