2 ভেরিয়েবল ব্যবহার করে ফিবোনাচি ক্রম প্রিন্ট করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক Delhivery ফ্যাক্সেট ফোরকিটস আরোহণ ম্যাক o9 সমাধান Payu
ডায়নামিক প্রোগ্রামিং ফিবানচি ক্রম

সমস্যা বিবৃতি

"2 ভেরিয়েবল ব্যবহার করে ফিবোনাচি সিকোয়েন্স মুদ্রণ করুন" সমস্যাটি জানিয়েছে যে আপনাকে ফিবোনাচি সিকোয়েন্সটি প্রিন্ট করতে হবে তবে কেবল 2 ভেরিয়েবল ব্যবহারের সীমাবদ্ধতা রয়েছে।

উদাহরণ

2 ভেরিয়েবল ব্যবহার করে ফিবোনাচি ক্রম প্রিন্ট করুন

n = 5
0 1 1 2 3 5

ব্যাখ্যা

আউটপুট সিকোয়েন্সটিতে ফিবোনাচি সিরিজের প্রথম পাঁচটি উপাদান রয়েছে।

অভিগমন

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

আমরা ভাবতে পারি গতিশীল প্রোগ্রামিং/ সমস্যার জন্য স্মৃতিচারণ। পদ্ধতির অবশ্যই সময় জটিলতা হ্রাস করবে। ঘনিষ্ঠ সময় জটিলতা রৈখিক সময়ের জটিলতায় হ্রাস পাবে। তবে এই পদ্ধতির জন্য এখনও আমাদের লিনিয়ার স্পেস জটিলতা প্রয়োজন। আমাদের এই স্পেস জটিলতা আরও কমাতে হবে। আমরা কী করতে পারি তা অপ্টিমাইজ করার চেষ্টা করা গতিশীল প্রোগ্রামিং পদ্ধতির।

আমরা যদি পুনরাবৃত্ত সূত্রটি দেখতে পাই, এফ (এন) = এফ (এন -1) + এফ (এন -2)। আমরা কেবল শেষ দুটি ফিবোনাচি সংখ্যার উপর নির্ভরশীল। এইভাবে আমরা কেবলমাত্র বর্তমান দুটি সন্ধানের জন্য শেষ দুটি ফিবোনাচি সংখ্যা সংরক্ষণ করতে পারি এবং এটি ও (1) স্থান জটিলতায় অ্যালগরিদমকে চালিত করে।

কোড

সি ++ কোডটি 2 ভেরিয়েবল ব্যবহার করে ফিবোনাচি সিকোয়েন্স প্রিন্ট করতে হবে

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

2 ভেরিয়েবল ব্যবহার করে ফিবোনাচি সিকোয়েন্স মুদ্রণের জন্য জাভা কোড

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int last = 1, lastToLast = 0;
      if(n>=0)
          System.out.print(lastToLast+" ");
      if(n>=1)
          System.out.print(last+" ");
      for(int i=2;i<=n;i++){
          int cur = last + lastToLast;
          System.out.print(cur+" ");
          lastToLast = last;
          last = cur;
      }
  	}
}
5
0 1 1 2 3 5

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), কারণ আমরা কেবল মুদ্রণের জন্য প্রয়োজনীয় সংখ্যক উপাদানগুলি অতিক্রম করেছি। প্রথমত, আমরা পুনরাবৃত্তি ব্যবহার করে সমস্যাটি সমাধান করার কথা ভেবেছিলাম কিন্তু এটি সময় মত প্রকাশযোগ্য। তারপরে আমরা যখন ব্যবহার করতাম তখন আমাদের সময়ের জটিলতা হ্রাস করেছিলাম গতিশীল প্রোগ্রামিং। যার কারণে আমরা লিনিয়ার সময়ে সমস্যার সমাধান করতে সক্ষম হয়েছি।

স্পেস জটিলতা ity

ও (1),  আমরা স্থির স্থান জটিলতায় সমস্যাটি সমাধান করেছি কারণ আমরা কেবল দুটি ভেরিয়েবল ব্যবহার করেছি।