জাভাস্ক্রিপ্টে ফিবোনাচি সিকোয়েন্স

ফিবোনাচি সংখ্যাগুলো এমন সংখ্যা যাতে সিরিজের প্রথম দুটি সংখ্যার পরের প্রতিটি সংখ্যা তার আগের দুটি সংখ্যার যোগফল। সিরিজটি ১, ১ দিয়ে শুরু হয়। উদাহরণ:

1, 1, 2, 3, 5, 8, 13, 21, 34, ….

আমরা nth ফিবোনাচি সংখ্যা জেনারেট করার একটি প্রোগ্রাম লিখতে পারি নিচের মত:

function fibNaive(n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

এটি নিচের আউটপুট দেবে:

13
21
34
3

আসুন দেখি এই ফাংশন কলগুলো আসলে কীভাবে হচ্ছে:

/**
 * f(5)
 * / \
 * f(4) f(3)
 * / \ / \
 * f(3) f(2) f(2) f(1)
 * / \ .......... 
 * f(2) f(1).......... 
 */

যখন আমরা f(5) কল করি, আমরা f(2)-কে প্রায় ৪ বার কল করব এবং একই কোড ৪ বার চালাবে। এটি একটি ওভারল্যাপিং সাবপ্রব্লেমের কেস। ৫০০ এর জন্য সেই ফাংশনটি চালিয়ে দেখুন। আপনি আটকে যাবেন কারণ এতগুলো কল খুব সময় নেবে।

যখন আমাদের ৫ম ফিবোনাচি সংখ্যা দরকার, আমাদের শুধু নিচের ফিবোনাচি সংখ্যাগুলো একবার দরকার কিন্তু আমরা সেগুলো অনেক বেশি বার কম্পিউট করি। আমরা এই রিডান্ডেন্ট কম্পিউটেশন কমানো যাব যদি আমরা কম্পিউট করা ভ্যালুগুলো কোথাও সংরক্ষণ করি। এটাই ডাইনামিক প্রোগ্রামিংর মূল বিষয়।

একবার কম্পিউট করুন এবং পরে পুনরাবৃত্তি ব্যবহার করুন।

আসুন ফিব ফাংশনের একটি মেমোরাইজড বাস্তবায়ন দেখি।

let fibStore = {};
function fibDP(n) {
    if (n <= 1) return n;
    if (fibStore[n]) {
        return fibStore[n];
    }
    fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
    return fibStore[n];
}

এখন আমরা একটি স্টোর, fibStore ব্যবহার করছি যা আমরা ইতিমধ্যে কম্পিউট করা ভ্যালুগুলো ট্র্যাক রাখে। এটি অতিরিক্ত রিডান্ডেন্ট কম্পিউটেশন কমানো এবং ফাংশনটিকে দক্ষ রাখে।

আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

এটি নিচের আউটপুট দেবে:

13
21
34
3

আপনি বড় ভ্যালুগুলো জন্যও এটি পরীক্ষা করতে পারেন।