ਦੋਸਤ ਜੋੜੀ ਬਣਾਉਣ ਵਿੱਚ ਸਮੱਸਿਆ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਇਕਸਪੀਡੀਆ GE ਹੈਲਥਕੇਅਰ ਗੂਗਲ ਹਨੀਵੈੱਲ JP Morgan
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਮਾਡਯੂਲਰ ਗਣਿਤ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ  

“ਦੋਸਤ ਜੋੜਨ ਦੀ ਸਮੱਸਿਆ” ਕਹਿੰਦੀ ਹੈ ਕਿ ਇੱਥੇ ਦੋਸਤ ਹਨ। ਅਤੇ ਹਰ ਇਕ ਇਕੱਲੇ ਰਹਿ ਸਕਦੇ ਹਨ ਜਾਂ ਇਕ ਦੂਜੇ ਨਾਲ ਜੋੜੀ ਬਣਾ ਸਕਦੇ ਹਨ. ਪਰ ਇਕ ਵਾਰ ਜੋੜੀ ਬਣ ਜਾਣ ਤੇ, ਉਹ ਦੋਵੇਂ ਦੋਸਤ ਜੋੜੀ ਬਣਾਉਣ ਵਿਚ ਹਿੱਸਾ ਨਹੀਂ ਲੈ ਸਕਦੇ. ਇਸ ਲਈ, ਤੁਹਾਨੂੰ ਕੁੱਲ ਤਰੀਕਿਆਂ ਨੂੰ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜਿਸ ਵਿਚ ਦੋਸਤਾਂ ਨੂੰ ਜੋੜਿਆ ਜਾ ਸਕਦਾ ਹੈ ਜਾਂ ਉਹ ਇਕੱਲੇ ਰਹਿ ਸਕਦੇ ਹਨ. ਏ

ਉਦਾਹਰਨ  

3
4

ਦੋਸਤ ਜੋੜੀ ਬਣਾਉਣ ਵਿੱਚ ਸਮੱਸਿਆਪਿੰਨ
ਦੋਸਤਾਂ ਦੀ ਜੋੜੀ ਬਣਾਉਣ ਦੀ ਸਮੱਸਿਆ ਲਈ ਪਹੁੰਚ  

ਇਸ ਦੀ ਬਜਾਏ ਇਸ ਬਾਰੇ ਸੋਚਣਾ ਇਕ ਵੱਡੀ ਸਮੱਸਿਆ ਹੈ. ਆਓ ਪਹਿਲਾਂ ਛੋਟੇ ਐਨ ਲਈ ਹੱਲ ਕਰਨ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰੀਏ. ਐਨ ਲਈ N = 1 ਲਈ, ਜਾਂ ਤਾਂ ਤੀਜਾ ਦੋਸਤ ਕੁਆਰੇ ਰਹਿ ਸਕਦਾ ਹੈ. ਇਸ ਲਈ ਇਸ ਦਾ ਉੱਤਰ N = 1 ਦੀ ਸਮੱਸਿਆ ਦਾ ਉੱਤਰ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿਉਂਕਿ ਉਨ੍ਹਾਂ ਸਾਰੇ ਮਾਮਲਿਆਂ ਵਿੱਚ ਸਾਡਾ ਤੀਜਾ ਦੋਸਤ ਕੁਆਰੇ ਰਹਿ ਸਕਦਾ ਹੈ. ਅਤੇ ਜੋੜੀ ਬਣਾਉਣ ਲਈ, ਇਹ ਕਿਸੇ ਵੀ ਦੋਸਤ ਨੂੰ ਚੁਣ ਸਕਦਾ ਹੈ. ਇਸ ਲਈ ਐਨ -2 ਦੋਸਤਾਂ ਵਿੱਚੋਂ 2 ਦੋਸਤ ਚੁਣਨਾ ਅਤੇ ਫਿਰ ਉਹ ਤਰੀਕਿਆਂ ਦੀ ਗਿਣਤੀ ਵਿੱਚ ਜਿਸ ਨਾਲ ਦੂਸਰੇ ਇਕੱਠੇ ਰਹਿ ਸਕਦੇ ਹਨ / ਰਹਿ ​​ਸਕਦੇ ਹਨ = (ਐਨ -3) * ਐੱਫ (ਐਨ -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 ਵੈਲਯੂਜ ਨੂੰ ਸਟੋਰ ਕਰਦੇ ਰਹਾਂਗੇ. ਜਿਸ ਨਾਲ ਸਾਡੀ ਜਗ੍ਹਾ ਬਚੇਗੀ.

ਇਹ ਵੀ ਵੇਖੋ
ਮੋਸਰ-ਡੀ ਬਰੂਜਿਨ ਸੀਕੁਏਂਸ

ਕੋਡ  

ਦੋਸਤਾਂ ਦੀ ਜੋੜੀ ਬਣਾਉਣ ਦੀ ਸਮੱਸਿਆ ਲਈ C ++ ਕੋਡ

#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), ਅਸੀਂ ਗਣਨਾ ਲਈ ਸਿਰਫ ਤਿੰਨ ਵੇਰੀਏਬਲ ਵਰਤੇ ਹਨ ਅਤੇ ਇਸ ਲਈ ਲੋੜੀਂਦੀ ਥਾਂ ਨਿਰੰਤਰ ਸੀ.