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