ডিটারমিনিস্টিক ফাইনাইট অটোমেটা (DFA) ব্যবহার করে চেক করা যায় একটি সংখ্যা অন্য সংখ্যা k দিয়ে বিভাজ্য কিনা। যদি বিভাজ্য না হয়, তবে এই অ্যালগরিদম বাকিও বের করবে।
DFA ভিত্তিক বিভাজনের জন্য, প্রথমে DFA-এর ট্রানজিশন টেবিল বের করতে হবে, সেই টেবিল ব্যবহার করে আমরা সহজে উত্তর পেতে পারি। DFA-তে, প্রতিটি স্টেটের শুধু দুটি ট্রানজিশন থাকে ০ এবং ১।
ইনপুট এবং আউটপুট
ইনপুট: সংখ্যাটি: ৫০ এবং বিভাজক ৩ আউটপুট: ৫০, ৩ দিয়ে বিভাজ্য নয় এবং বাকি হল: ২
অ্যালগরিদম
dfaDivision(num, k)
ইনপুট: একটি সংখ্যা num, এবং বিভাজক k।
আউটপুট: বিভাজ্যতা চেক করুন এবং বাকি।
শুরু k * 2 আকারের ট্রানজিশন টেবিল তৈরি করুন //০ এবং ১ ট্রানজিশনের জন্য ২ state = 0 checkState(num, state, table) state ফেরত দিন শেষ
checkState(num, state, table)
ইনপুট: একটি সংখ্যা num, state, এবং ট্রানজিশন টেবিল।
আউটপুট: বিভাজন করার পর state আপডেট করুন।
শুরু
যদি num ≠ 0, তবে
tempNum := i বিটের জন্য ডান শিফট সংখ্যা
checkState(tempNum, state, table)
index := number AND 1 //সংখ্যা এবং ১-এর সাথে লজিক্যাল AND
state := table[state][index]
শেষউদাহরণ
#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; //বিট ০ এর জন্য পরবর্তী স্টেট transTable[state][0] = (zeroTrans < n)? zeroTrans: zeroTrans-n; oneTrans = (state<<1) + 1; //বিট ১ এর জন্য পরবর্তী স্টেট transTable[state][1] = (oneTrans < n)? oneTrans: oneTrans-n; } } void checkState(int num, int &state, int Table[][2]) { if (num != 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; //প্রাথমিকভাবে কন্ট্রোল ০ স্টেটে 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
