ফিবোনাকি সংখ্যা কি?

অনেক অনেক দিন আগে ইতালিতে একটা বিশাল মাথাওয়ালা গণিতবিদ থাকতো যার নাম ছিল ফিবোনাকি। ফিবোনাকির ছিল অনেক ঝাকড়া চুল, আর সেখানটায় নাকি অনেক গাবদা গাবদা উকুন ছিল। তো সে করতো কি খুব মাথা চুলকাতো, আর সারাদিন বসে বসে ফ্যাঁচ ফ্যাঁচ করে কাঁদতো। তো একদিন সে গেলো গঙ্গা নাপিতের দোকানে। সেখানে গিয়ে সে বগল কামালো আর মাথার সব চুল ফেলে দিলো আর তারপর মুহাহাহাহাহা করে একটা বিশাল বিটকেলে হাসি দিয়ে লুঙ্গি হাতে ধরে নাঁচতে নাঁচতে বাসায় ফিরে আসলো।

কিন্তু উকুন ফেলে দিলে কি হবে, আকাশে একটা শকুন উড়ছিল মিগ২৯ নিয়ে। তো সেই শকুনটা করলো কি ওর মিগ২৯ নিয়ে পুঁউউউউ করে উড়ে আসলো আর একটা ছোট্ট অণূবিক্ষণিক মিসাইলের ডগায় এক জোড়া উকুন নিয়ে সেটা শিউউউ করে ছুঁড়ে মারলো ফিবোনাকির মাথায়।

তো প্রথম মাসে ফিবোনাকির মাথায় ছিল ১ জোড়া উকুন। (সবমিলে ১)

প্রথম মাসের শেষে ১ জোড়াই থাকলো। (সবমিলে ১)

দ্বিতীয় মাসের শুরুতে সেই জোড়া করলো কি, আরো ১ জোড়া উকুনের জন্ম দিলো। 

তো সেই মাসের শেষে ২ জোড়া উকুন থাকলো। (সবমিলে ২)

তৃতীয় মাসে এই ২ জোড়া করলো কি আরো ২ জোড়া জন্ম দিলো, আর মাসের শেষে প্রথম জোড়া মরে গেলো কারণ কোন উকুন ২ মাসের বেশি বাঁচে না। 

তো সেই মাসের শেষে ৩ জোড়া উকুন থাকলো। (সবমিলে ৩)

তুমি যদি এভাবে হিসেব করতেই থাকো, তাহলে দেখবে পরের মাসে ৫ জোড়া উকুন হয়, তার পরের মাসে ৮ জোড়া। 

তো জিনিসটা দাঁড়ায় এরকম ১, ১, ২, ৩, ৫, ৮, ১৩, ২১, ৩৪, ... 

তো ফিবোনাকি খুব মন খারাপ করে বসে বসে উকুনের কামড় খেতেই থাকলো তো খেতেই থাকলো। ন্যাড়া হবার পরদিন বেলতলায় যাওয়ার পর ওর মাথায় একটা বেল পড়েছিল বলে সে আবার চুল সব ফেলে দেয়ার সাহস পেলো না। তো সে বসে বসে কামড় খেয়ে খেয়ে উকুন গুনতে গুনতে হঠাৎ দেখলো, আরি আজিব! আগের দুই মাসের উকুন সংখ্যা যোগ করলেই এই মাসে মাথায় কয়টা উকুন থাকবে সেটা বের হয়ে যায়। তো সে ইয়ে ইয়ে ইয়ে বলে নাচানাচি শুরু করলো, আর ওর নাচ দেখে সবাই ভাবলো সে কি না কি আবিষ্কার করে ফেলেছে - তো সেজন্য সে খুব খুব বিখ্যাত হয়ে গেলো।

আসলে ব্যাপারটা তেমন কঠিন কিছু না, এই মাসে যারা বেঁচে থাকবে, তাদের বয়স যেহেতু ২ এর কম হতে হবে, তাহলে অবশ্যই তাদের জন্ম ঠিক আগের মাসে, অথবা তার আগের মাসের আগের মাসে হতেই হবে তাই না?

