Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
Duda con el ejercicio 32 de la guía "de 83 ejercicios"
Autor Mensaje
rob. Sin conexión
Presidente del CEIT
Smile!
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.149
Agradecimientos dados: 126
Agradecimientos: 83 en 64 posts
Registro en: Dec 2010
Mensaje: #1
Duda con el ejercicio 32 de la guía "de 83 ejercicios" Ejercicios Algoritmos y Estructuras de Datos
Para evitar confusiones, es un ejercicio de la guía "complementaria" de 83 ejercicios:

32) Dado un archivo de alumnos inscriptos para cursar por año completo (desordenado) donde cada registro contiene:
a) Nro. de legajo (5 digitos)
b) Especialidad (1 a 10)
c) Turno ('M', 'T' ó 'N')
d) División (1 a 100)

Desarrollar el programa que genere otro archivo con la misma cantidad de registros pero ordenado por especialidad, turno y division.
Nota: no hay mas de 100 alumnos por cada división y se disponen de 550kb de memoria.


Comentario:
En ejercicios anteriores acostumbraba hacer búsqueda binaria, y meter en un array la posición del legajo en el archivo (siendo la posición del array el legajo). Sin embargo, acá me confundo cuando hay que ordenar por tres, y no se me ocurre una estrategia para hacer con arrays.


Espero puedan ayudarme (preferentemente armenlo en Visio, aunque me da igual como lo expliquen mientras lo pueda entender), ¡gracias! =D

wake me up when september ends!
(Este mensaje fue modificado por última vez en: 30-05-2012 23:31 por rob..)
30-05-2012 23:29
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
el pibe Sin conexión
Presidente del CEIT
Benderista
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.235
Agradecimientos dados: 5
Agradecimientos: 102 en 28 posts
Registro en: May 2011
YouTube
Mensaje: #2
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"
mira, con 550 kb te haces alto guiso (?)

legajo: 5 digitos ponele longword -> 4 bytes
especialidad: 1 digito, byte -> 1 byte
turno: un char (o como dicen los eruditos locos, un int, en fin, tamos todos locos) -> 1 byte
division: 1 a 100, byte -> 1 byte

total= 7 bytes
sumale un puntero
total =11 bytes

supongamos caso maximo: 100 alumnos en las 100 divisiones:
100*100 = 10000
10000 * 11 bytes = 110000 bytes = 107.42 kb

y te dan 550 kb

si multiplicas eso por 5 te da 537.109 kb (te sobra). Podes hacer 5 listas iguales.

A lo que voy, es que te recontra regalan espacio. Ahora, con todo ese espacio, no vas a hacer 5 listas.

Lo que podes hacer es esto:

1) Haces un array de registros cuyo indice es la especialidad(1 a 10) y su unico campo es un puntero a una lista de turnos
sumario de memoria hasta ahora: 10 filas * 1 columna de 4 bytes = 40 bytes ;
cada puntero apunta a una lista con 3 nodos (mañana, tarde, noche) eso es (1 byte + 4 bytes del puntero) * 3 (cantidad de nodos) = 15 bytes;
esos 15 bytes van a estar para las 10 filas, asi que 15 bytes * 10 filas= 150 bytes
Entonces hasta ahora tenemos: 40 bytes + 150 bytes = 190 bytes

2) Insertar los alumnos en la especialidad que corresponda, turno que corresponda, ordenado por especialidad
Si tomamos caso maximo de alumnos, como puse antes seria: 100 alumnos en las 100 divisiones: 100*100 = 10000 bytes; 10000 * 11 bytes = 110000 bytes = 107.42 kb


A eso le sumamos los 190 bytes de lo demas: 190 bytes + 107.42 kb < 550 kb

Te dan 550 kb. RECONTRA OPTIMO.

Capaz hay otra forma mas optima, npi (ni puta idea)


Para armar el archivo, recorres cada fila del array, clavas por turno todos los alumnos. Bueno, se entiende por donde va la idea ?

edit: sume mal los bytes al final

[Imagen: tolivi10.jpg]
2 Veces congresista por eArgentina
13 Veces congresista por eBolivia
1 Vez Emperador por eBolivia
Ex-Ministro de Salud eArgentino

[Imagen: Necromancer616.png]
(Este mensaje fue modificado por última vez en: 31-05-2012 00:12 por el pibe.)
31-05-2012 00:10
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] el pibe recibio 1 Gracias por este post
rob. (01-06-2012)
nanuiit Ausente
♫ I'm Blue ...
... Da ba dee, da ba da ♫
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 8.880
Agradecimientos dados: 216
Agradecimientos: 574 en 201 posts
Registro en: Aug 2010
Mensaje: #3
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"

Off-topic:
Me aguantás hasta esta noche y te respondo? Mí estar en el laburou y se me complica


Ah, y te lo escanearía, pero mi cuaderno lo tiene Rulo. Pero llego a casa y te digo qué opino del ejercicio

ALGORITMOS

Apuntes: Mem. Dinámica - Mem. Estática - Proc. y Funciones || Guías: Módulos + 83 Ejercicios || Finales: 2004-2013


[Imagen: digitalizartransparent.png]

[Imagen: firmananiv2.png]
31-05-2012 10:06
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
el pibe Sin conexión
Presidente del CEIT
Benderista
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.235
Agradecimientos dados: 5
Agradecimientos: 102 en 28 posts
Registro en: May 2011
YouTube
Mensaje: #4
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"
bleh, hice las cosas rapido y me falto aclarar:
cada nodo de turno tiene un puntero a una lista con los alumnos, ordenado por division.

