ডিটারমিনিস্টিক ফাইনাইট অটোমেটা (DFA) ব্যবহার করা হয় একটি সংখ্যা অন্য সংখ্যা k দিয়ে বিভাজ্য কিনা চেক করতে। এই অ্যালগরিদম উপকারী কারণ এটি রিমেন্ডারও বের করতে পারে যদি সংখ্যাটি বিভাজ্য না হয়।
DFA ভিত্তিক ডিভিশনে আমরা k স্টেটের একটি DFA টেবিল বানাই। আমরা সংখ্যার বাইনারি রিপ্রেজেন্টেশন বিবেচনা করি তাই প্রতিটি স্টেটে শুধু 0 এবং 1 থাকে।
createTransTable(int k, int transTable[][2]) ফাংশন transTable তৈরি করতে এবং স্টেটগুলো স্ট্রোর করতে ব্যবহৃত হয়। এটি বিভাজক সংখ্যা k এবং transTable[][2] নেয় যেটি ২ কলামের একটি অ্যারে। তারপর দুটি ভেরিয়েবল ডিক্লেয়ার করা হয় trans_0 যেটি বিট ০ এর নেক্স্ট স্টেট স্ট্রোর করে এবং trans_1 যেটি বিট ১ এর নেক্স্ট স্টেট স্ট্রোর করে।
void createTransTable(int k, int transTable[][2]){
int trans_0, trans_1;
ফর লুপ স্টেট k চেয়ে কম रहने পর্যন্ত চলে। যদি trans_0 k চেয়ে কম হয় তবে transTable[state][0] trans_0 সমান হবে অন্যথায় k বিয়োগ করা হবে।
trans_1-এর জন্য যদি trans_1 k চেয়ে কম হয় তবে transTable[state][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]) ফাংশন ভাগ যাবে সংখ্যা, রেফারেন্স হিসেবে state ভেরিয়েবল এবং transTable[][2] অ্যারে নেয়। এটি চেক করে যদি সংখ্যা ০ না হয় তবে বিটওয়াইজ রাইট শিফ্ট ১ দিয়ে সংখ্যাকে বাম থেকে ডানে শিফ্ট করে রিকার্সিভলি নিজেকে কল করে যতক্ষণ না সংখ্যা ০ হয়। রাইট শিফ্ট করলে সংখ্যা ২ দিয়ে ভাগ হয় যতক্ষণ না ০ হয়। transtable[state][num&1] এরপর state ভেরিয়েবলে অ্যাসাইন করা হয়।
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 নেয়। ২ কলাম এবং k সারিয়ुक्त ট্রানজিশন টেবিল transTable[k][2] ডিক্লেয়ার করা হয়। createTransTable(k, transTable) এবং checkDivisible(num, state, transTable) কল করা হয় যা state ভেরিয়েবল মডিফাই করে। state ভেরিয়েবল ফেরত দেওয়া হয় যা আমাদের ভাগশেষ রিপ্রেজেন্ট করে।
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