তাহলে দেখো, এখানেও একটা রিকার্শন আছে। 

fibonacci( 5 ) = fibonacci( 4 ) + fibonacci( 3 )

তাই না? এটার জেনারেল ফর্ম হচ্ছে

fibonacci( n ) = fibonacci( n-1 ) + fibonacci( n-2 )

তবে, যদি n = 0 অথবা n = 1 হয় তাহলে fibonacci(n) = 1

এটা আমরা সি তে লিখলে সেটা হবে - 

int fibonacci( int n ) {
    if( n == 0 || n == 1 ) return 1;
    else return fibonacci( n-1 ) + fibonacci( n-2 );
}

এখন সমস্যা হলো কি  - যখনই আমার 6 কে ফিবোনাকি মারতে হচ্ছে, তখন সে 5 আর 4 এর ফিবোনাকিকে ডাকছে, আবার 5  ডাকছে 4 আর 3 এর ফিবোনাকিকে। ব্যাপারটা অনেকটা এরকম হচ্ছে। (এখানে ০ মাস বলে কিছু নেই - ১ থেকে ওর গোনা শুরু করেছে)

From Wikipedia, the free encyclopedia

একবার তাকাও, দেখো f(2) কে সেই রকম ভাবে ডাকাডাকি করা হচ্ছে। পাঁচ পাঁচ বার! আবার f(3) কে ডাকা হচ্ছে তিন তিন বার! তো এখানে অনেক অনেক বার ডাকাডাকি করা হচ্ছে, আর কাওকে ডাকাডাকি করলে সে আরো অন্য অনেককে ডাকাডাকি করছে। তো প্রচুর বার ডাকাডাকি করে সবাই খুব ক্লান্ত হয়ে যাচ্ছে, আর আমাদের প্রচুর ভালো ভালো সময় নষ্ট হচ্ছে, যেগুলো দিয়ে আমরা প্রচ্চুর কার্টুন দেখতে পারতাম আর অনেক অনেক গল্পের বই পড়তে পারতাম। তুমি যদি f(10) কে ডাকাডাকি করো তাহলে দেখবে সে f(2) কে ডাকতে ডাকতে মাথাই খারাপ করে ফেলছে। 

তো আমরা একটা কাজ করতে পারি, আমরা যদি মনে রাখি f(3) এর মান কতো, আর সেটা লিখে রাখি, তাহলে যখনই কেউ f(3) কে ডাকবে, সে পাগলের মতো ওর মান জানার জন্য f(2) আর f(1) কে বারবার ডাকাডাকি করবে না। তাই না?

তাহলে আমরা প্রোগ্রামটা এভাবে লিখতে পারি - 

int array[20];
int fibonacci( int n ) {
    if( n == 0 || n == 1 ) return 1;
    else if( array[n] == 0 ) // ami oke ekbaro process kori nai - or khub mon kharap! :(
        array[n] = fibonacci( n-1 ) + fibonacci( n-2 ); // ye! o khushi! :D
   
    return array[n];
}

 এটা আর আগেরটার একটাই পার্থক্য - আমি যেহেতু একবার প্রসেসিং এর পরই array[n] এর মধ্যে লিখে রাখছি fibonacci(n) এর মান - আমার বারবার সেটা প্রসেস করা লাগছে না। আমার সময় বেঁচে যাচ্ছে কার্টুন দেখার জন্য।

এই যে কান্ডটা আমরা এই মাত্র করলাম, এটার একটা গাল ভরা নাম আছে - ডাইনামিক প্রোগ্রামিং। যখন কেউ নতুন ডাইনামিক প্রোগ্রামিং শেখে, সে টানা কয়েকদিন ধেই ধেই করে নাচানাচি করে, আর সবার সাথে ডাইনামিক প্রোগ্রামিং নিয়ে কথা বলতে চায়। তারপর ঘুমাতে গেলে রিকার্শন স্বপ্ন দেখে, আর ঘুমের ঘোরে বিড়বিড় করে, ডাই ডাই-নামি-ক প্রো-প্রো-গ্রামিং! ইয়ে! গুড়ুড় গুড়ুড়!