C++-এ নির্দিষ্ট রেঞ্জে ফিবোনাচ্চি সংখ্যা গণনা O(Log n) সময় ও O(1) স্পেসে

আমাদের একটি রেঞ্জ দেওয়া আছে শুরু এবং শেষ সংখ্যাসহ, এবং আমাদের কাজ হল দেওয়া রেঞ্জে থাকা ফিবোনাচ্চি সংখ্যাগুলোর মোট গণনা O(Log n) সময় এবং O(1) স্পেসে করা।

ফিবোনাচ্চি সংখ্যা কী?

ফিবোনাচ্চি সংখ্যাগুলো হল একটি সংখ্যা শৃঙ্খলা যাকে ফিবোনাচ্চি শৃঙ্খলা বলা হয় যেখানে প্রতিটি নতুন সংখ্যা পिछले দুটি সংখ্যার যোগফল।

যেখানে, f(0) = 0 এবং f(1) = 1 অর্থাৎ f(0) এবং f(1)-এর অবস্থান শৃঙ্খলায় নির্দিষ্ট এবং গণনা তৃতীয় সংখ্যা থেকে শুরু হবে।

শৃঙ্খলা গণনার সূত্র −

F_n = F_n-1 + F_n-2

যেখানে, F₀ = 0, F₁ = 1

উদাহরণ

ইনপুট − start = 6 এবং last = 100 আউটপুট − শৃঙ্খলায় ফিবোনাচ্চি সংখ্যার সংখ্যা 6

ব্যাখ্যা − 6 এবং 100-এর মধ্যবর্তী ফিবোনাচ্চি সংখ্যাগুলো: 8, 13, 21, 34, 55, 89 অর্থাৎ মোট গণনা 6।

ইনপুট − start = 0 এবং last = 8 আউটপুট − শৃঙ্খলায় ফিবোনাচ্চি সংখ্যার সংখ্যা 7

ব্যাখ্যা − 0 এবং 8-এর মধ্যবর্তী ফিবোনাচ্চি সংখ্যাগুলো: 0, 1, 1, 2, 3, 5, 8 অর্থাৎ মোট গণনা 7।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

শুরু এবং শেষ সংখ্যা ইনপুট নিয়ে রেঞ্জ তৈরি করুন
fib1 = 0, fib2 = 1, fib3 = 1 ঘোষণা ও আরম্ভ করুন
একটি অস্থায়ী ভেরিয়েবল res ঘোষণা করুন এবং 0 দিয়ে আরম্ভ করুন
while fib1 <= last লুপ শুরু করুন
লুপের ভিতরে, যদি fib1 >= start হয় তবে res 1 বৃদ্ধি করুন
fib1 = fib2, fib2 = fib3, fib3 = fib1 + fib2 সেট করুন
res ফেরত দিন
ফলাফল প্রিন্ট করুন

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

// start থেকে last রেঞ্জে ফিবোনাচ্চি সংখ্যা গণনা
int count_fibonacci(int start, int last) {
    // প্রথম তিনটি ফিবোনাচ্চি সংখ্যা
    int fib1 = 0, fib2 = 1, fib3 = 1;
    // ফিবোনাচ্চি গণনার জন্য res
    int res = 0;
    while (fib1 <= last) {
        if (fib1 >= start) {
            res++;
        }
        fib1 = fib2;
        fib2 = fib3;
        fib3 = fib1 + fib2;
    }
    return res;
}

// main ফাংশন
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