আমাদের শুরু এবং শেষ সংখ্যা সহ পরিসর দেওয়া হয়েছে এবং কাজটি হল O(লগ n) সময় এবং O(1) স্থানের মধ্যে প্রদত্ত রেঞ্জের মধ্যে উপলব্ধ ফিবোনাচি সংখ্যার মোট গণনা করা।
ফিবোনাচি সংখ্যা কি
ফিবোনাচি সংখ্যা হল ফিবোনাচি সিকোয়েন্স নামে পরিচিত সংখ্যার ক্রম যেখানে প্রতিটি নতুন সংখ্যা শেষ দুটি পূর্ববর্তী সংখ্যার যোগফল।
যেখানে, f(0) =0 এবং f(1) =1 অর্থাৎ f(0) এবং f(1) ক্রমানুসারে নির্দিষ্ট অবস্থান রয়েছে এবং গণনা তৃতীয় সংখ্যা থেকে শুরু হবে৷
ক্রম গণনার জন্য ব্যবহৃত সূত্র হল −
Fn =Fn-1 + Fn-2
কোথায়,
F0 =0, F1 =l
উদাহরণের জন্য
Input − start = 6 and last = 100 Output − Number of fibonacci Numbers in the series are 6
ব্যাখ্যা − 6 এবং 100 এর মধ্যে ফিবোনাচি সংখ্যা হল 8, 13, 21, 34, 55, 89 অর্থাৎ মোট গণনা হল 6
Input − start = 0 and last = 8 Output − Number of fibonacci Numbers in the series are 7
ব্যাখ্যা − 0 এবং 8 এর মধ্যে ফিবোনাচি সংখ্যা হল 0, 1, 1, 2, 3, 5, 8 অর্থাৎ মোট গণনা হল 7
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি পরিসর তৈরি করতে শুরু এবং শেষ সংখ্যাগুলি ইনপুট করুন
-
ঘোষণা করুন এবং শুরু করুন fib1 থেকে 0, fib2 থেকে 1, fib3 থেকে 1
-
একটি অস্থায়ী পরিবর্তনশীল রেস ঘোষণা করুন এবং এটি 0
দিয়ে আরম্ভ করুন -
একটি লুপ শুরু করুন, যখন fib1 শেষের থেকে কম বা সমান হয়
-
লুপের ভিতরে, fib1 স্টার্টের চেয়ে বড় বা সমান কিনা তা পরীক্ষা করুন তারপর রেস 1 দ্বারা বৃদ্ধি করুন
-
fib1 থেকে fib2, fib2 থেকে fib3 এবং fib3-এ fib1 + fib2 সেট করুন
-
রিটার্ন রিটার্ন
-
ফলাফল প্রিন্ট করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// function to count fibonacci numbers in range
// from start to last
int count_fibonacci(int start, int last){
// First three Fibonacci Numbers
int fib1 = 0, fib2 = 1, fib3 = 1;
// res to count the number of fibonacci
int res = 0;
while (fib1 <= last){
if (fib1 >= start){
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// main function
int main(){
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are "
<< count_fibonacci(start, last);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেNumber of fibonacci Numbers in the series are 6
