مشكلة الاقتران بين الأصدقاء - البرمجة الديناميكية

بالنظر إلى عدد n من الأصدقاء، يمكن لكل واحد منهم أن يظل عازبًا أو يمكن أن يقترن بصديق آخر. يمكن إقران كل صديق مرة واحدة فقط. اكتشف العدد الإجمالي للطرق التي يمكن من خلالها للأصدقاء أن يظلوا منفردين أو يمكن أن يكونوا مقترنين.

أمثلة:

  Input :   n = 3   Output :   4   Explanation:   {1} {2} {3} : all single {1} {2 3} : 2 and 3 paired but 1 is single. {1 2} {3} : 1 and 2 are paired but 3 is single. {1 3} {2} : 1 and 3 are paired but 2 is single. Note that {1 2} and {2 1} are considered same.   Mathematical Explanation:   The problem is simplified version of how many ways we can divide n elements into multiple groups. (here group size will be max of 2 elements). In case of n = 3 we have only 2 ways to make a group: 1) all elements are individual(111) 2) a pair and individual (21) In case of n = 4 we have 3 ways to form a group: 1) all elements are individual (1111) 2) 2 individuals and one pair (211) 3) 2 separate pairs (22)

tinytextbf{صيغة رياضية:} newline{frac{n!}{((g_1!)^xtimes (g_2!)^ytimes ... (g_n!)^z)times(x!times y!times...z!)}}spacespacetinytext{ ----- (1)} newline{tinytext{إذا تم تكرار نفس حجم المجموعة xy...z مرات علينا قسمة إجابتنا بالإضافة إلى ذلك على x!y!...z!}} newline{tinytext{الآن لنفكر في حالتنا n=3 وحجم المجموعة الحد الأقصى للحجم 2 والحد الأدنى للحجم 1:}} newline{frac{3!}{(1!)^3times(3!)} space+space frac{3!}{(2!)^1times(1!)^1times(1!)^2}space = 4} newline{text{الآن دعونا نفكر في حالتنا n=4:}} السطر الجديد{فارك{4!}{(1!)^4مرات(4!)} مسافة+ فارك{4!}{(2!)^1مرات(1!)^2مرات(2!)}مسافة + مساحة فارك{4!}{(2!)^2مرات(2!)}مسافة = 10}

الممارسة الموصى بها مشكلة الاقتران بين الأصدقاء جربه!

بالنسبة إلى الشخص n، هناك خياران: 1) يظل الشخص n أعزبًا، ونتكرر بالنسبة إلى f(n - 1)2) يتزاوج الشخص n مع أي من الأشخاص المتبقين n - 1. نحصل على (n - 1) * f(n - 2) لذلك يمكننا كتابة f(n) بشكل متكرر على النحو التالي:f(n) = f(n - 1) + (n - 1) * f(n - 2)

فرز جافا Arraylist

منذ الصيغة العودية المذكورة أعلاه لديها مشاكل فرعية متداخلة يمكننا حلها باستخدام البرمجة الديناميكية.

C++

// C++ program for solution of // friends pairing problem #include    using namespace std; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings(int n) {  int dp[n + 1];  // Filling dp[] in bottom-up manner using  // recursive formula explained above.  for (int i = 0; i <= n; i++) {  if (i <= 2)  dp[i] = i;  else  dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];  }  return dp[n]; } // Driver code int main() {  int n = 4;  cout << countFriendsPairings(n) << endl;  return 0; }

Java

// Java program for solution of // friends pairing problem import java.io.*; class GFG {  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  int dp[] = new int[n + 1];  // Filling dp[] in bottom-up manner using  // recursive formula explained above.  for (int i = 0; i <= n; i++) {  if (i <= 2)  dp[i] = i;  else  dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];  }  return dp[n];  }  // Driver code  public static void main(String[] args)  {  int n = 4;  System.out.println(countFriendsPairings(n));  } } // This code is contributed by vt_m

Python3

