ANTECEDENTES

El problema planeta usa conversión de binario a decimal, sin embargo el problema en este caso es generar particiones de la cadena base tales que cada subcadena represente un dígito entre 0 y 9.

SOLUCIÓN

La solución propuesta va generando subcadenas de la cadena original. La máxima longitud de estas subcadenas es de 4, que es el número de dígitos binarios necesarios para representar el 8 y el 9. A medida que se genera una subcadena se procede a verificar que no tenga ceros a la izquierda. Para esta verificación se mira que el número de dígitos necesarios para representar el número sea igual a la longitud de la subcadena.

Cuando se genera esta subcadena, se repite el mismo proceso con la parte restante de la cadena original. De esta forma en cada paso lo que se tiene es

          Cadena = subcadena + resto

Donde subcadena es la representación binaria de un dígito de 0 a 9. Entonces al repetir recursivamente el proceso para el resto de la cadena, obtenemos una secuencia de dígitos que es una de las posibles interpretaciones de la cadena binaria original.

Nótese que esta solución es adecuada, debido a que en el problema se requiere como salida todas las posibles interpretaciones de la cadena, lo que implica que es necesario interpretar todas las posibles secuencias de subcadenas, que es lo que se realiza con el proceso recursivo.

CÓDIGO

Dentro del código la función que resuelve el problema es

Procesar( pos, n)

Prueba con las subcadenas que inician en la posición pos para generar un dígito decimal. Este dígito decimal se almacena en el arreglo sol en la posición n. Dentro de esta función existen llamadas recursivas para comenzar a probar subcadenas en las posiciones siguientes y con n+1.

Duvier Alexander Zuluaga Mora

duvier@softhome.net