የጓደኞች ማጣመር ችግር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን Expedia GE የጤና google Honeywell ጂፒ ሞርጋን
ተለዋዋጭ ፕሮግራም ሞዱል ሂሳብ

የችግሩ መግለጫ

“የጓደኞች ተጣማጅ ችግር” ኤን ጓደኞች እንዳሉ ይናገራል። እና እያንዳንዳቸው ነጠላ ሆነው ሊቆዩ ወይም እርስ በእርስ ሊጣመሩ ይችላሉ ፡፡ ግን አንድ ጥንድ ከተሰራ በኋላ እነዚያ ሁለት ጓደኞች በማጣመር ውስጥ መሳተፍ አይችሉም ፡፡ ስለዚህ ፣ ጓደኞች ተጣምረው ወይም ነጠላ ሆነው ለመቆየት የሚችሉባቸውን አጠቃላይ መንገዶች መፈለግ ያስፈልግዎታል

ለምሳሌ

3
4

የጓደኞች ማጣመር ችግር
የጓደኞች አቀራረብ ችግር የመደመር ችግር

እንደ ትልቅ ችግር ከማሰብ ይልቅ ፡፡ እስቲ በመጀመሪያ ለትንሽ ኤን ለመፍታት እንሞክር ለ N = 1 ፣ መልሱ 1. ለ N = 2 ፣ መልሱ 2. ነው ወይ ሁለቱም ጓደኞቹ ነጠላ ሆነው ይቀሩ ወይም ይጣመራሉ ፡፡ ለ N = 3 ፣ ሦስተኛው ጓደኛ ነጠላ ሆኖ መቆየት ይችላል ፡፡ ስለዚህ ለዚያ መልስ በ N = ለችግሩ መልስ መሆን አለበት ፡፡ በእነዚህ ሁሉ ጉዳዮች ሦስተኛው ጓደኛችን ነጠላ ሆኖ መቆየት ይችላል ፡፡ እና ለማጣመር ከጓደኞች መካከል ማንኛውንም መምረጥ ይችላል ፡፡ ስለዚህ ከ N-2 ጓደኞች 1 ጓደኛን መምረጥ እና ከዚያ ሌሎች ሊያጣምሩ / ነጠላ ሆነው የሚቆዩባቸው መንገዶች ብዛት = (N-1) * F (N-1)። አሁን ፣ ለችግሩ ዳግመኛ ስለማስቀመጫ ቀመር ማሰብ እንችላለን ፡፡

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

ከ ዘንድ recursive ቀመር፣ F (N) ን በምንሰላበት ጊዜ F (N-2) ን እንደምናሰላ ማየት እንችላለን ፡፡ እና ከዚያ ለ F (N-1) እንዲሁ F (N-2) ን እናሰላለን ፡፡ ስለዚህ እሴቶችን ከመቁጠር ይልቅ መጠቀም አለብን ተለዋዋጭ ፕሮግራም. እዚህ ፣ አጠቃላይ የ F (N) እሴቶችን ከ 0 እስከ 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እሱን ለማግኘት እስከ ኤን ድረስ አንድ ዙር ማሄድ አለብን ፡፡ F (N) በ F (N-1) እና F (N-2) ላይ ጥገኛ ስለሆነ ፡፡

የቦታ ውስብስብነት

ኦ (1) ፣ እኛ ለማስላት ሶስት ተለዋዋጮችን ብቻ እንጠቀም ነበር እናም ስለሆነም የሚፈለገው ክፍተት ቋሚ ነበር።