Dado un número N, la tarea es contar todas las combinaciones posibles de pares formados usando elementos adyacentes.
Nota : si un elemento ya existe en un par, no se puede seleccionar en el siguiente par. Por ejemplo: para {1,2,3}: {1,2} y {2,3} no se considerarán una combinación correcta.
Ejemplos:
Input : N = 4 Output : 5 Explanation : If N = 4, the possible combinations are: {1}, {2}, {3}, {4} {1, 2}, {3, 4} {1}, {2, 3}, {4} {1}, {2}, {3, 4} {1, 2}, {3}, {4} Input : N = 5 Output : 8
Enfoque: Dividir el problema en subproblemas más pequeños. Si hay N números, y hay dos casos, o un número está solo o está en un par, si un número está solo, encuentre las formas de emparejar (n-1) números que quedan, o si está en un par , encuentre las formas de emparejar (n-2) números que quedan. Si solo quedan 2 números pueden generar 2 combinaciones solos o en pareja, y si queda un solo número será en singleton, por lo que solo queda 1 combinación.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h> using namespace std; // Function to count the number of ways int ways(int n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } // Driver Code int main() { int n = 5; cout << "Number of ways = " << ways(n); return 0; }
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Function to count the number of ways static int ways(int n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } // Driver Code public static void main (String[] args) { int n = 5; System.out.println("Number of ways = " + ways(n)); } }
Python3
# Python3 code implementation of the above program # Function to count the number of ways def ways(n) : # If there is a single number left # it will form singleton if (n == 1) : return 1; # if there are just 2 numbers left, # they will form a pair if (n == 2) : return 2; else : return ways(n - 1) + ways(n - 2); # Driver Code if __name__ == "__main__" : n = 5; print("Number of ways = ", ways(n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the above code using System; class GFG { // Function to count the number of ways static int ways(int n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } // Driver Code public static void Main() { int n = 5; Console.WriteLine("Number of ways = " + ways(n)); } } // This code is contributed by AnkitRai01
Javascript
<script> // Javascript implementation of the above code // Function to count the number of ways function ways(n) { // If there is a single number left // it will form singleton if (n == 1) { return 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return 2; } else { return ways(n - 1) + ways(n - 2); } } let n = 5; document.write("Number of ways = " + ways(n)); // This code is contributed by suresh07. </script>
Number of ways = 8
Complejidad de tiempo: O(2^N)
Espacio auxiliar: O(N)
Otro enfoque:
Podemos almacenar los valores calculados en una array y reutilizar los epílogos del valor calculado, lo que haría que el programa fuera eficiente.
Implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // vector to store the computed values vector<int> dp; // Function to count the number of ways int ways(int n) { // If there is a single number left // it will form singleton int& res = dp[n]; // return the stored value // if the value is already computed if(res!=-1) return res; // base case if (n == 1) { return res=1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return res=2; } else { return res = ways(n - 1) + ways(n - 2); } } // Driver Code int main() { int n = 5; dp = vector<int>(n + 1,-1); cout << "Number of ways = " << ways(n); return 0; }
Java
// Java implementation of the above approach class GFG { // vector to store the computed values static int[] dp; // Function to count the number of ways static int ways(int n) { // If there is a single number left // it will form singleton int res = dp[n]; // return the stored value // if the value is already computed if (res != -1) return res; // base case if (n == 1) { return res = 1; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { return res = 2; } else { return res = ways(n - 1) + ways(n - 2); } } // Driver Code public static void main(String[] args) { int n = 10; dp = new int[n + 1]; Arrays.fill(dp, -1); System.out.println("Number of ways = " + ways(n)); } } // This code is contributed by jainlovely450
Python3
# Python3 implementation of the above approach # vector to store the computed values dp=[] # Function to count the number of ways def ways(n): # If there is a single number left # it will form singleton res = dp[n] # return the stored value # if the value is already computed if(res!=-1): return res # base case if (n == 1) : res=1 return res # if there are just 2 numbers left, # they will form a pair if (n == 2) : res=2 return res else : res = ways(n - 1) + ways(n - 2) return res # Driver Code if __name__ == '__main__': n = 5 dp = [-1]*(n + 1) print("Number of ways =",ways(n))
Javascript
<script> // JavaScript implementation of the above approach // array to store the computed values let dp = []; // Function to count the number of ways function ways(n) { // If there is a single number left // it will form singleton let res = dp[n]; // return the stored value // if the value is already computed if(res!=-1) return res; // base case if (n == 1) { res = 1; return res; } // if there are just 2 numbers left, // they will form a pair if (n == 2) { res = 2; } else { res = ways(n - 1) + ways(n - 2); } dp[n] = res; return res; } // Driver Code let n = 5; dp = new Array(n+1).fill(-1); document.write(dp); document.write("Number of ways = " + ways(n)); // This code is contributed by shinjanpatra </script>
Number of ways = 8
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por mishrakishan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA