При дадени 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{Математическа формула:} нов ред{frac{n!}{((g_1!)^xtimes (g_2!)^ytimes ... (g_n!)^z)times(x!times y!times...z!)}}spacespacetinytext{ ----- (1)} нов ред{minytext{ако същият размер на групата се повтаря xy...z пъти, трябва да разделим допълнително нашия отговор на x!y!...z!}} нов ред{малък текст{сега нека разгледаме нашия случай n=3 и максимален размер на групата от размер 2 и минимален размер 1:}} нов ред{frac{3!}{(1!)^3times(3!)} интервал+интервал frac{3!}{(2!)^1times(1!)^1times(1!)^2}space = 4} нов ред{текст{сега нека разгледаме нашия случай n=4:}} нов ред{frac{4!}{(1!)^4times(4!)} space+ frac{4!}{(2!)^1times(1!)^2times(2!)}space + space frac{4!}{(2!)^2times(2!)}space = 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)
Тъй като горната рекурсивна формула има припокриващи се подпроблеми можем да го решим с помощта на динамично програмиране.
C++// C++ program for solution of // friends pairing problem #include
// 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
# 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 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. ?> <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>
Изход
10
Времева сложност: O(n)
Помощно пространство: O(n)
Друг подход: (Използване на рекурсия)
C++// C++ program for solution of friends // pairing problem Using Recursion #include
// 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 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 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 ?> <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>
Изход
10
Времева сложност: O(n)
Помощно пространство: O(n)
Тъй като горната формула е подобна на число на фибоначи можем да оптимизираме пространството с итеративно решение.
C++#include
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.
# 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
// 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 ?> <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>
Изход
10
Времева сложност: O(n)
Помощно пространство: О(1)
Друг подход: Тъй като можем да решим горния проблем с помощта на математика, решението по-долу се прави без използване на динамично програмиране.
C++// C++ soln using mathematical approach #include
// 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 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
<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>
Изход
10
Времева сложност: O(n)
Помощно пространство: O(n)