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

ফিবোনাচি সংখ্যা হল এমন সংখ্যা যাতে প্রথম দুটির পর সিরিজের প্রতিটি সংখ্যা পূর্ববর্তী দুটির সমষ্টি। সিরিজটি 1, 1 দিয়ে শুরু হয়। উদাহরণ −

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

আমরা নিচের মত nth তৈরি করার জন্য একটি প্রোগ্রাম লিখতে পারি -

functionfibNaive(n) {
   if (n<= 1) return n;
   returnfibNaive(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) কে প্রায় 4 বার কল করব এবং এটি একই কোড বারবার এবং 4 বার চালাবে। এটি একটি ওভারল্যাপিং সাব সমস্যার একটি কেস। 500-এর জন্য সেই ফাংশনটি চালানোর চেষ্টা করুন৷ আপনি আটকে যাবেন কারণ এই সমস্ত কলগুলিতে অনেক সময় লাগবে৷

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

একবার গণনা করুন এবং পরে পুনরায় ব্যবহার করুন৷

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

letfibStore = {};
functionfibDP(n) {
   if (n<= 1) return n;
if (fibStore[n]) {
   returnfibStore[n];
}
   fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
   returnfibStore[n];
}

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

আপনি −

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

এটি আউটপুট দেবে −

13
21
34
3

এমনকি আপনি বিশাল মানের জন্য এটি পরীক্ষা করতে পারেন।