Analisis

Análisis del problema de investigación.

El problema presentado es el de la página 73 del libro: Programming Challenges by Miguel Revilla

Este problema consiste en Fragmentación de Archivos

Este es el enunciado del problema según la versión en español del libro:

Un amigo, bioquímico de profesión, tropezó en su laboratorio mientras llevaba una bandeja llena de archivos de PC. Todos los archivos se rompieron al caer al suelo. Él recogió todos los trozos y busco ayuda para volver a ponerlos juntos.

Por suerte, todos los archivos de la bandeja eran idénticos, y todos se rompieron exactamente en dos trozos. Además se encontraron todos los trozos. Por desgracia, no todos se rompieron por el mismo sitio, y los trozos se mezclaron unos con otros al caer.

Los fragmentos binarios originales se han traducido a caracteres ASCII 1's y 0's. La tarea consiste en escribir un programa que determine el patrón de bits que contienen los archivos.

Entradas:

• La entrada comienza con un único entero positivo en una línea, que indica el número de casos de prueba, seguido de una línea en blanco. También habrá una línea en blanco entre cada dos casos consecutivos.

• Cada caso constara de una secuencia de “fragmentos de archivos", uno por línea, finalizado por un carácter de “\n” de archivo o una línea en blanco. Cada fragmento se representa como una cadena de 1s y 0s.

Salidas:

• Por cada caso de prueba en la entrada, se mostrara una única línea de 1s y 0s que indique el patrón

• de bits de los archivos originales. Si hay 2N fragmentos en la entrada, deberá ser posible concatenar dichos fragmentos, de manera que se formen N copias de la salida. Si no hay una solución única, cualquiera de las posibles será válida.

• Nuestro amigo bioquímico está seguro de que no hay más de 144 archivos en la bandeja, y que cada uno de ellos tena menos de 256 bytes de tamaño.

• Se separara con una línea en blanco la salida de cada dos casos consecutivos.

Ejemplo del archivo a leer:

Entrada

1

011

0111

01110

111

0111

10111

Salida

01110111

Se programó en 4 avances: Estos fueron en Java, Ruby, Erlang

...