Cuente el número de formas de organizar los primeros N números naturales en una línea de modo que el número más a la izquierda sea siempre 1 y no haya dos números consecutivos que tengan una diferencia absoluta mayor que 2 .
Ejemplos:
Entrada: N = 4
Salida: 4
Los únicos arreglos posibles son (1, 2, 3, 4),
(1, 2, 4, 3), (1, 3, 4, 2) y (1, 3, 2, 4).Entrada: N = 6
Salida: 9
Enfoque ingenuo: genere todas las permutaciones y cuente cuántas de ellas satisfacen las condiciones dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of required arrangements int countWays(int n) { // Create a vector vector<int> a; int i = 1; // Store numbers from 1 to n while (i <= n) a.push_back(i++); // To store the count of ways int ways = 0; // Generate all the permutations // using next_permutation in STL do { // Initialize flag to true if first // element is 1 else false bool flag = (a[0] == 1); // Checking if the current permutation // satisfies the given conditions for (int i = 1; i < n; i++) { // If the current permutation is invalid // then set the flag to false if (abs(a[i] - a[i - 1]) > 2) flag = 0; } // If valid arrangement if (flag) ways++; // Generate the next permutation } while (next_permutation(a.begin(), a.end())); return ways; } // Driver code int main() { int n = 6; cout << countWays(n); return 0; }
Java
// Java implementation of the // above approach import java.util.*; class GFG{ // Function to return the count // of required arrangements static int countWays(int n) { // Create a vector Vector<Integer> a = new Vector<>(); int i = 1; // Store numbers from // 1 to n while (i <= n) a.add(i++); // To store the count // of ways int ways = 0; // Generate all the permutations // using next_permutation in STL do { // Initialize flag to true // if first element is 1 // else false boolean flag = (a.get(0) == 1); // Checking if the current // permutation satisfies the // given conditions for (int j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.abs(a.get(j) - a.get(j - 1)) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next permutation } while (next_permutation(a)); return ways; } static boolean next_permutation(Vector<Integer> p) { for (int a = p.size() - 2; a >= 0; --a) if (p.get(a) < p.get(a + 1)) for (int b = p.size() - 1;; --b) if (p.get(b) > p.get(a)) { int t = p.get(a); p.set(a, p.get(b)); p.set(b, t); for (++a, b = p.size() - 1; a < b; ++a, --b) { t = p.get(a); p.set(a, p.get(b)); p.set(b, t); } return true; } return false; } // Driver code public static void main(String[] args) { int n = 6; System.out.print(countWays(n)); } } // This code is contributed by shikhasingrajput
Python3
# Python3 implementation of the approach from itertools import permutations # Function to return the count # of required arrangements def countWays(n): # Create a vector a = [] i = 1 # Store numbers from 1 to n while (i <= n): a.append(i) i += 1 # To store the count of ways ways = 0 # Generate the all permutation for per in list(permutations(a)): # Initialize flag to true if first # element is 1 else false flag = 1 if (per[0] == 1) else 0 # Checking if the current permutation # satisfies the given conditions for i in range(1, n): # If the current permutation is invalid # then set the flag to false if (abs(per[i] - per[i - 1]) > 2): flag = 0 # If valid arrangement if (flag): ways += 1 return ways # Driver code n = 6 print(countWays(n)) # This code is contributed by shivanisinghss2110
C#
// C# implementation of the // above approach using System; using System.Collections.Generic; class GFG{ // Function to return the count // of required arrangements static int countWays(int n) { // Create a vector List<int> a = new List<int>(); int i = 1; // Store numbers from // 1 to n while (i <= n) a.Add(i++); // To store the count // of ways int ways = 0; // Generate all the // permutations using // next_permutation in STL do { // Initialize flag to true // if first element is 1 // else false bool flag = (a[0] == 1); // Checking if the current // permutation satisfies the // given conditions for (int j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.Abs(a[j] - a[j - 1]) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next // permutation } while (next_permutation(a)); return ways; } static bool next_permutation(List<int> p) { for (int a = p.Count - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.Count - 1;; --b) if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Count - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } return false; } // Driver code public static void Main(String[] args) { int n = 6; Console.Write(countWays(n)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the // above approach // Function to return the count // of required arrangements function countWays(n) { // Create a vector let a =[]; let i = 1; // Store numbers from // 1 to n while (i <= n) a.push(i++); // To store the count // of ways let ways = 0; // Generate all the permutations // using next_permutation in STL do { // Initialize flag to true // if first element is 1 // else false let flag = (a[0] == 1); // Checking if the current // permutation satisfies the // given conditions for (let j = 1; j < n; j++) { // If the current permutation // is invalid then set the // flag to false if (Math.abs(a[j] - a[j - 1]) > 2) flag = false; } // If valid arrangement if (flag) ways++; // Generate the next permutation } while (next_permutation(a)); return ways; } function next_permutation(p) { for (let a = p.length - 2;a >= 0; --a) {if (p[a] < p[a + 1]) {for (let b = p.length - 1;; --b) {if (p[b] > p[a]) { let t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false; } // Driver code let n = 6; document.write(countWays(n)); // This code is contributed by patel2127 </script>
9
Enfoque eficiente: este problema se puede resolver mediante programación dinámica .
Un mejor enfoque lineal para este problema se basa en la siguiente observación. Busque la posición de 2. Sea a[i] el número de formas para n = i. Hay tres casos:
- 12_____ – “2” en la segunda posición.
- 1*2____ – “2” en la tercera posición.
1**2___ – “2” en la cuarta posición es imposible porque la única forma posible es (1342), que es igual al caso 3.
1***2__ – “2” en la quinta posición es imposible porque se debe seguir 1 por 3 , 3 por 5 y 2 necesita 4 antes de que se convierta en 13542 , nuevamente como el caso 3. - 1_(i – 2)terms___2 – “2” en la última posición (1357642 y similares)
Para cada caso, las siguientes son las subtareas:
Sumar 1 a cada término de a[i – 1], es decir (1__(i – 1) términos__).
En cuanto a 1_2_____ solo puede haber un 1324___(i – 4) términos____ es decir a[i – 3].
Por lo tanto, la relación de recurrencia será,
a[i] = a[i – 1] + a[i – 3] + 1
Y los casos base serán:
a[0] = 0
a[1] = 1
a[2] = 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of required arrangements int countWays(int n) { // Create the dp array int dp[n + 1]; // Initialize the base cases // as explained above dp[0] = 0; dp[1] = 1; // (12) as the only possibility dp[2] = 1; // Generate answer for greater values for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 3] + 1; } // dp[n] contains the desired answer return dp[n]; } // Driver code int main() { int n = 6; cout << countWays(n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to return the count // of required arrangements static int countWays(int n) { // Create the dp array int []dp = new int[n + 1]; // Initialize the base cases // as explained above dp[0] = 0; dp[1] = 1; // (12) as the only possibility dp[2] = 1; // Generate answer for greater values for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 3] + 1; } // dp[n] contains the desired answer return dp[n]; } // Driver code public static void main(String args[]) { int n = 6; System.out.println(countWays(n)); } } // This code is contributed by 29AjayKumar
Python3
# Python implementation of the approach # Function to return the count # of required arrangements def countWays(n): # Create the dp array dp = [0 for i in range(n + 1)] # Initialize the base cases # as explained above dp[0] = 0 dp[1] = 1 # (12) as the only possibility dp[2] = 1 # Generate answer for greater values for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 3] + 1 # dp[n] contains the desired answer return dp[n] # Driver code n = 6 print(countWays(n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; class GFG { // Function to return the count // of required arrangements static int countWays(int n) { // Create the dp array int []dp = new int[n + 1]; // Initialize the base cases // as explained above dp[0] = 0; dp[1] = 1; // (12) as the only possibility dp[2] = 1; // Generate answer for greater values for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 3] + 1; } // dp[n] contains the desired answer return dp[n]; } // Driver code public static void Main() { int n = 6; Console.WriteLine(countWays(n)); } } // This code is contributed by Code@Mech.
Javascript
<script> // Function to return the count // of required arrangements function countWays( n) { // Create the dp array let dp = new Array (n + 1); // Initialize the base cases // as explained above dp[0] = 0; dp[1] = 1; // (12) as the only possibility dp[2] = 1; // Generate answer for greater values for (let i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 3] + 1; } // dp[n] contains the desired answer return dp[n]; } // Driver code let n = 6; document.write(countWays(n)); // This code is contributed by shivanisinghss2110 </script>
9
Complejidad de tiempo : O(N)
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por mayank77dh9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA