Encuentre todos los números binarios de n dígitos sin ningún 1 consecutivo
Dado un entero positivo n, cuente todos los números binarios de n dígitos sin ningún número consecutivo 1's.
por ejemplo, para n = 5, los números binarios que satisfacen las restricciones dadas son: [00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101].
Una solución simple sería generar todos los números enteros de n dígitos e imprimir solo aquellos números enteros que satisfagan las restricciones dadas. La complejidad de esta solución sería exponencial.
Una mejor solución es generar solo aquellos números enteros de n dígitos que satisfagan las restricciones dadas. La idea es usar recursión. anexamos 0 y 1 al número parcialmente formado y recurren con un dígito menos en cada punto de la recursión. Aquí, el truco es añadir 1 y se repite solo si el último dígito del número parcialmente formado es 0. De esa manera, nunca tendremos ninguna consecutiva. 1's en la string de salida.
A continuación se muestra la implementación de la idea en C++, Java y Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <string> using namespace std; // Función para contar todos los números binarios de n dígitos sin ningún 1 consecutivo int countStrings(int n, int last_digit) { // caso base if (n == 0) { return 0; } // si solo queda un digito if (n == 1) { if (last_digit) { // si el ultimo digito es 1 return 1; } else { // de lo contrario, si el último dígito es 0 return 2; } } // si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual if (last_digit == 0) { return countStrings(n - 1, 0) + countStrings(n - 1, 1); } // si el último dígito es 1, solo podemos tener 0 en la posición actual else { return countStrings(n - 1, 0); } } int main() { // número total de dígitos int n = 5; cout << "The total number of " << n << "–digit binary numbers without any " "consecutive 1's are " << countStrings(n, 0); return 0; } |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Main { // cuenta todos los números binarios de n dígitos sin ningún 1 consecutivo public static int countStrings(int n, int lastDigit) { // caso base if (n == 0) { return 0; } // si solo queda un digito if (n == 1) { return (lastDigit == 1) ? 1: 2; } // si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual if (lastDigit == 0) { return countStrings(n - 1, 0) + countStrings(n - 1, 1); } // si el último dígito es 1, solo podemos tener 0 en la posición actual else { return countStrings(n - 1, 0); } } public static void main(String[] args) { // número total de dígitos int n = 5; System.out.println("The total number of " + n + "–digit binary numbers " + "without any consecutive 1's are " + countStrings(n, 0)); } } |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# cuenta todos los números binarios de n dígitos sin ningún 1 consecutivo def countStrings(n, lastDigit=0): # Caja base if n == 0: return 0 # si solo queda un dígito if n == 1: return 1 if (lastDigit == 1) else 2 # si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual if lastDigit == 0: return countStrings(n - 1, 0) + countStrings(n - 1, 1) # si el último dígito es 1, solo podemos tener 0 en la posición actual else: return countStrings(n - 1, 0) if __name__ == '__main__': # número total de dígitos n = 5 print(f'The total number of {n}–digit binary numbers without any consecutive 1\'s' f' is {countStrings(n)}') |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
La complejidad temporal de la solución anterior es exponencial y ocupa espacio en la pila de llamadas.
El problema tiene un subestructura óptima y exhibiciones subproblemas superpuestos. Si dibujamos el árbol de recurrencia de la solución, podemos ver que los mismos subproblemas se calculan repetidamente. Sabemos que los problemas con subestructura óptima y subproblemas superpuestos se pueden resolver mediante programación dinámica, en la que las soluciones de los subproblemas se memorizan en lugar de calcularse repetidamente.
El algoritmo se puede implementar de la siguiente manera en C++, Java y Python, donde primero resolvemos los subproblemas más pequeños y luego resolvemos los subproblemas más grandes a partir de ellos.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <string> using namespace std; // Función para contar todos los números binarios de n dígitos sin ningún 1 consecutivo int countStrings(int n) { int T[n+1][2]; T[0][0] = 0, T[0][1] = 0; // no queda ningún dígito T[1][0] = 2, T[1][1] = 1; // si solo queda un digito for (int i = 2; i <= n; i++) { // si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual T[i][0] = T[i-1][0] + T[i-1][1]; // si el último dígito es 1, solo podemos tener 0 en la posición actual T[i][1] = T[i-1][0]; } return T[n][0]; } int main() { // número total de dígitos int n = 5; cout << "The total number of " << n << "–digit binary numbers without any " "consecutive 1's are " << countStrings(n); return 0; } |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Main { // Función para contar todos los números binarios de n dígitos sin ningún 1 consecutivo public static int countStrings(int n) { int[][] T = new int[n+1][2]; // si solo queda un digito T[1][0] = 2; T[1][1] = 1; for (int i = 2; i <= n; i++) { // si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual T[i][0] = T[i-1][0] + T[i-1][1]; // si el último dígito es 1, solo podemos tener 0 en la posición actual T[i][1] = T[i-1][0]; } return T[n][0]; } public static void main(String[] args) { // número total de dígitos int n = 5; System.out.print("The total number of " + n + "–digit binary numbers " + "without any consecutive 1's are " + countStrings(n)); } } |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Función para contar todos los números binarios de n dígitos sin ningún 1 consecutivo def countStrings(n): T = [[0 for x in range(2)] for y in range(n + 1)] # si solo queda un dígito T[1][0] = 2 T[1][1] = 1 for i in range(2, n + 1): # si el último dígito es 0, podemos tener tanto 0 como 1 en la posición actual T[i][0] = T[i-1][0] + T[i-1][1] # si el último dígito es 1, solo podemos tener 0 en la posición actual T[i][1] = T[i-1][0] return T[n][0] if __name__ == '__main__': # número total de dígitos n = 5 print(f'The total number of {n}–digit binary numbers without any consecutive 1\'s' f' is {countStrings(n)}') |
Resultado:
The total number of 5–digit binary numbers without any consecutive 1’s is 13
La complejidad temporal de la solución anterior es O(n) y requiere O(n) espacio adicional, donde n es el número total de dígitos.
¿Cómo imprimir todos los números binarios?
El siguiente código recursivo en C++, Java y Python también imprime todos los números binarios:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <string> using namespace std; // Función para imprimir todos los números binarios de n dígitos sin ningún 1 consecutivo void countStrings(int n, string out, int last_digit) { // si el número se convierte en n-dígito, imprímelo if (n == 0) { cout << out << endl; return; } // agregar 0 al resultado y repetir con un dígito menos countStrings(n - 1, out + "0", 0); // agregar 1 al resultado y repetir con un dígito menos // solo si el ultimo digito es 0 if (last_digit == 0) { countStrings(n - 1, out + "1", 1); } } int main() { // número total de dígitos int n = 5; string out = ""; countStrings(n, out, 0); return 0; } |
Resultado:
00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class Main { // Función para imprimir todos los números binarios de n dígitos sin ningún 1 consecutivo public static void countStrings(int n, String out, int last_digit) { // si el número se convierte en n-dígito, imprímelo if (n == 0) { System.out.println(out); return; } // agregar 0 al resultado y repetir con un dígito menos countStrings(n - 1, out + '0', 0); // agregar 1 al resultado y repetir con un dígito menos // solo si el ultimo digito es 0 if (last_digit == 0) { countStrings(n - 1, out + '1', 1); } } public static void main(String[] args) { // número total de dígitos int n = 5; String out = ""; countStrings(n, out, 0); } } |
Resultado:
00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
# Función para imprimir todos los números binarios de n dígitos sin ningún 1 consecutivo def countStrings(n, out='', last_digit=0): # si el número se convierte en n-dígito, imprímalo if n == 0: print(out, end=' ') return # agregar 0 al resultado y repetir con un dígito menos countStrings(n - 1, out + '0', 0) # agregar 1 al resultado y repetir con un dígito menos # solo si el último dígito es 0 if last_digit == 0: countStrings(n - 1, out + '1', 1) if __name__ == '__main__': # número total de dígitos n = 5 countStrings(n) |
Resultado:
00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101