4.5. Conversión de un entero a una cadena en cualquier base¶
Supongamos que usted desea convertir un entero a una cadena en una base entre la binaria y la hexadecimal. Por ejemplo, conviertir el entero 10 a su representación de cadena en decimal: "10", o a su representación de cadena en binario: "1010". Aunque hay muchos algoritmos para resolver este problema, incluyendo el algoritmo discutido en la sección de pilas, la formulación recursiva del problema es muy elegante.
Veamos un ejemplo concreto usando la base 10 y el número 769. Supongamos que tenemos una secuencia de caracteres que corresponde a los primeros 10 dígitos, como cadenaConversion = "0123456789". Es fácil convertir un número menor que 10 a su equivalente en cadena al buscarlo en la secuencia. Por ejemplo, si el número es 9, entonces la cadena es cadenaConversion[9] o "9". Si logramos descomponer el número 769 en tres números de un solo dígito, 7, 6 y 9, convertirlo entonces a una cadena es simple. Un número menor que 10 parece un buen caso base.
Saber cuál es nuestra base sugiere que el algoritmo global implicará tres componentes:
Reducir el número original a una serie de números de un solo dígito.
Convertir el número de un sólo dígito a una cadena mediante una búsqueda.
Concatenar las cadenas de un solo dígito para formar el resultado final.
El siguiente paso es averiguar cómo cambiar el estado y avanzar hacia el caso base. Puesto que estamos trabajando con un número entero, consideremos qué operaciones matemáticas podrían reducir un número. Las candidatas más probables son la división y la resta. Mientras que la resta podría funcionar, no está claro qué debemos restar de qué. La división entera con los residuos nos da una dirección clara. Echemos un vistazo a lo que sucede si dividimos un número por la base a la que estamos tratando de convertirlo.
Usando división entera para dividir 769 entre 10, obtenemos 76 con un residuo de 9. Esto nos da dos buenos resultados. En primer lugar, el residuo es un número menor que nuestra base que se puede convertir inmediatamente en una cadena mediante la búsqueda en cadenaConversion. En segundo lugar, obtenemos un número que es más pequeño que nuestro original y nos mueve hacia el caso base de tener un único número menor que nuestra base. Ahora nuestro trabajo es convertir 76 a su representación de cadena. Nuevamente usaremos la división entera más el residuo para obtener resultados de 7 y 6 respectivamente. Finalmente, hemos reducido el problema a la conversión de 7, lo cual puede hacerse fácilmente ya que satisface la condición de caso base de \(n < base\), donde \(base = 10\). La serie de operaciones que acabamos de realizar se ilustra en la Figura 3. Observe que los números que queremos recordar están en los bloques restantes a lo largo del lado derecho del diagrama.
Figura 3: Conversión de un entero a una cadena en base 10¶
Figura 3: Conversión de un entero a una cadena en base 10
El ActiveCode 1 muestra el código en Python que implementa el algoritmo descrito anteriormente para cualquier base entre 2 y 16.
Observe que en la línea 3 verificamos el caso base donde n es menor que la base a la que estamos convirtiendo. Cuando detectamos el caso base, dejamos la recursividad y simplemente devolvemos la cadena de la secuencia cadenaConversion. En la línea 6 satisfacemos tanto la segunda ley como la tercera, haciendo la llamada recursiva y reduciendo el tamaño del problema mediante la división.
Examinemos el algoritmo nuevamente; esta vez vamos a convertir el número 10 a su representación en base 2 como cadena ("1010").
Figura 4: Conversión del número 10 a su representación en base 2 como cadena¶
Figura 4: Conversión del número 10 a su representación en base 2 como cadena
La Figura 4 muestra que obtenemos los resultados que estamos buscando, pero parece que los dígitos están en el orden equivocado. El algoritmo funciona correctamente porque primero hacemos la llamada recursiva en la línea 6 y luego le concatenamos la representación en cadena del residuo. Si invertimos los valores devueltos por cadenaConversion y por la llamada aCadena, ¡la cadena resultante quedaría al revés! Pero al retrasar la operación de concatenación hasta después de que la llamada recursiva haya devuelto su valor, nos permite obtener el resultado en el orden correcto. Esto debería recordarle a usted nuestra discusión sobre las pilas en el capítulo anterior.
Autoevaluación
Escriba una función que tome una cadena como parámetro y devuelva una nueva cadena que sea la inversa de la cadena original.
Escriba una función que tome una cadena como parámetro y devuelva True si la cadena es un palíndromo y False en caso contrario. Recuerde que una cadena es un palíndromo si se escribe igual tanto hacia delante como hacia atrás. Por ejemplo: radar es un palíndromo. Como punto adicional, considere que los palíndromos también pueden ser frases, pero es necesario eliminar los espacios y la puntuación antes de hacer la verificación. Por ejemplo: anita lava la tina es un palíndromo. Otros palíndromos divertidos incluyen:
reconocer
La ruta natural
A la Manuela dale una mala
Ana, la galana
Anita, la gorda lagartona, no traga la droga latina
Aroma a mora
A ti no, bonita
Luz azul