# Python program solution of # friends pairing problem # Returns count of ways # n people can remain # single or paired up. def countFriendsPairings(n): dp = [0 for i in range(n + 1)] # Filling dp[] in bottom-up manner using # recursive formula explained above. for i in range(n + 1): if(i <= 2): dp[i] = i else: dp[i] = dp[i - 1] + (i - 1) * dp[i - 2] return dp[n] # Driver code n = 4 print(countFriendsPairings(n)) # This code is contributed # by Soumen Ghosh.

// C# program solution for // friends pairing problem using System; class GFG {  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  int[] dp = new int[n + 1];  // Filling dp[] in bottom-up manner using  // recursive formula explained above.  for (int i = 0; i <= n; i++) {  if (i <= 2)  dp[i] = i;  else  dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];  }  return dp[n];  }  // Driver code  public static void Main()  {  int n = 4;  Console.Write(countFriendsPairings(n));  } } // This code is contributed by nitin mittal.

PHP

 // PHP program solution for  // friends pairing problem // Returns count of ways n people  // can remain single or paired up. function countFriendsPairings($n) { $dp[$n + 1] = 0; // Filling dp[] in bottom-up  // manner using recursive formula  // explained above. for ($i = 0; $i <= $n; $i++) { if ($i <= 2) $dp[$i] = $i; else $dp[$i] = $dp[$i - 1] + ($i - 1) * $dp[$i - 2]; } return $dp[$n]; } // Driver code $n = 4; echo countFriendsPairings($n) ; // This code is contributed  // by nitin mittal. ?>

JavaScript

<script> // Javascript program for solution of // friends pairing problem     // Returns count of ways n people  // can remain single or paired up.  function countFriendsPairings(n)  {  let dp = [];    // Filling dp[] in bottom-up manner using  // recursive formula explained above.  for (let i = 0; i <= n; i++) {  if (i <= 2)  dp[i] = i;  else  dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];  }    return dp[n];  }   // Driver Code    let n = 4;  document.write(countFriendsPairings(n));  </script>

الإخراج

تعقيد الوقت : على)
المساحة المساعدة : على)

نهج آخر: (باستخدام العودية)

C++

// C++ program for solution of friends // pairing problem Using Recursion #include    using namespace std; int dp[1000]; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings(int n) {  if (dp[n] != -1)  return dp[n];  if (n > 2)  return dp[n] = countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2);  else  return dp[n] = n; } // Driver code int main() {  memset(dp -1 sizeof(dp));  int n = 4;  cout << countFriendsPairings(n) << endl;  // this code is contributed by Kushdeep Mittal }

Java

// Java program for solution of friends // pairing problem Using Recursion import java.io.*; class GFG {  static int[] dp = new int[1000];  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  if (dp[n] != -1)  return dp[n];  if (n > 2)  return dp[n] = countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2);  else  return dp[n] = n;  }  // Driver code  public static void main(String[] args)  {  for (int i = 0; i < 1000; i++)  dp[i] = -1;  int n = 4;  System.out.println(countFriendsPairings(n));  } } // This code is contributed by Ita_c.

Python3

# Python3 program for solution of friends  # pairing problem Using Recursion  dp = [-1] * 1000 # Returns count of ways n people  # can remain single or paired up.  def countFriendsPairings(n): global dp if(dp[n] != -1): return dp[n] if(n > 2): dp[n] = (countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2)) return dp[n] else: dp[n] = n return dp[n] # Driver Code n = 4 print(countFriendsPairings(n)) # This code contributed by PrinciRaj1992

// C# program for solution of friends // pairing problem Using Recursion using System; class GFG {  static int[] dp = new int[1000];  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  if (dp[n] != -1)  return dp[n];  if (n > 2)  return dp[n] = countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2);  else  return dp[n] = n;  }  // Driver code  static void Main()  {  for (int i = 0; i < 1000; i++)  dp[i] = -1;  int n = 4;  Console.Write(countFriendsPairings(n));  } } // This code is contributed by DrRoot_

