Actualizacion de tablas de frecuencias (Ex.Pract. PRO2 Q2-2018-2019 T1) X30943

1. El peso de este ejercicio en la nota del exámen de la práctica es de un 66.66% (2/3 de la nota).
2. Nota manual: 50%, nota automática: 50%
3. El peso de todos los juegos de pruebas en el cálculo de la nota automática es idéntico (público: 2.5/10, privados: 2.5/10 cada uno).

Dadas dos tablas de frecuencias f1=F₁ y f2=F₂, queremos una función que actualiza la primera con los datos de la segunda. Las tablas estarán representadas por map<string,int>. Todas las frecuencias en f1 y f2 son estrictamente positivas.

Como resultado de la actualización la tabla f1 contendrá:

• Si ⟨ s,f⟩ es un par de la tabla F₁ y F₂ no contiene ningún par con clave igual a s, entonces ⟨ s,f⟩ está en la tabla f1 final.
• Si ⟨ s,f⟩ es un par de la tabla F₂ y F₁ no contiene ningún par con clave igual a s, entonces ⟨ s,f⟩ está en la tabla f1 final.
• Si ⟨ s,f⟩ es un par de la tabla F₁ y ⟨ s,f′⟩ es un par de la tabla F₂ entonces ⟨ s,f+f′⟩ está en la tabla f1 final.

Por ejemplo si f1 y f2 son las tablas mostradas a continuación:

entonces después de la actualización f1 será

Implementa la siguiente función

// Pre: y Post: ver la descripción del enunciado
void actualiza_tabla_frec(map<string,int>& f1, const map<string,int>& f2);

Escribe un pequeño programa que lea una tabla de frecuencias f1, y a continuación, aplica sucesivas actualizaciones, imprimiendo cómo queda f1 después de cada actualización. Para cada actualización se ha de leer una tabla de frecuencias f2, actualizar f1 con f2 mediante la función implementada, e imprimir la tabla f1.

N.B. De cara a obtener una solución lo más eficiente posible, tened en cuenta lo siguiente:

1. Recorrer un map mediante iteradores de principio a fin toma tiempo proporcional al tamaño del map—suponiendo que en cada iteración del recorrido se invierte un tiempo constante.
2. La clase map tiene un método insert(iterator,par-clave-valor) para dar una “pista” sobre dónde debe insertarse el nuevo elemento. Por ejemplo, si insertamos N elementos en orden creciente de clave usando m.insert(m.end(), x) el coste será proporcional a N; si se utilizase el método normal m.insert(x) el coste será mucho mayor, proporcional a N· log₂ N.

Entrada Cada tabla de frecuencias se representará en la entrada mediante una secuencia que comienza con un entero k≥ 0 seguida de una secuencia de k pares ⟨ s, f⟩ describiendo los pares que constituyen la tabla.

La entrada comienza con la subsecuencia que representa a la tabla f1. A continuación viene una serie de tablas de frecuencias (cada una representada por una secuencia con el formato que hemos descrito arriba). La última tabla de frecuencias de la serie es un tabla vacía (k = 0).

Salida Para cada tabla de frecuencias f2 de la serie, excepto la última tabla vacía que marca el final de la serie, se actualiza la tabla f1 con los datos de f2 y se imprime la tabla f1 actualizada. Una tabla de frecuencias se imprime siguiendo el mismo convenio que para la entrada: primero un entero k con su tamaño y a continuación una secuencia de los k pares ⟨ s, f⟩ que contiene la tabla (separamos las componentes s y f de cada par mediante un espacio en blanco), pero adicionalmente los pares han de estar en orden creciente de clave (ordenados por la s). Después de imprimir la tabla f1 tras cada actualización se imprime un salto de línea.

Observación Utilizad la plantilla (plantilla-solucion.cc_txt) que os damos con los ficheros públicos (icono del gatito) para preparar la solución.