நண்பர்கள் இணைத்தல் சிக்கல்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் Expedia GE ஹெல்த்கேர் கூகிள் ஹனிவெல் ஜேபி மோர்கன்
டைனமிக் புரோகிராமிங் மட்டு எண்கணிதம்

சிக்கல் அறிக்கை

N நண்பர்கள் இருப்பதாக “நண்பர்கள் இணைத்தல் சிக்கல்” கூறுகிறது. மேலும் அவை ஒவ்வொன்றும் ஒற்றுமையாக இருக்கலாம் அல்லது ஒருவருக்கொருவர் ஜோடியாக இருக்கலாம். ஆனால் ஒரு ஜோடி செய்யப்பட்டவுடன், அந்த இரண்டு நண்பர்களும் இணைப்பதில் பங்கேற்க முடியாது. எனவே, நண்பர்களை இணைக்கக்கூடிய அல்லது அவர்கள் ஒற்றுமையாக இருக்கக்கூடிய மொத்த வழிகளின் எண்ணிக்கையை நீங்கள் கண்டுபிடிக்க வேண்டும்

உதாரணமாக

3
4

நண்பர்கள் இணைத்தல் சிக்கல்
நண்பர்கள் இணைத்தல் சிக்கலுக்கான அணுகுமுறை

அதைப் பற்றி ஒரு பெரிய பிரச்சினையாக நினைப்பதற்கு பதிலாக. முதலில் சிறிய N ஐ தீர்க்க முயற்சிப்போம். N = 1 க்கு, பதில் 1. N = 2 க்கு, பதில் 2. ஒன்று. நண்பர்கள் இருவரும் ஒற்றைக்காரி அல்லது அவர்கள் ஜோடி. N = 3 க்கு, மூன்றாவது நண்பர் தனிமையில் இருக்க முடியும். எனவே அந்த பதில் N = 2 இன் சிக்கலுக்கு விடையாக இருக்க வேண்டும். அந்த எல்லா சந்தர்ப்பங்களிலும் எங்கள் மூன்றாவது நண்பர் தனிமையில் இருக்க முடியும். இணைப்பதற்கு, இது எந்த நண்பர்களையும் தேர்வு செய்யலாம். எனவே N-1 நண்பர்களிடமிருந்து 1 நண்பரைத் தேர்ந்தெடுத்து, மற்றவர்கள் ஒற்றை / (N-1) * F (N-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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனென்றால் அதைக் கண்டுபிடிக்க N வரை ஒரு சுழற்சியை இயக்க வேண்டும். F (N) F (N-1) மற்றும் F (N-2) ஆகியவற்றைப் பொறுத்தது என்பதால்.

விண்வெளி சிக்கலானது

ஓ (1), கணக்கீட்டிற்கு நாங்கள் மூன்று மாறிகள் மட்டுமே பயன்படுத்தினோம், இதனால் தேவையான இடைவெளி நிலையானது.