डिटरमिनिस्टिक फाइनाइट ऑटोमेटन (DFA) का उपयोग यह जांचने के लिए किया जाता है कि कोई संख्या किसी अन्य संख्या k से विभाज्य है या नहीं। एल्गोरिदम उपयोगी है क्योंकि यदि संख्या विभाज्य नहीं है तो यह शेषफल भी ढूंढ सकता है।
DFA आधारित विभाजन में हम k स्टेट्स के साथ एक DFA टेबल बनाते हैं। हम संख्या के बाइनरी प्रतिनिधित्व पर विचार करते हैं इसलिए प्रत्येक स्टेट में DFA में केवल 0 और 1 होता है।
createTransTable(int k, int transTable[][2]) फंक्शन ट्रांजिशन टेबल बनाने और उसमें स्टेट्स संग्रहीत करने के लिए उपयोग किया जाता है। यह वह संख्या k लेता है जिससे संख्या विभाज्य होनी चाहिए और transTable[][2] जो 2 कॉलम वाला एक सरणी है। हम फिर दो वेरिएबल घोषित करते हैं trans_0 जो बिट 0 का अगला स्टेट संग्रहीत करता है और trans_1 जो बिट 1 का अगला स्टेट संग्रहीत करता है।
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;
अंदर फॉर लूप तब तक चलता है जब तक स्टेट k से कम है। यदि trans_0 संख्या k से कम है तो transTable[state][0] trans_0 के बराबर होता है अन्यथा trans_0 से k घटाया जाता है।
trans_1 के लिए यदि trans_1 संख्या k से कम है तो transTable[state][1] trans_1 के बराबर होता है अन्यथा trans_1 से k घटाया जाता है।
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 के बराबर नहीं है तो यह मूल रूप से संख्या को बिटवाइज राइट शिफ्ट का उपयोग करके बाएं से दाएं शिफ्ट करता है जब तक संख्या रिकर्सिवली खुद को कॉल करके 0 नहीं बन जाती। राइट शिफ्ट करके संख्या 2 से विभाजित होती है जब तक यह 0 नहीं बन जाती। 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 leaves remainder " << remainder;
return 0;
}
आउटपुट
उपरोक्त कोड निम्नलिखित आउटपुट देगा।
67 is not divisible by 5 and leaves remainder 2
