ചങ്ങാതിമാരുടെ ജോടിയാക്കൽ പ്രശ്നം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ബൈ 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)

എസ് ആവർത്തന ഫോർമുല, എഫ് (എൻ) കണക്കുകൂട്ടുന്നതിനിടയിൽ നമ്മൾ എഫ് (എൻ -2) കണക്കാക്കുന്നു. F (N-1) നായി ഞങ്ങൾ F (N-2) കണക്കുകൂട്ടുന്നു. അതിനാൽ മൂല്യങ്ങൾ വീണ്ടും കംപ്യൂട്ട് ചെയ്യുന്നതിനുപകരം നമ്മൾ ഉപയോഗിക്കണം ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. ഇവിടെ, 0 മുതൽ N വരെയുള്ള മുഴുവൻ എഫ് (എൻ) മൂല്യങ്ങളും സംഭരിക്കാൻ കഴിയും, പക്ഷേ അത് ആവശ്യമില്ല. എഫ് (എൻ) ന്റെ മൂല്യം അവസാന 1 മൂല്യങ്ങളായ എഫ് (എൻ -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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം അത് കണ്ടെത്താൻ N വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കണം. F (N) F (N-1), F (N-2) എന്നിവയെ ആശ്രയിച്ചിരിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കണക്കുകൂട്ടലിനായി ഞങ്ങൾ മൂന്ന് വേരിയബിളുകൾ മാത്രമാണ് ഉപയോഗിച്ചത്, അതിനാൽ ആവശ്യമുള്ള ദൂരം സ്ഥിരമായിരുന്നു.