Turėdami n draugų, kiekvienas iš jų gali likti vienišas arba gali būti suporuotas su kitu draugu. Kiekvienas draugas gali būti suporuotas tik vieną kartą. Sužinokite, kiek būdų draugai gali likti vieniši arba gali būti suporuoti.
Pavyzdžiai:
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{Matematinė formulė:} nauja eilutė{frac{n!}{((g_1!)^xtimes (g_2!)^times ... (g_n!)^z)times(x!times y!times...z!)}}spacespacetinytext{ ----- (1)} nauja eilute{tinytext kartojamas x!y!...z!}} nauja eilute{tinytext{dabar apsvarstykite mūsų atvejį n=3 ir grupės dydį iki 2 dydžio ir minimalaus dydžio 1:}} naują eilutę{frac{3!}{(1!)^3times(3!)} tarpas+tarpas frac{3!}{(2!)^1times(1!)^1times(1!)^1times(1) apsvarstykite mūsų atvejį{1!nowspace n=4:}} nauja eilute{frac{4!}{(1!)^4times(4!)} tarpas+ frac{4!}{(2!)^1times(1!)^2times(2!)}tarpas + tarpas frac
Rekomenduojama praktika Draugų poravimo problema Išbandykite!
N-tam asmeniui yra du pasirinkimai: 1) n-asis asmuo lieka vienas, kartojame f(n - 1)2) n-asis asmuo susiporuoja su bet kuriuo iš likusių n - 1 asmenų. Gauname (n - 1) * f(n - 2) Todėl galime rekursyviai parašyti f(n) kaip:f(n) = f(n - 1) + (n - 1) * f(n - 2)
Kadangi aukščiau pateikta rekursinė formulė turi persidengiančios subproblemos galime tai išspręsti naudodami dinaminį programavimą.
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>
Išvestis
10
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(n)
Kitas požiūris: (Naudojama rekursija)
gigabaitas vs megabaitasC++
// 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>
Išvestis
10
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(n)
Kadangi aukščiau pateikta formulė yra panaši į Fibonačio skaičius galime optimizuoti erdvę iteraciniu sprendimu.
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>
Išvestis
10
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)
Kitas požiūris: Kadangi aukščiau pateiktą problemą galime išspręsti naudodami matematiką, toliau pateiktas sprendimas yra atliktas nenaudojant dinaminio programavimo.
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>
Išvestis
10
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(n)