Dado un número entero N , la tarea es encontrar el número mínimo de operaciones necesarias para obtener el número N a partir de 1 . A continuación se muestran las operaciones:
- Suma 1 al número actual.
- Multiplica el número actual por 2.
- Multiplica el número actual por 3.
Imprime el número mínimo de operaciones requeridas y la secuencia correspondiente para obtener N .
Ejemplos:
Entrada: N = 3
Salida:
1
1 3
Explicación:
Operación 1: Multiplica 1 * 3 = 3.
Por lo tanto, solo se requiere 1 operación.Entrada: N = 5
Salida:
3
1 2 4 5
Explicación:
Las operaciones mínimas requeridas son las siguientes:
1 * 2 -> 2
2 * 2 -> 4
4 + 1 -> 5
Enfoque recursivo: genera recursivamente todas las combinaciones posibles para reducir N a 1 y calcular el número de operaciones necesarias. Finalmente, después de agotar todas las combinaciones posibles, imprima la secuencia que requirió el mínimo número de operaciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; vector<int> find_sequence(int n) { // Base Case if (n == 1) return {1, -1}; // Recursive Call for n-1 auto arr = find_sequence(n - 1); vector<int> ans = {arr[0] + 1, n - 1}; // Check if n is divisible by 2 if (n % 2 == 0) { vector<int> div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) ans = {div_by_2[0] + 1, n / 2}; } // Check if n is divisible by 3 if (n % 3 == 0) { vector<int> div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) vector<int> ans = {div_by_3[0] + 1, n / 3}; } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution vector<int> find_solution(int n) { auto a = find_sequence(n); // Print the length cout << a[0] << endl; vector<int> sequence; sequence.push_back(n); //Exit condition for loop = -1 //when n has reached 1 while (a[1] != -1) { sequence.push_back(a[1]); auto arr = find_sequence(a[1]); a[1] = arr[1]; } // Return the sequence // in reverse order reverse(sequence.begin(), sequence.end()); return sequence; } // Driver Code int main() { // Given N int n = 5; // Function call auto i = find_solution(n); for(int j : i) cout << j << " "; } // This code is contributed by mohit kumar 29
Java
// Java program to implement // the above approach import java.util.*; import java.util.Collections; import java.util.Vector; //Vector<Integer> v = new Vector<Integer>(n); class GFG{ static Vector<Integer> find_sequence(int n) { Vector<Integer> temp = new Vector<Integer>(); temp.add(1); temp.add(-1); // Base Case if (n == 1) return temp; // Recursive Call for n-1 Vector<Integer> arr = find_sequence(n - 1); Vector<Integer> ans = new Vector<Integer>(n); ans.add(arr.get(0) + 1); ans.add(n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { Vector<Integer> div_by_2 = find_sequence(n / 2); if (div_by_2.get(0) < ans.get(0)) { ans.clear(); ans.add(div_by_2.get(0) + 1); ans.add(n / 2); } } // Check if n is divisible by 3 if (n % 3 == 0) { Vector<Integer> div_by_3 = find_sequence(n / 3); if (div_by_3.get(0) < ans.get(0)) { ans.clear(); ans.add(div_by_3.get(0) + 1); ans.add(n / 3); } } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution static Vector<Integer> find_solution(int n) { Vector<Integer> a = find_sequence(n); // Print the length System.out.println(a.get(0)); Vector<Integer> sequence = new Vector<Integer>(); sequence.add(n); // Exit condition for loop = -1 // when n has reached 1 while (a.get(1) != -1) { sequence.add(a.get(1)); Vector<Integer> arr = find_sequence(a.get(1)); a.set(1, arr.get(1)); } // Return the sequence // in reverse order Collections.reverse(sequence); return sequence; } // Driver Code public static void main(String args[]) { // Given N int n = 5; // Function call Vector<Integer> res = find_solution(n); for(int i = 0; i < res.size(); i++) { System.out.print(res.get(i) + " "); } } } // This code is contributed by Surendra_Gangwar
Python3
# Python3 program to implement # the above approach def find_sequence(n): # Base Case if n == 1: return 1, -1 # Recursive Call for n-1 ans = (find_sequence(n - 1)[0] + 1, n - 1) # Check if n is divisible by 2 if n % 2 == 0: div_by_2 = find_sequence(n // 2) if div_by_2[0] < ans[0]: ans = (div_by_2[0] + 1, n // 2) # Check if n is divisible by 3 if n % 3 == 0: div_by_3 = find_sequence(n // 3) if div_by_3[0] < ans[0]: ans = (div_by_3[0] + 1, n // 3) # Returns a tuple (a, b), where # a: Minimum steps to obtain x from 1 # b: Previous number return ans # Function that find the optimal # solution def find_solution(n): a, b = find_sequence(n) # Print the length print(a) sequence = [] sequence.append(n) # Exit condition for loop = -1 # when n has reached 1 while b != -1: sequence.append(b) _, b = find_sequence(b) # Return the sequence # in reverse order return sequence[::-1] # Driver Code # Given N n = 5 # Function Call print(*find_solution(n))
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ static List<int> find_sequence(int n) { List<int> temp = new List<int>(); temp.Add(1); temp.Add(-1); // Base Case if (n == 1) return temp; // Recursive Call for n-1 List<int> arr = find_sequence(n - 1); List<int> ans = new List<int>(n); ans.Add(arr[0] + 1); ans.Add(n - 1); // Check if n is divisible by 2 if (n % 2 == 0) { List<int> div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) { ans.Clear(); ans.Add(div_by_2[0] + 1); ans.Add(n / 2); } } // Check if n is divisible // by 3 if (n % 3 == 0) { List<int> div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) { ans.Clear(); ans.Add(div_by_3[0] + 1); ans.Add(n / 3); } } // Returns a tuple (a, b), where // a: Minimum steps to obtain x // from 1 b: Previous number return ans; } // Function that find the optimal // solution static List<int> find_solution(int n) { List<int> a = find_sequence(n); // Print the length Console.WriteLine(a[0]); List<int> sequence = new List<int>(); sequence.Add(n); // Exit condition for loop = -1 // when n has reached 1 while (a[1] != -1) { sequence.Add(a[1]); List<int> arr = find_sequence(a[1]); a.Insert(1, arr[1]); } // Return the sequence // in reverse order sequence.Reverse(); return sequence; } // Driver Code public static void Main(String []args) { // Given N int n = 5; // Function call List<int> res = find_solution(n); for(int i = 0; i < res.Count; i++) { Console.Write(res[i] + " "); } } } // This code is contributed by shikhasingrajput
Javascript
<script> // JavaScript program to implement // the above approach function find_sequence(n) { // Base Case if (n == 1) return [1, -1]; // Recursive Call for n-1 var arr = find_sequence(n - 1); var ans = [arr[0] + 1, n - 1]; // Check if n is divisible by 2 if (n % 2 == 0) { var div_by_2 = find_sequence(n / 2); if (div_by_2[0] < ans[0]) ans = [div_by_2[0] + 1, n / 2]; } // Check if n is divisible by 3 if (n % 3 == 0) { var div_by_3 = find_sequence(n / 3); if (div_by_3[0] < ans[0]) var ans = [div_by_3[0] + 1, n / 3]; } // Returns a tuple (a, b), where // a: Minimum steps to obtain x from 1 // b: Previous number return ans; } // Function that find the optimal // solution function find_solution(n) { var a = find_sequence(n); // Print the length document.write( a[0] + "<br>"); var sequence = []; sequence.push(n); //Exit condition for loop = -1 //when n has reached 1 while (a[1] != -1) { sequence.push(a[1]); var arr = find_sequence(a[1]); a[1] = arr[1]; } // Return the sequence // in reverse order sequence.reverse(); return sequence; } // Driver Code // Given N var n = 5; // Function call var i = find_solution(n); i.forEach(j => { document.write(j + " "); }); </script>
4 1 2 4 5
Complejidad de tiempo: T(N) = T(N-1) + T(N/2) + T(N/3), donde N es un número entero. Este algoritmo da como resultado una complejidad de tiempo exponencial.
Espacio Auxiliar: O(1)
Recursión con enfoque de memorización : el enfoque anterior se puede optimizar memorizando los subproblemas superpuestos.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 program to implement # the above approach # Function to find the sequence # with given operations def find_sequence(n, map): # Base Case if n == 1: return 1, -1 # Check if the subproblem # is already computed or not if n in map: return map[n] # Recursive Call for n-1 ans = (find_sequence(n - 1, map)[0]\ + 1, n - 1) # Check if n is divisible by 2 if n % 2 == 0: div_by_2 = find_sequence(n // 2, map) if div_by_2[0] < ans[0]: ans = (div_by_2[0] + 1, n // 2) # Check if n is divisible by 3 if n % 3 == 0: div_by_3 = find_sequence(n // 3, map) if div_by_3[0] < ans[0]: ans = (div_by_3[0] + 1, n // 3) # Memoize map[n] = ans # Returns a tuple (a, b), where # a: Minimum steps to obtain x from 1 # b: Previous state return ans # Function to check if a sequence can # be obtained with given operations def find_solution(n): # Stores the computed # subproblems map = {} a, b = find_sequence(n, map) # Return a sequence in # reverse order print(a) sequence = [] sequence.append(n) # If n has reached 1 while b != -1: sequence.append(b) _, b = find_sequence(b, map) # Return sequence in reverse order return sequence[::-1] # Driver Code # Given N n = 5 # Function Call print(*find_solution(n))
4 1 2 4 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque de programación dinámica iterativa : el enfoque anterior se puede optimizar aún más mediante el uso de un enfoque de DP iterativo. Siga los pasos a continuación para resolver el problema:
- Cree una array dp[] para almacenar la longitud mínima de secuencia que se requiere para calcular de 1 a N mediante las tres operaciones disponibles.
- Una vez que se calcula la array dp[], obtenga la secuencia recorriendo la array dp[] de N a 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to generate // the minimum sequence void find_sequence(int n) { // Stores the values for the // minimum length of sequences int dp[n + 1]; memset(dp, 0, sizeof(dp)); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array vector<int> sequence; while (n >= 1) { // Append n to the sequence sequence.push_back(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[(int)floor(n / 2)] == dp[n] - 1) { n = (int)floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[(int)floor(n / 3)] == dp[n] - 1) { n = (int)floor(n / 3); } } // Print the sequence // in reverse order reverse(sequence.begin(), sequence.end()); // Print the length of // the minimal sequence cout << sequence.size() << endl; for(int i = 0; i < sequence.size(); i++) { cout << sequence[i] << " "; } } // Driver code int main() { // Given Number N int n = 5; // Function Call find_sequence(n); return 0; } // This code is contributed by divyeshrabadiya07
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to generate // the minimum sequence public static void find_sequence(int n) { // Stores the values for the // minimum length of sequences int[] dp = new int[n + 1]; Arrays.fill(dp, 0); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array List<Integer> sequence = new ArrayList<Integer>(); while (n >= 1) { // Append n to the sequence sequence.add(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[(int)Math.floor(n / 2)] == dp[n] - 1) { n = (int)Math.floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[(int)Math.floor(n / 3)] == dp[n] - 1) { n = (int)Math.floor(n / 3); } } // Print the sequence // in reverse order Collections.reverse(sequence); // Print the length of // the minimal sequence System.out.println(sequence.size()); for(int i = 0; i < sequence.size(); i++) { System.out.print(sequence.get(i) + " "); } } // Driver Code public static void main (String[] args) { // Given Number N int n = 5; // Function Call find_sequence(n); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to implement # the above approach # Function to generate # the minimum sequence def find_sequence(n): # Stores the values for the # minimum length of sequences dp = [0 for _ in range(n + 1)] # Base Case dp[1] = 1 # Loop to build up the dp[] # array from 1 to n for i in range(1, n + 1): if dp[i] != 0: # If i + 1 is within limits if i + 1 < n + 1 and (dp[i + 1] == 0 \ or dp[i + 1] > dp[i] + 1): # Update the state of i + 1 # in dp[] array to minimum dp[i + 1] = dp[i] + 1 # If i * 2 is within limits if i * 2 < n + 1 and (dp[i * 2] == 0 \ or dp[i * 2] > dp[i] + 1): # Update the state of i * 2 # in dp[] array to minimum dp[i * 2] = dp[i] + 1 # If i * 3 is within limits if i * 3 < n + 1 and (dp[i * 3] == 0 \ or dp[i * 3] > dp[i] + 1): # Update the state of i * 3 # in dp[] array to minimum dp[i * 3] = dp[i] + 1 # Generate the sequence by # traversing the array sequence = [] while n >= 1: # Append n to the sequence sequence.append(n) # If the value of n in dp # is obtained from n - 1: if dp[n - 1] == dp[n] - 1: n = n - 1 # If the value of n in dp[] # is obtained from n / 2: elif n % 2 == 0 \ and dp[n // 2] == dp[n] - 1: n = n // 2 # If the value of n in dp[] # is obtained from n / 3: elif n % 3 == 0 \ and dp[n // 3] == dp[n] - 1: n = n // 3 # Return the sequence # in reverse order return sequence[::-1] # Driver Code # Given Number N n = 5 # Function Call sequence = find_sequence(n) # Print the length of # the minimal sequence print(len(sequence)) # Print the sequence print(*sequence)
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to generate // the minimum sequence public static void find_sequence(int n) { // Stores the values for the // minimum length of sequences int[] dp = new int[n + 1]; Array.Fill(dp, 0); // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(int i = 1; i < n + 1; i++) { if(dp[i] != 0) { // If i + 1 is within limits if(i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if(i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if(i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array List<int> sequence = new List<int>(); while(n >= 1) { // Append n to the sequence sequence.Add(n); // If the value of n in dp // is obtained from n - 1: if(dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if(n % 2 == 0 && dp[(int)Math.Floor((decimal)n / 2)] == dp[n] - 1) { n = (int)Math.Floor((decimal)n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if(n % 3 == 0 && dp[(int)Math.Floor((decimal)n / 3)] == dp[n] - 1) { n = (int)Math.Floor((decimal)n / 3); } } // Print the sequence // in reverse order sequence.Reverse(); // Print the length of // the minimal sequence Console.WriteLine(sequence.Count); for(int i = 0; i < sequence.Count; i++) { Console.Write(sequence[i] + " "); } } // Driver Code static public void Main () { // Given Number N int n = 5; // Function Call find_sequence(n); } } // This code is contributed by rag2127
Javascript
<script> // Javascript program to implement // the above approach // Function to generate // the minimum sequence function find_sequence(n) { // Stores the values for the // minimum length of sequences let dp = new Array(n + 1); for(let i=0;i<n+1;i++) { dp[i]=0; } // Base Case dp[1] = 1; // Loop to build up the dp[] // array from 1 to n for(let i = 1; i < n + 1; i++) { if (dp[i] != 0) { // If i + 1 is within limits if (i + 1 < n + 1 && (dp[i + 1] == 0 || dp[i + 1] > dp[i] + 1)) { // Update the state of i + 1 // in dp[] array to minimum dp[i + 1] = dp[i] + 1; } // If i * 2 is within limits if (i * 2 < n + 1 && (dp[i * 2] == 0 || dp[i * 2] > dp[i] + 1)) { // Update the state of i * 2 // in dp[] array to minimum dp[i * 2] = dp[i] + 1; } // If i * 3 is within limits if (i * 3 < n + 1 && (dp[i * 3] == 0 || dp[i * 3] > dp[i] + 1)) { // Update the state of i * 3 // in dp[] array to minimum dp[i * 3] = dp[i] + 1; } } } // Generate the sequence by // traversing the array let sequence = []; while (n >= 1) { // Append n to the sequence sequence.push(n); // If the value of n in dp // is obtained from n - 1: if (dp[n - 1] == dp[n] - 1) { n--; } // If the value of n in dp[] // is obtained from n / 2: else if (n % 2 == 0 && dp[Math.floor(n / 2)] == dp[n] - 1) { n = Math.floor(n / 2); } // If the value of n in dp[] // is obtained from n / 3: else if (n % 3 == 0 && dp[Math.floor(n / 3)] == dp[n] - 1) { n = Math.floor(n / 3); } } // Print the sequence // in reverse order sequence.reverse(); // Print the length of // the minimal sequence document.write(sequence.length+"<br>"); for(let i = 0; i < sequence.length; i++) { document.write(sequence[i] + " "); } } // Driver Code let n = 5; // Function Call find_sequence(n); // This code is contributed by unknown2108 </script>
4 1 3 4 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por premnagdeo y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA