ফিবোনাচ্চি নাম্বার এবং ডায়নামিক প্রোগ্রামিং(Fibonacci Number and Dynamic Programming)

 

ত্রয়োদ্বশ শতাব্দী তে বিখ্যাত ইতালীয় গণিতবীদ ফিবোনাচ্চি খরগোশের বংশবৃদ্ধি পর্যবেক্ষণ করতে গিয়ে একটি সিরিজ দেখতে পান। সিরিজটি হচ্ছে, ০ ১ ১ ২ ৩ ৫ ৮ ১৩ ২১। তার নামানুসারেই এই সিরিজ কে বলা ফিবোনাচ্চি সিরিজ। 

সিরিজটির ১ম সংখ্যা হচ্ছে ০ এবং ২য় সংখ্যা হচ্ছে ১, তাছাড়া বাকি সংখ্যা গুলো হচ্ছে পূর্বের দুইটি সংখ্যার যোগফল। মানে n তম ফিবোনাচ্চি সংখ্যা হচ্ছে, n-1 তম ফিবোনাচ্চি এবং n-2 তম ফিবোনাচ্চি সংখ্যার যোগফল। তাহলে n তম ফিবোনাচ্চি সংখ্যা কীভাবে বের করতে পারি? একটি সহজ সমাধান হচ্ছে, রিকারসিভ ফাংশন দিয়ে সংখ্যা টি বের করে আনা। যদি n তম ফিবোনাচ্চি সংখ্যা বের করতে চাই তাহলে, ফাংশন টি ডিজাইন করব এভাবে, Fib(n) = Fib(n-1) + Fib(n-2) এবং বেইস কেইস মানে n যখন ১ বা ০ হবে তখন n রিটার্ন করে দিব। যেহেতু ১ম এবং ২য় সংখ্যা দুটি হচ্ছে, ০ এবং ১। এবার তাহলে প্রোগ্রাম টি লিখে ফেলি।

int Fibonacci(int n) {   if (n==1 || n==0) // Base Case     return n;   return Fibonacci(n-1) + Fibonacci(n-2); }

কমপ্লেক্সিটি হবে 2^n। যেহেতু প্রতি ফাংশন থেকে আরো ২টি ফাংশন কে কল করতেছি এবং এভাবে বেইস কেইসে গিয়ে আবার ফেরত আসার সময় ফিবোনাচ্চি সংখ্যা ক্যালকুলেট করে নিয়ে আসবে। যদি বুঝতে সমস্যা হয় এবং আরো ভালো করে বুঝতে চান তাহলে নিচের ছবি টি দেখুন।

ধরে নেই n হচ্ছে ৫ এবং যেহেতু, প্রতি ফাংশন থেকে আরো দুইটি ফাংশন কে কল করতেছি সেহেতু, ৫ থেকে যাবে ৪ এবং ৩ এ। আবার তাদের থেকে আরো দুইটি করে কল হবে। এভাবে চলতে থাকবে যতক্ষণ না বেইস কেইসে যাবে। মানে n সমান ০ বা ১ হলে আবার রিটার্ন করে ফাংশন কে ফেরত পাঠিয়ে দিবে তবে সাথে ফাংশনে ভ্যালু দিয়ে দিবে, n ০ হলে ০ এবং ১ হলে ১। তারপর ফেরত যাওয়ার সময় যে ফাংশন গুলো কল হয়েছিলো তাদের মাধ্যমে ক্যালকুলেট হতে থাকবে এভাবে, ০ ১ ১ ২। এখন যারা রিকারশনের সাথে পরিচিত না তারা ভাবতে পারেন, যে ফাংশন গুলো কল হয়েছিলো, ফেরত যাওয়ার সময় তা আবার পাব কীভাবে? রিকারশন ফাংশনের সুবিধা হচ্ছে, প্রতি কল সম্পন্ন হয়ে পরবর্তী ফাংশন কল হওয়ার আগে তা কম্পিউটারের স্ট্যাকে জমা হয়ে থাকে। তবে এর বড় অসুবিধা হচ্ছে, অনেক মেমোরি লাগে। আশা করছি বুঝতে পেরেছেন।

এবার উপরের ছবিতে যদি লাল কালারের ফাংশন গুলোর দিকে তাকান তাহলে বুঝতে পারবেন এগুলো কল করার কোন দরকার ই ছিলো না। কোন দরকার ছাড়াই এগুলো দুইবার বা তার অধিক কল হয়েছে। n সমান ৫ বলে তেমন বুঝা যাচ্ছে, কিন্তু যত বেশি হবে তত বেশি এই অযথা কাজ গুলো আরো বেশি হবে। আচ্ছা, এই অযথা ফাংশন কল গুলো এড়িয়ে যাওয়ার কোন উপায় আছে? উপায় আছে, যদি কোন ভাবে মনে রাখতে পারি Fib(1) ফাংশন টি এর আগে ক্যালকুলেট করে ফেলেছি তাহলেই কিন্তু পরে অযথা চারবার এই ফাংশন কে আবার কল করে ক্যালকুলেট করতে হবে না। এই যে মনে রাখার কাজ, এটি কে বলে মেমোরাইজেশন আর মনে রেখে অদরকারী কাজ এড়িয়ে চলাকেই বলে ডায়নামিক প্রোগ্রামিং!!! এখন প্রোগ্রামের কমপ্লেক্সিটি হবে O(n)। O(2^n) থেকে O(n) মানে, কত কাজ কমে যাচ্ছে তা একটু ইমাজিন করতে পারেন।

এখন তাহলে, মেমোরাইজেশন করব কীভাবে? একটি অ্যারে নিতে পারি n সাইজের। সব গুলোতে আগে ০ বা -১ রেখে দিব। কল করে ক্যালকুলেশন হওয়ার পরে ক্যালকুলেটেড রেজাল্ট, মানে বর্তমান n তম ফিবোনাচ্চি অ্যারের n তম পজিশনে রেখে দিবো। এটি করব যদি অ্যারের n তম ঘরে আগেই ক্যালকুলেটেড ভ্যালু না থাকে। মানে, আগেই যদি ক্যালকুলেড করে থাকি তাহলে আর সামনে যাব না, সেটিই রিটার্ন করে দিব। ক্যালকুলেট করেছি কিনা এটি বুঝব n তম ঘরে -১ আছে কিনা। থাকলে ক্যালকুলেট হয়নি আর না থেকে অন্য কোন ভ্যালু থাকলে ক্যালকুলেট হয়েছে এবং সেটি n তম ফিবোনাচ্চি নাম্বার।

const int N = 20; int Fib[N+1]; int Fibonacci(int n) {   // Base Case   if (n==1 || n==0) return Fib[n] = n;   // Return if it's already calculated   if (Fib[n] != -1) return Fib[n];   return Fib[n] = Fibonacci(n-1) + Fibonacci(n-2); } int main() {   // Initialize with safe value   for (int i = 0;i <= N;i++) {     Fib[i] = -1;   }   Fibonacci(N);   cout << Fib[20] << endl;   cout << Fib[0] << endl;   cout << Fib[1] << endl;   cout << Fib[5] << endl;   return 0; }

এর আরেকটি বড় সুবিধা আছে। আমি মেমোরাইজেশনের সময় কী করেছি? অবশ্যই n তম ফিবোনাচ্চি নাম্বার অ্যারের n তম ঘরে রেখে দিয়েছি যেন সেটি আবার ক্যালকুলেট না হয়। এভাবে কিন্তু ০ থেকে n পর্যন্ত সব ঘরের জন্যেই আমাকে ফিবোনাচ্চি নাম্বার রাখতে হয়েছে। মানে, আমি মেমোরাইজেশন করতে গিয়ে O(n) সময়ে ০ থেকে n পর্যন্ত প্রতিটি নাম্বারের ফিবোনাচ্চি বের করে তাদের কে অ্যারে তে রেখে দিয়েছি! এখন যদি বলে শুধু একটি নাম্বারের জন্য না, ৪ টি নাম্বারের জন্য ফিবোনাচ্চি বের করো। তাহলে কিন্তু আমাকে ৪ টি নাম্বারের জন্য চারবার O(n) সময়ে ফাংশন কল করে ৪ টি ফিবোনাচ্চি বের করার প্রয়োজন নেই। এটিও এখন অপ্রয়োজনীয় কাজ হয়ে গেছে। উপরের প্রোগ্রামে আমি তাই করেছি। ০ থেকে ২০ পর্যন্ত সবগুলো নাম্বারের জন্য ফিবোনাচ্চি বের করে অ্যারে তে রেখে দিয়েছি O(20) সময়ে। এরপর O(1) সময়ে ফিবোনাচ্চি নাম্বার শুধু প্রিন্ট করে দিয়েছি কাঙ্ক্ষিত নাম্বারের জন্য। তবে ডায়নামিক প্রোগ্রামিংয়ের বেলায় অবশ্যই মেমোরি হ্যান্ডেলিং টা একটু সতর্কতার সাথে করতে হবে।

রিকারশন দিয়ে ডায়নামিক প্রোগ্রামিং ব্যবহার করে ফিবোনাচ্চি বের করলাম, এবার এই কাজ টি ইটারেটিভ ডিপি দিয়ে করব। এটিও খুব সহজ কাজ। n সাইজের একটি অ্যারে নিব, এরপর যেহতু জানি ফিবোনাচ্চির ১ম ও ২য় নাম্বার যথাক্রমে ০ এবং ১ তাই অ্যারের ১ম ও ২য় ঘরে যথাক্রমে ০ এবং ১ বসিয়ে দিব। রিকারসিভ ডিপির বেইস কেইস এটি, নিশ্চয়ই বুঝতে পেরেছেন। ডিপি তে বেইস কেইস বের করতে পারলেই কাজ প্রায় সম্পন্ন হয়ে যায়। এরপরের কাজ হচ্ছে ২ থেকে n পর্যন্ত লুপ চালাব এবং বর্তমান পজিশনে আগের দুই পজিশনের যোগফল রেখে দিব, Fib[i] = Fib[i-1] + Fib[i-2]; (when i is greater than 1)

উপরের ছবি টি দেখার পর আশা করছি আরো পরিস্কার বুঝতে পেরেছেন এবং আরো আশা করছি এই কাজ টি এখন নিজেই করে ফেলতে পারবেন। আমি কোড দিয়ে দিচ্ছি, অবশ্যই নিজে চেষ্টা করার পরে দেখবেন।

const int N = 20; int Fib[N+1]; void Fibonacci() {   // Base Case   Fib[0] = 0;   Fib[1] = 1;   for (int i = 2;i <= N;i++) {     Fib[i] = Fib[i-1] + Fib[i-2];   } }

আশা করছি ডায়নামিক প্রোগ্রামিং শুরু করার জন্য অল্প কিছু হলেও বুঝাতে পেরেছি। ডায়নামিক প্রোগ্রামিং সহজ বিষয় তবে একটু চিন্তা করতে হয় বেশি এবং বেশি কেইস হ্যান্ডেল করতে হয়। বেশি বেশি শিখতে থাকুন এবং প্র্যাক্টিস করতে থাকুন, আপনার চলার পথ সুন্দর অভিজ্ঞতাময় হোক <3