PHP

 // PHP program for solution of friends  // pairing problem Using Recursion  // Returns count of ways n people  // can remain single or paired up.  function countFriendsPairings($n) { $dp = array_fill(0 1000 -1); if($dp[$n] != -1) return $dp[$n]; if($n > 2) { $dp[$n] = countFriendsPairings($n - 1) + ($n - 1) * countFriendsPairings($n - 2); return $dp[$n]; } else { $dp[$n] = $n; return $dp[$n]; } } // Driver Code $n = 4; echo countFriendsPairings($n) // This code is contributed by Ryuga ?>

JavaScript

<script> // Javascript program for solution of friends // pairing problem Using Recursion    let dp = new Array(1000);    // Returns count of ways n people  // can remain single or paired up.  function countFriendsPairings(n)  {  if (dp[n] != -1)  return dp[n];    if (n > 2)  return dp[n] = countFriendsPairings(n - 1)   + (n - 1) * countFriendsPairings(n - 2);  else  return dp[n] = n;  }    // Driver code  for (let i = 0; i < 1000; i++)  dp[i] = -1;  let n = 4;  document.write(countFriendsPairings(n));    // This code is contributed by rag2127   </script>

الإخراج

تعقيد الوقت : على)
المساحة المساعدة : على)

بما أن الصيغة المذكورة أعلاه مشابهة لـ رقم فيبوناتشي يمكننا تحسين المساحة من خلال حل تكراري.

C++

#include    using namespace std; // Returns count of ways n people // can remain single or paired up. int countFriendsPairings(int n) {  int a = 1 b = 2 c = 0;  if (n <= 2) {  return n;  }  for (int i = 3; i <= n; i++) {  c = b + (i - 1) * a;  a = b;  b = c;  }  return c; } // Driver code int main() {  int n = 4;  cout << countFriendsPairings(n);  return 0; } // This code is contributed by mits

Java

import java.io.*; class GFG {  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  int a = 1 b = 2 c = 0;  if (n <= 2) {  return n;  }  for (int i = 3; i <= n; i++) {  c = b + (i - 1) * a;  a = b;  b = c;  }  return c;  }  // Driver code  public static void main(String[] args)  {  int n = 4;  System.out.println(countFriendsPairings(n));  } } // This code is contributed by Ravi Kasha.

Python3

# Returns count of ways n people # can remain single or paired up. def countFriendsPairings(n): a b c = 1 2 0; if (n <= 2): return n; for i in range(3 n + 1): c = b + (i - 1) * a; a = b; b = c; return c; # Driver code n = 4; print(countFriendsPairings(n)); # This code contributed by Rajput-Ji

using System; class GFG {  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  int a = 1 b = 2 c = 0;  if (n <= 2) {  return n;  }  for (int i = 3; i <= n; i++) {  c = b + (i - 1) * a;  a = b;  b = c;  }  return c;  }  // Driver code  public static void Main(String[] args)  {  int n = 4;  Console.WriteLine(countFriendsPairings(n));  } } // This code has been contributed by 29AjayKumar

PHP

 // Returns count of ways n people // can remain single or paired up. function countFriendsPairings($n) { $a = 1; $b = 2; $c = 0; if ($n <= 2) { return $n; } for ($i = 3; $i <= $n; $i++) { $c = $b + ($i - 1) * $a; $a = $b; $b = $c; } return $c; } // Driver code $n = 4; print(countFriendsPairings($n)); // This code is contributed by mits ?>

JavaScript

<script>  // Returns count of ways n people  // can remain single or paired up.  function countFriendsPairings(n)  {  let a = 1 b = 2 c = 0;  if (n <= 2) {  return n;  }  for (let i = 3; i <= n; i++) {  c = b + (i - 1) * a;  a = b;  b = c;  }  return c;  }    // Driver code  let n = 4;  document.write(countFriendsPairings(n));      // This code is contributed by avanitrachhadiya2155 </script>

الإخراج

تعقيد الوقت : على)
المساحة المساعدة : يا(1)

تحويل نوع جافا والصب

نهج آخر: وبما أننا نستطيع حل المشكلة أعلاه باستخدام الرياضيات، فإن الحل أدناه يتم دون استخدام البرمجة الديناميكية.

C++

