ডিএফএ ভিত্তিক বিভাগ

Deterministic Finite Automaton(DFA) ব্যবহার করা হয় একটি সংখ্যার k দ্বারা বিভাজ্য কিনা তা পরীক্ষা করতে। যদি এটি বিভাজ্য না হয়, তাহলে এই অ্যালগরিদমটি অবশিষ্টাংশও খুঁজে পাবে।

ডিএফএ ভিত্তিক বিভাগের জন্য, প্রথমে, আমাদের ডিএফএ-এর ট্রানজিশন টেবিলটি খুঁজে বের করতে হবে, সেই টেবিলটি ব্যবহার করে আমরা সহজেই উত্তরটি খুঁজে পেতে পারি। 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