ডিটারমিনিস্টিক ফিনিট অটোমেটন (ডিএফএ) ব্যবহার করা হয় একটি সংখ্যা অন্য সংখ্যা k দ্বারা বিভাজ্য কিনা তা পরীক্ষা করার জন্য। অ্যালগরিদমটি কার্যকর কারণ সংখ্যাটি বিভাজ্য না হলে এটি অবশিষ্টাংশও খুঁজে পেতে পারে।
DFA ভিত্তিক বিভাগে আমরা k রাজ্যের সাথে একটি DFA টেবিল তৈরি করি। আমরা সংখ্যার বাইনারি উপস্থাপনা বিবেচনা করি তাই DFA-তে প্রতিটি রাজ্যে শুধুমাত্র 0 এবং 1 আছে।
createTransTable(int k, int transTable[][2]) ফাংশনটি transTable তৈরি করতে এবং এতে স্টেট সংরক্ষণ করার জন্য ব্যবহৃত হয়। এটি k সংখ্যাটি নেয় যার দ্বারা সংখ্যাটি বিভাজ্য এবং ট্রান্সটেবল[][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 এর সমান অন্যথা 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 হয়ে যায়। তারপরে ট্রান্সটেবল[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) ফাংশনটি লভ্যাংশ সংখ্যা এবং লভ্যাংশ k নেয়। ট্রান্সটেবল[k][2] সারির 2টি কলাম এবং k সংখ্যা সহ ট্রানজিশন টেবিল ঘোষণা করা হয়েছে। 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
