Buenas gente,

hoy me presente al final de algoritmos (7/12/13) y debo decir que nada q ver con lo que tomaron en septiembre y agosto. El final era mas o menos esto:

Te dan un archivo de registros con dos campos, uno era un entero y el otro un caracter. Despues te daban una lista enlazada de listas enlazadas, donde la lista principal eran numeros con dos punteros, uno para el siguiente y el otro para la sublista, las sublistas eran de letras (caracteres). Tanto la "meta-lista" como el archivo estaban ordenados y habia que desarrollar una funcion que fusione ambas estructuras en una, un apareo. Te daban el prototipo de la funcion, los parametros eran (const string& n, const lista& l, puntero p), n era el nombre del archivo, l era la meta-lista, ambos de entrada, p el puntero hacia la nueva estructura, de salida. Devolvia void.

en temas evaluados aparecia: corte de control, apareo, listas, archivo, registros, abstraccion procedural.

el punto 2 era simplemente explicar que tipo de estructura seria la mas eficiente y por que.

honestamente no tengo ni idea de como se resuelve, por suerte nos dieron 10 min para ver el final y decidir si lo rendiamos, yo me retire.

EDIT

aca hice una resolucion

final http://pastebin.com/VY3c2mQ4
libreria http://pastebin.com/c9XcLVmm

compila y todo

Hola que tal, en clase hicimos ese mismo ejercicio con él. Lo que había que hacer era leer registro a registro (del archivo) y nodo a nodo (de la metalista) y comparar los enteros, si era menor el del registro del archivo (suponiendo que el orden era creciente) usabas corte de control para meter en una nueva lista todos los campos char del registro cuyo campo entero fuera igual, y en una metalista metes ese entero y el puntero a la lista con los caracteres.

Si era más chico el entero del nodo de la metalista simplemente agregabas ese nodo a la metalista que creas vos, no tenés que hacer más nada porque la sublista correspondiente a ese nodo ya va a tener todos los caracteres que corresponden a ese entero.

Como en cualquier apareo, al agotarse uno de los dos estructuras salís del bucle, y quedaría agotar la estructura con mayor cantidad de elementos. Cerras el archivo y termina la función.

Espero haberte ayudado, si me expresé mal preguntá de nuevo y veo de decirlo de otra manera más entendible xD

Saludos!

Voy a intentar poner mi resolución ahora que está medio fresca.

1) La estrategia que use fue algo asi (si aparecen dudas intento hacer el diagrama, ahora estoy sin dormir y con paja)

procedure Fusionar(archivo : string; lista : tipoLista; var estrAbstracta : puntero);

Te daban algunos procedimientos "magicos" para usar ya que se desconocía cual era el formato de la estructura de salida (estructura abstracta) a donde iba a parar la fusion entre el archivo y la lista:

InsertarGrupo(estructura, grupo)
InsertarValorEnGrupo(estructura, grupo, valor)

Otra aclaración, los valores de las letras de la lista iban de a-m y los del archivo de n-z.

