परिचय
डिटरमिनिस्टिक फाइनाइट ऑटोमेटन (DFA) का उपयोग यह जांचने के लिए किया जाता है कि कोई संख्या किसी अन्य संख्या k से विभाज्य है या नहीं। यदि यह विभाज्य नहीं है, तो यह एल्गोरिदम शेषफल भी ज्ञात करेगा।
DFA आधारित विभाजन के लिए, सबसे पहले, हमें DFA की संक्रमण तालिका ढूंढनी होगी, उस तालिका का उपयोग करके, हम आसानी से उत्तर ढूंढ सकते हैं। DFA में, प्रत्येक अवस्था के केवल दो संक्रमण होते हैं 0 और 1।
इनपुट और आउटपुट
इनपुट: संख्या: 50 और भाजक 3 आउटपुट: 50, 3 से विभाज्य नहीं है और शेषफल है: 2
एल्गोरिदम
dfaDivision(num, k)
इनपुट: एक संख्या num, और भाजक k
आउटपुट: विभाज्यता जांचें और शेषफल
Begin
k * 2 आकार की संक्रमण तालिका बनाएं // 0 और 1 संक्रमण के लिए 2
state = 0
checkState(num, state, table)
state लौटाएं
End
checkState(num, state, table)
इनपुट: एक संख्या num, अवस्था, और संक्रमण तालिका।
आउटपुट: विभाजन करने के बाद अवस्था को अपडेट करें।
Begin
यदि num ≠ 0, तो
tempNum := i बिट के लिए संख्या को दाएं शिफ्ट करें
checkState(tempNum, state, table)
index := number AND 1 // संख्या और 1 के साथ तार्किक AND करें
state := table[state][index]
End
उदाहरण (C++ कोड)
#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; // बिट 0 के लिए अगली अवस्था
transTable[state][0] = (zeroTrans < n) ? zeroTrans : zeroTrans - n;
oneTrans = (state << 1) + 1; // बिट 1 के लिए अगली अवस्था
transTable[state][1] = (oneTrans < n) ? oneTrans : oneTrans - n;
}
}
void checkState(int num, int &state, int Table[][2]) {
if (num != 0) {
// संख्या को दाएं से बाएं शिफ्ट करें जब तक 0 न हो जाए
checkState(num >> 1, state, Table);
state = Table[state][num & 1];
}
}
int isDivisible(int num, int k) {
int table[k][2]; // संक्रमण तालिका बनाएं
makeTransTable(k, table); // तालिका भरें
int state = 0; // प्रारंभ में नियंत्रण 0 अवस्था में
checkState(num, state, table);
return state; // अंतिम और प्रारंभिक अवस्था समान होनी चाहिए
}
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