te sigue sobrando memoria

[Imagen: tolivi10.jpg]
2 Veces congresista por eArgentina
13 Veces congresista por eBolivia
1 Vez Emperador por eBolivia
Ex-Ministro de Salud eArgentino

[Imagen: Necromancer616.png]
31-05-2012 11:01
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
rob. Sin conexión
Presidente del CEIT
Smile!
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.149
Agradecimientos dados: 126
Agradecimientos: 83 en 64 posts
Registro en: Dec 2010
Mensaje: #5
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"
(31-05-2012 11:01)el pibe escribió:  bleh, hice las cosas rapido y me falto aclarar:
cada nodo de turno tiene un puntero a una lista con los alumnos, ordenado por division.

te sigue sobrando memoria

No me hables de nodos ni punteros que recién lo estoy viendo. Me basta con tocarlo entre archivos y registros solamente, o como mucho con arrays =P.


Leí lo primero y con lo de punterios medio que me mataste, así que improvisaré algo hasta tanto (o sea, voy a tratar de descifrar tu "estrategia" y ver que puedo sacar. Le mando un "gracias" igual por la intención =D.

(31-05-2012 10:06)nanuiit escribió:  Pero llego a casa y te digo qué opino del ejercicio

=)

wake me up when september ends!
(Este mensaje fue modificado por última vez en: 01-06-2012 00:43 por rob..)
01-06-2012 00:17
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
nanuiit Ausente
♫ I'm Blue ...
... Da ba dee, da ba da ♫
**********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 8.880
Agradecimientos dados: 216
Agradecimientos: 574 en 201 posts
Registro en: Aug 2010
Mensaje: #6
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"
Leí muy por arriba porque estoy con diez mil cosas, pero si podés usar un array como para ordenar ahí mientras vas leyendo, podés hacer un InsertaOrdenadoArray por más de un criterio
Eso es válido y aplica a la época de la cursada en la que estás
Ese ejercicio cuando habla de memoria, es memoria estática.. creo que la parte de dinámica es por arriba del ejercicio 50.

Volviendo, si tuviera el cuaderno, ahí tenía la resolución más óptima.

Me acuerdo que era un ejercicio super fulero.
De muy buenas y primeras, y no es la solución más feliz, yo grabaría en el array las posibles combinaciones entre especialidad, turno y división. Total, sabés que como máximo hay 100 divisiones

Entonces tendrías (1 byte de especialidad + 1 byte de turno + 1 byte de división) * 100 = 300 bytes
Leeria en el archivo, me fijaria si los datos de estas tres cosas coinciden con las del array; de no ser así grabo una nueva combinación en el vector

Una vez que hago eso puedo reordenar el array (burbujeo), o antes podría haberlo insertado ordenado.

Después tomo el vector, que como está ordenado lo uso para ir buscando en el archivo y entonces voy haciendo eso mientras grabo en el archivo nuevo.

No es de lo más feliz...


Creo que la otra solución era usar el array para grabar por curso.. y cada vez que leías todo el curso, vaciabas el array, que tampoco me convence

ALGORITMOS

Apuntes: Mem. Dinámica - Mem. Estática - Proc. y Funciones || Guías: Módulos + 83 Ejercicios || Finales: 2004-2013


[Imagen: digitalizartransparent.png]

[Imagen: firmananiv2.png]
(Este mensaje fue modificado por última vez en: 01-06-2012 01:06 por nanuiit.)
01-06-2012 00:42
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] nanuiit recibio 1 Gracias por este post
rob. (01-06-2012)
lagrange Sin conexión
Empleado del buffet
Sin estado :(
*

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 24
Agradecimientos dados: 45
Agradecimientos: 1 en 1 posts
Registro en: Dec 2009
Mensaje: #7
RE: Duda con el ejercicio 32 de la guía "de 83 ejercicios"
Te agrego otra posibilidad, usando segmentación.

Es muy parecido a lo que decía nanuiit, pero sin ordenar.

utilizo un array compuesto por:
(1 byte de especialidad + 1 byte de turno + 1 byte de división + 4 bytes de legajo) * 3000 = 21000 bytes < 20 kb

El 3000 es por la combinación de ocurrencias :
10 especialidades * 3 turnos * 100 divisiones = 3000 ocurrencias

Lo siguiente a realizar es completar el array inicializandolo con todas las especialidades posibles, combinado con todos los turnos posibles y todas las divisiones posibles y el campo de legajo en cero.

Luego leo el primer registro y busco secuencialmente (aunque podría ser binaria) su especialidad en el array que esta ordenado, luego busco desde el principio de ese subgrupo el turno, para buscas en el principio de ese subsubgrupo la division que le corresponde, y en ese lugar guardo el legajo. Asi por cada registro.

Entonces me queda cargado el array con el contenido del archivo pero con el orden pedido.

Ahora recorro este array y grabo en el archivo nuevo siempre que no encuentre en cero el legajo.

Como moraleja usas mucha mas memoria y la carga inicial de la matriz puede ser conflictiva pero evitas el ordenamiento que baja la performance de un pgm.

Saludos!
02-06-2012 01:24
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] lagrange recibio 1 Gracias por este post
rob. (04-06-2012)
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.