Estrategia:
1. Crear la estructura abstracta (estructura = NIL)
2. Leer archivo(arch, reg, fin)
3. while (lista<>NIL) and (not fin)
>>>> if reg.grupo < lista.grupo
* InsertarGrupo(estrAbstracta, reg.grupo)
* InsertarValorEnGrupo(estrAbstracta, reg.grupo, reg.valor)
* GrupoAnterior = Grupo (habia que hacer un corte de control para el archivo)
* LeerArchivo
>> while not fin and GrupoAnterior = Grupo do
- InsertarValorEnGrupo
- LeerArchivo
>>>> if reg.grupo = lista.grupo (en este caso primero se procesa la lista y despues el archivo)
* InsertarGrupo(estrAbstracta, lista.grupo)
* lista = lista^.sublista
>> while lista <> nil
- InsertarValorEnGrupo(estrAbstracta, grupo, sublista.valor)
- lista = sublista^.sgte
* (afuera del while) lista = lista^.sgte
* InsertarValorEnGrupo(estrAbstracta, reg.grupo, reg.valor) <empieza a procesar el archivo
* GrupoAnterior = Grupo (habia que hacer un corte de control para el archivo)
* LeerArchivo
>> while not fin and GrupoAnterior = Grupo do
- InsertarValorEnGrupo
- LeerArchivo
>>>> if reg.grupo > lista.grupo
* InsertarGrupo(estrAbstracta, lista.grupo)
* lista = lista^.sublista
* InsertarValorEnGrupo(estrAbstracta, grupo, sublista.valor)
>> while lista <> nil
- InsertarValorEnGrupo
- lista = sublista^.sgte
* (afuera del while) lista = lista^.sgte
4. while not fin do
- InsertarGrupo
- InsertarValorEnGrupo
- LeerArchivo
5. while lista <> nil do
- InsertarGrupo
- InsertarValorEnGrupo
- lista = sublista^.sgte

2)
Para determinar la estructura me basé en los 2 campos que se usan para resolver el problema: grupo (entero) y valor (char).
Para el grupo, que sería el 1er. nivel de la estructura, sabemos que es un numero entero pero no se sabemos cuantos grupos puede haber (podrían ser de 0 a N grupos), por lo que había que usar memoría dinámica (ej. una lista).
Para el valor, que son caracteres (osea, el abecedario, 27 letras), se sabe la cantidad que pueden ser asi que puse que había que usar un vector de 27 posiciones (suponiendo que cada letra esta solamente 1 vez por grupo, por lo que habia posibilidad que se usen menos de las 27 pos).

Entonces queda una lista que por cada nodo tiene 3 campos: un registro con grupo y vector (letras), y un campo siguiente:
   

La codificación quedaría asi:

 type



tVector = array[1..27] of char;



tInfo = record

Grupo : integer;

Vector : tVector;

end;



tLista = ^tNodo;



tNodo = record

Info : tInfo;

Sgte : tLista;

end;

Practique con los finales de la nueva modalidad y con las guias de ejercicios. Comparandolo con los finales nuevos, lo que mas complicaba era la lista de listas, no habian tomado una estructura asi mas complejita hasta ahora.. pero el apareo sí ya lo venian tomando en los finales (merge, interseccion, diferencia simetrica).

Yo fui a rendir hoy y me saqué un 8. Lo que hice fue hacer el procedimiento FUSIONAR con la estructura del Apareo, y había que ir recorriendo la lista y dentro de la lista, la sublista (los caracteres), y el archivo que te daban. La estructura de salida no te decía exactamente qué era, solo te decían que era de tipo PUNTERO y te daban unas funciones que tenías que usar para cargarla. Esas funciones se debían usar, eran para crear e insertar, ya sea el grupo (número) o el valor dentro del grupo (caracter).
Los caracteres de la sublista iban del rango [a,m] y los del archivo de [l,z], es decir, que primero se debían cargar los de la lista y después los del archivo.
Sin la imagen del exámen es medio raro para entenderlo, a mi me costó entender el enunciado un montón. Estuve un buen rato leyéndolo e improvisando, hasta que me salió. No era gran cosa el final, creo que la cuestión era entenderlo. A mi me parece que los enunciados que están haciendo la complican. En general fue hacer un procedimiento en el cual se hacía apareo y se usaban ciertas funciones olbigatorias que te daban.

entonces, basicamente era un apareo de un archivo y una lista... ordenados por grupo (numero).

me mato lo de la estructura abstracta, no entendia q hacia o como estaba hecha

gracias gente, capaz q despues algun alma solidaria sube el enunciado y veo de hacerlo

Volaron al carajo lo bueno de tener varios ejers con diferentes temas de los finales anteriores. Subo el enunciado.

Acá el enunciado completo.

Subido por el profesor Oscar Bruno, en un twit.

