डीएफए आधारित डिवीजन

Deterministic Finite Automaton(DFA) का उपयोग यह जांचने के लिए किया जाता है कि कोई संख्या किसी अन्य संख्या k से विभाज्य है या नहीं। यदि यह विभाज्य नहीं है, तो यह एल्गोरिथम शेषफल भी खोज लेगा।

DFA बेस्ड डिवीजन के लिए सबसे पहले हमें DFA की ट्रांजिशन टेबल ढूंढनी होती है, उस टेबल का इस्तेमाल करके हम आसानी से जवाब ढूंढ सकते हैं। DFA में, प्रत्येक राज्य में केवल दो संक्रमण 0 और 1 होते हैं।

इनपुट और आउटपुट

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

एल्गोरिदम

dfaDivision(num, k)

इनपुट: एक संख्या संख्या, और भाजक k.

आउटपुट: विभाज्यता और शेष की जाँच करें।

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, State, table)

इनपुट: एक संख्या संख्या, स्थिति और संक्रमण तालिका।

>आउटपुट: विभाजन करने के बाद राज्य को अपडेट करें।

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

उदाहरण

#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;
}

आउटपुट

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