// C++ soln using mathematical approach #include    using namespace std; void preComputeFact(vector<long long int>& fact int n) {  for(int i = 1; i <= n; i++)  fact.push_back(fact[i - 1] * i); } // Returns count of ways n people // can remain single or paired up. int countFriendsPairings(vector<long long int> fact   int n) {  int ones = n twos = 1 ans = 0;    while (ones >= 0)   {    // pow of 1 will always be one  ans += fact[n] / (twos * fact[ones] *   fact[(n - ones) / 2]);  ones -= 2;  twos *= 2;  }  return ans; } // Driver code int main() {  vector<long long int> fact;  fact.push_back(1);  preComputeFact(fact 100);  int n = 4;  cout << countFriendsPairings(fact n) << endl;  return 0; } // This code is contributed by rajsanghavi9.

Java

// Java soln using mathematical approach import java.util.*; class GFG{ static Vector<Integer> fact; static void preComputeFact( int n) {  for(int i = 1; i <= n; i++)  fact.add(fact.elementAt(i - 1) * i); } // Returns count of ways n people // can remain single or paired up. static int countFriendsPairings(int n) {  int ones = n twos = 1 ans = 0;    while (ones >= 0)   {    // pow of 1 will always be one  ans += fact.elementAt(n) / (twos * fact.elementAt(ones) *   fact.elementAt((n - ones) / 2));  ones -= 2;  twos *= 2;  }  return ans; } // Driver code public static void main(String[] args) {  fact = new Vector<>();  fact.add(1);  preComputeFact(100);  int n = 4;  System.out.print(countFriendsPairings(n) +'n'); } } // This code is contributed by umadevi9616

Python3

# Python3 soln using mathematical approach # factorial array is stored dynamically fact = [1] def preComputeFact(n): for i in range(1 n+1): fact.append((fact[i-1]*i)) # Returns count of ways n people # can remain single or paired up. def countFriendsPairings(n): ones = n twos = 1 ans = 0 while(ones >= 0): # pow of 1 will always be one ans = ans + (fact[n]//(twos*fact[ones]*fact[(n-ones)//2])) ones = ones - 2 twos = twos * 2 return(ans) # Driver Code # pre-compute factorial preComputeFact(1000) n = 4 print(countFriendsPairings(n)) # solution contributed by adarsh_007

// C# program to implement the approach using System; using System.Collections.Generic; public class GFG  {  // initializing the fact list  static List<int> fact = new List<int>();  // computing the next n values of fact  static void preComputeFact(int n)  {  for (int i = 1; i <= n; i++) {  fact.Add(fact[i - 1] * i);  }  }  // Returns count of ways n people  // can remain single or paired up.  static int countFriendsPairings(int n)  {  int ones = n;  int twos = 1;  int ans = 0;  while (ones >= 0) {  // pow of 1 will always be one  ans += fact[n]  / (twos * fact[ones]  * fact[(n - ones) / 2]);  ones -= 2;  twos *= 2;  }  return ans;  }  // driver code  static public void Main()  {  // initializing the first element of fact  fact.Add(1);  preComputeFact(100);  int n = 4;  Console.Write(countFriendsPairings(n));  } } // this code is contributed by phasing17

JavaScript

<script> // Javascript soln using mathematical approach // factorial array is stored dynamically let fact = [1]; function preComputeFact(n) {  for(let i=1;i<n+1;i++)  {  fact.push((fact[i-1]*i));  } } // Returns count of ways n people // can remain single or paired up. function countFriendsPairings(n) {  let ones = n  let twos = 1;  let ans = 0;  while(ones >= 0)  {  // pow of 1 will always be one  ans = ans + Math.floor(fact[n]/(twos*fact[ones]*  fact[(n-ones)/2]))  ones = ones - 2  twos = twos * 2  }  return ans; } // Driver Code // pre-compute factorial preComputeFact(1000) n = 4 document.write(countFriendsPairings(n)) // This code is contributed by ab2127 </script>

الإخراج

تعقيد الوقت: على)
المساحة المساعدة: على)

إنشاء اختبار