এই সমস্যাতে, আমাদের একটি ইন্টিজার N দেওয়া আছে। আমাদের কাজ হল C++ প্রোগ্রাম দিয়ে Nth নন-ফিবোনাচি সংখ্যা বের করা।
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা F0 এবং F1 থেকে শুরু হয়। F0 এবং F1-এর প্রাথমিক মান ০, ১ বা ১, ১ নেওয়া যেতে পারে।
উদাহরণ দেখি:
ইনপুট
N = 5
আউটপুট
10
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল ফিবোনাচি সংখ্যাগুলো বের করে তারপর প্রথম n সংখ্যা প্রিন্ট করা যেগুলো ফিবোনাচি সংখ্যা নয়।
আরেকটি পদ্ধতি হল ফিবোনাচি সংখ্যা ফর্মুলা ব্যবহার করে দুটি ফিবোনাচি সংখ্যার মধ্যবর্তী গ্যাপ যোগ করতে থাকা। শেষে সব গ্যাপের যোগফল আমাদের আউটপুট দেবে। এখানে আমরা বুদ্ধিমানের মতো আইডিয়া ব্যবহার করব।
অ্যালগরিদম
তিনটি ভেরিয়েবল তৈরি করুন যা করেন্ট এলিমেন্ট, প্রিভিয়াস এলিমেন্ট এবং তারও প্রিভিয়াস এলিমেন্ট ট্র্যাক করবে।
নন-ফিবোনাচি কাউন্ট নন-নেগেটিভ থাকতে দিয়ে ফিবোনাচি সংখ্যার সহজ ফর্মুলা ব্যবহার করুন - Fib(n)=Fib(n-1)+Fib(n-2)।
নন-ফিবোনাচি সংখ্যার কাউন্ট পেতে n=n+(curr-prev-1) ফর্মুলা ব্যবহার করুন।
এখন nth নন-ফিবোনাচি সংখ্যা পেতে n থেকে প্রিভিয়াস সংখ্যা বিয়োগ করুন।
উদাহরণ
#include<iostream> using namespace std; int findNthNonFiboNumber(int n){ int lastLastVal = 1, lastVal = 2, currVal = 3; while (n > 0){ lastLastVal = lastVal; lastVal = currVal; currVal = lastLastVal + lastVal; n = n - (currVal - lastVal - 1); } n = n + (currVal - lastVal - 1); return (lastVal + n); } int main(){ int n = 7; cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n); return 0; }
আউটপুট
Nth non fibonacci number is 12
