এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যার মান দেওয়া হয়েছে। আমাদের কাজ হল Nth Non Fibonacci Number বের করার জন্য একটি C + + প্রোগ্রাম ব্যবহার করা .
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা থেকে শুরু হয় - F0 এবং F1। F0 এবং F1 এর প্রাথমিক মান যথাক্রমে 0, 1 বা 1, 1 নেওয়া যেতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 5
আউটপুট
10
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল ফিবোনাচি সংখ্যাগুলি খুঁজে বের করা এবং তারপরে প্রথম n সংখ্যাগুলি মুদ্রণ করা যা ফিবোনাচি সংখ্যাগুলিতে উপস্থিত নেই৷
আরেকটি সমাধান হল ফিবোনাচি সংখ্যা সূত্র ব্যবহার করে এবং তারপর পরপর দুটি ফিবোনাচি সংখ্যার মধ্যে ফাঁক যোগ করতে থাকুন। শেষ পর্যন্ত, সমস্ত ফাঁকের যোগফলের মান পছন্দসই আউটপুটে পরিণত হবে। এখানে আমরা ক্র্যাকিংয়ের জন্য বুদ্ধিমান ধারণা ব্যবহার করব।
অ্যালগরিদম
-
তিনটি ভেরিয়েবল তৈরি করুন যা বর্তমান উপাদান, পূর্ববর্তী উপাদান এবং পূর্ববর্তী উপাদানের উপর নজর রাখবে।
-
যদিও নন ফিবোনাচির সংখ্যা নেতিবাচক নয়, ফিবোনাচি সংখ্যার সরল সূত্র ব্যবহার করুন − Fib(n)=Fib(n-1)+Fib(n-2)।
-
n=n+(curr-prev-1) সূত্র ব্যবহার করে নন ফিবোনাচি সংখ্যার গণনা পেতে।
-
-
এখন nম নন ফিবোনাচি সংখ্যা পেতে 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