Si entendí bien, viene a ser algo así? Hace rato que no toco pascal, si ven algo mal avisen!

 Type



Tsublista = ^Tsubnodo;

Tsubnodo = Record

  letra: char;

  sig: Tsublista

end;



Tinfo = Record

  grupo: integer;

  sublista: Tsublista

end;



Tlista = ^Tnodo;

Tnodo = Record

  info: Tinfo;

  sig: Tlista

end;

Si bien como esta arriba con un array funciona, como estaba dibujado en el enunciado supuse que una lista quedaría mas acorde.


Ah y otra cosa, dice que esta todo ordenado. No es mas fácil ir agregando a la nueva estructura (por orden de grupo) 1ro los del archivo, 2do los de igual grupo (con preferencia a los del archivo) y finalmente los grupos que quedaron en la estructura? De esa forma te evitas el corte de control.

Yo tuve a Frankel y no explicaba nada, era mi primera cursada. Abandone a mitad de año y viendo bien este final si seguia no iba a estar bien preparado. Lo unico que me aferre en la cursada fue al libro de pascal. Que profesores explican bien la materia?

(13-12-2013 19:00)alvar escribió:  Yo tuve a Frankel y no explicaba nada, era mi primera cursada. Abandone a mitad de año y viendo bien este final si seguia no iba a estar bien preparado. Lo unico que me aferre en la cursada fue al libro de pascal. Que profesores explican bien la materia?

mmm eso es un tanto subjetivo/personal

yo tuve a Solá y si bien no explica mal, tampoco explica mucho, muchos temas (como cortes de control) no los dio, apareo tampoco

el año pasado tuve a ferrari, pero no sabria decirte porque la deje a mitad de año

Despues esta Bruno Oscar, el jefe del departamento, hay opiniones encontradas sobre el, algunos dicen q es lo mas, otros q no lo pueden ni ver
personalmente ni idea como es

Para aprobar Bruno es la mejor opción, pero realmente no es el mejor de los profesores para aprender bien, te ayuda mucho con las clases de consulta cuando venís perdido, está bueno si cursas con alguien más y complementas con el, pero en sí no arma bien las clases, da todos los temas muy por el aire, los algoritmos básicos los enseña sobre un ejercicio particular en vez de hacerlos más genéricos para poder volver a aplicarlos en cualquier lado, los enunciados ni el los entiende (fuera de joda, varias veces el se quedaba mirándolo sin saber que había pedido, me pasó en el segundo parcial xD) y da muy poca práctica y muy sencilla y medio que te confias, para aprender te tenés que poner por tu cuenta y consultarle las dudas.

Pablo snadjler (o algo así) explica muy bien, pero tengo entendido que es medio exigente, con cuello no te anotes ni por casualidad, y hay un profesor que no se si tiene un curso fijo, se llama Marcelo Lipskin, ese si que explica como los dioses, la tiene muy clara y te trasmite muy fácil todo lo que sabe, te enseña las estructuras, a encarar los ejercicios y te da tips muy buenos, yo lo tuve unas clases cuando Bruno se había ido de viaje, pero no se si tiene cursos, tendrías que consultar.

ahi adjunte una resolucion propuesta, si me dicen q tal esta fenomeno

compila y todo pero capaz q le pifie a algun concepto

EDIT

otra cosa, para q esta la funcion crear puntero? si el puntero p es un parametro de salida, y deberia existir antes de la llamada a la funcion fusionar

Creo que esta bien, por lo menos la estrategia es similar a lo que pensé. grupo_ant lo usas en el caso que tengas grupos repetidos?

Este final fue bastante accesible,,

(13-12-2013 23:32)Shiny Shoes escribió:  Creo que esta bien, por lo menos la estrategia es similar a lo que pensé. grupo_ant lo usas en el caso que tengas grupos repetidos?

claro, es muy probable q sea asi ya q era un corte de control al final