বন্ধুদের জুটি করার সমস্যা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক এক্সপিডিয়া জিই হেলথকেয়ার গুগল Honeywell জেপি মরগান
ডায়নামিক প্রোগ্রামিং মডুলার গাণিতিক

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

"ফ্রেন্ডস পেয়ারিং প্রব্লেম" তে বলা হয়েছে যে এন বন্ধু রয়েছে। এবং তাদের প্রতিটি অবিবাহিত থাকতে পারে বা একে অপরের সাথে জুড়ি দেওয়া যায়। তবে একবার জুটি তৈরি হয়ে গেলে এই দুই বন্ধু জুটি বেঁধে অংশ নিতে পারবেন না। সুতরাং, আপনার বন্ধুদের মোট জুটি তৈরি করতে বা তারা অবিবাহিত থাকতে পারে তার মোট সংখ্যা খুঁজে বের করতে হবে Aএ

উদাহরণ

3
4

বন্ধুদের জুটি করার সমস্যা
বন্ধুদের যুক্ত করার সমস্যাটির জন্য অ্যাপ্রোচ

পরিবর্তে এটি একটি বড় সমস্যা হিসাবে চিন্তা। প্রথমে ছোট এন এর সমাধান করার চেষ্টা করা যাক, এন = 1 এর জন্য উত্তরটি 1 টি। এন 2 এর জন্য উত্তরটি 2 হয় ither হয় উভয় বন্ধু অবিবাহিত থাকেন বা তারা জুটি বাঁধেন। এন = 3 এর জন্য, তৃতীয় বন্ধুটি অবিবাহিত থাকতে পারে। সুতরাং সেই উত্তরটির জন্য এন = 2 নিয়ে সমস্যার উত্তর হওয়া উচিত কারণ এই সমস্ত ক্ষেত্রে আমাদের তৃতীয় বন্ধু অবিবাহিত থাকতে পারে। এবং জুটি বাঁধার জন্য, এটি বন্ধুদের যে কোনও একটি চয়ন করতে পারে। সুতরাং এন -1 বন্ধুবান্ধব থেকে 1 জন বন্ধু এবং তারপরে অন্যরা কীভাবে জুড়ি / একা থাকতে পারে তার সংখ্যা = (এন -1) * এফ (এন -2)। এখন, আমরা সমস্যার পুনরাবৃত্তির সূত্রটি ভাবতে পারি।

F(N)     =     F(N-1)   +   (N-1)*F(N-2)
                  ^              ^
                  |              |
Nth friend (stays single) (pairs with N-1 friends)

থেকে পুনরাবৃত্তি সূত্র, আমরা দেখতে পাচ্ছি যে F (N) গণনা করার সময় আমরা F (N-2) গণনা করি। এবং তারপরে F (N-1) এর পাশাপাশি, আমরা F (N-2) গণনা করি। সুতরাং পুনঃনির্মাণ মানগুলির পরিবর্তে আমাদের ব্যবহার করা উচিত গতিশীল প্রোগ্রামিং। এখানে আমরা 0 থেকে N পর্যন্ত পুরো F (N) মান সংরক্ষণ করতে পারি তবে এটির প্রয়োজন নেই। যেহেতু F (N) এর মান কেবল F (N-1) এবং F (N-2) এর উপর নির্ভরশীল যা সর্বশেষ 2 টি মান। সুতরাং আমরা কেবল শেষ 2 টি মান সংরক্ষণ করি। কারণ এটি আমাদের স্থান বাঁচাবে।

কোড

বন্ধুদের যুক্ত করার সমস্যায় সি ++ কোড

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

int main()
{
  // number of friends
  int n;cin>>n;

  int last = 2, lastTolast = 1;
  // here last denotes F(N-1) and lastTolast denotes F(N-2)
  // we can also use a dp array but that will only increase space complexity
  // and from the recursive formula we can see that
  // F(N) is dependent only on F(N-1) and F(N-2)
  int current;
  for(int i=3;i<=n;i++){
    current = last + (i-1)*lastTolast;
    lastTolast = last;
    last = current;
  }
  cout<<current<<endl;
}E
4
10

বন্ধুদের যুক্ত করার সমস্যার জন্য জাভা কোড

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// number of friends

    int last = 2, lastTolast = 1;
    // here last denotes F(N-1) and lastTolast denotes F(N-2)
    // we can also use a dp array but that will only increase space complexity
    // and from the recursive formula we can see that
    // F(N) is dependent only on F(N-1) and F(N-2)
    int current;
    for(int i=3;i<=n;i++){
      current = last + (i-1)*lastTolast;
      lastTolast = last;
      last = current;
    }
    System.out.println(current);
  }
}
4
10

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

সময় জটিলতা

চালু), কারণ এটি খুঁজে পেতে আমাদের এন পর্যন্ত একটি লুপ চালাতে হবে। যেহেতু F (N) F (N-1) এবং F (N-2) এর উপর নির্ভরশীল।

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

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