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
[Aporte] [Algoritmos] Final 27/09/13 + posible resolución
Autor Mensaje
Tian Sin conexión
Empleado del buffet
Panic is on the way!
*

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 13
Agradecimientos dados: 3
Agradecimientos: 2 en 1 posts
Registro en: Mar 2013
Mensaje: #1
[Aporte] [Algoritmos] Final 27/09/13 + posible resolución Finales Algoritmos y Estructuras de Datos
Hola gente, les dejo el final que tomaron el viernes pasado, el 27/09. Como se dijo, se tomo algo de la nueva modalidad, aunque obviamente con enunciados y temáticas distintas. Voy a adjuntar la foto del enunciado, pero además lo voy a escribir por así se entiende bien

Acá va la foto
Spoiler: Mostrar
[Imagen: tfnw.jpg]

1) Merge (Apareo) de listas enlazadas Acá como ven hasta te decían que tenías que aplicar jaja
Temas evaluados: Listas enlazadas, abstracción procedural, estructuras de control, y lenguaje de programación

Sea Merge una operación definida para listas enlazadas del tipo genérico T que recibe dos listas, a y b, genere una tercer lista c con el apareo o fusión entre a y b

1a. Escriba en Pascal, C o C++, el encabezado de la función o procedimiento Merge

Bueno esto era básicamente poner:

Spoiler: Mostrar

Procedure Merge(a,b: T, var c:T)
.
.
.
Begin
.
.
.
end.


1.b Diseñe un algoritmo congruente con 1a. El algoritmo puede estar representado por un diagrama estructurado o por codigo en Pascal, C o C++

Asuma que las listas a y b están ordenadas y no tienen repeticiones Acá Bruno hizo una aclaración diciendo que además de que las listas no tenían repeticiones, tampoco había valores repetidos entre las diferentes listas. O sea que eran las dos totalmente distintas. En el momento supuse que dijo eso para que no confundan el ejercicio con hacer una intersección

Respete las siguientes restricciones
  • Invoque a function EsMenor(x: T; y: T): Boolean para comparar los elementos del tipo T, retorna verdadero si x es menor a y, si no, falso. No invoque otras funciones En esta parte, algunos se confundieron y pensaron que no se podía usar el InsertaNodo por ejemplo. Y bueno se complicaron la vida
  • Las listas datos a y b no deben ser modificadas.
  • La lista c debe generarse ordenada
  • Minimice la cantidad de veces que se recorra cualquiera de las tres listas

2. Suma de Números Astronómicos
Temas evaluados: Pilas, abstracción procedural, estructuras de control y lenguaje de programación, reusabilidad.
Introducción: En cierto campo de la astronomía los numeros enteros pueden tener magnitudes muy grandes, y su representación requiere una secuencia extensa de dígitos decimales (0 a 9). Esto imposibilita utilizar los tipos de datos generalmente contenidos en los lenguajes de programación. Un número astronómico se almacena en un archivo con una representación especial. La función LeerNumero es capaz de interpretar esa representación. La función LeerNumero(nombre) lee la secuencia de dígitos que encuentra en el archivo llamado nombre y lo retorna en una variable del tipo de dato Número Astronómico. NumeroAstronómico es una pila de bytes, donde cada byte es un dígito del número astronómico, el dígito menos significativo (el último del archivo y ne leerse) queda en la cima

Problema: Se reciben dos archivos, n1.dat y n2.dat, cada uno contiene un numero astronómico, y se requiere informar la suma de ambos.

2a. Implemente la función SumarNumeros(a,b) que suma los números astronómicos a y b y retorne el resultado en una pila de dígitos. En la cima de la pila resultante queda el dígito más significativo de la suma, a la inversa de lo que ocurre con cada NumeroAstronomico. Las pilas a y b quedan vacías. Debe utilizar las funciones de la biblioteca al dorso. La implementación de la función puede estar representada en un diagrama estructurado o codificada en Pascal, C o C++.

function SumarNumeros(var a: NumeroAstronomico, var b: NumeroAstronomico): PilaDeDigitos

2b. Implemente un programa que resuelva el problema. Debe invocar a LeerNumero(solo usarla), SumarNumeros (desarrollarla y usarla) y a MostrarNumero(solo usarla). La implementación del programa puede estar representada en un diagrama estructurado o codificada en Pascal, C o C++.

Resumiendo, lo que nos daban eran dos pilas que formaban un numero enorme cada una, donde cada nodo era un dígito, y teniamos que devolver la suma de ese numero, pero en otra pila.

El ejemplo que nos daban era:

Pila1: -> 6 -> 8 -> 9 -> 9 (este seria el numero 9986)

Pila2: -> 5 -> 3 (este sería el numero 35)

Teniamos que hacer la suma 9986 + 53 y devolver 10021 en una pila, PilaSuma en mi caso, en ese orden

PilaSuma: -> 1 -> 0 -> 0 -> 2 -> 1

¿Como se hacía?. Bueno era bastante fácil, pero había que darse cuenta de algo que era clave. La cosa era asi:


Spoiler: Mostrar
Sacas el tope de la Pila1, y el de la Pila2, y los sumas. Podía pasar que esa suma sea mayor o menor o igual a 10. Si la suma era menor o 10, el resultado que ponía en la PilaSuma era la suma directa. Pero si era mayor o igual a 10 lo que ponía como resultado en la pila era: ValorSuma - 10. Y además de eso, inicializar en 1 una variable auxiliar que yo llamé Carry.

¿De donde sale el Carry y eso de ValorSuma - 10?. Bueno por ejemplo:
Yo agarro el tope de las dos pilas, teniendo para sumar a 6 y a 5. Hago 6+5 y me da 11. Yo no puedo poner ese 11 como nodo de la PilaSuma, porque tiene que ser un dígito entre 0 y 9. Entonces, a ese 11 le resto 10; me queda un 1, que es el que pongo en la PilaSuma. Después lo del Carry es para sumar "lo que me llevo" o "lo que acarreo" en la siguiente suma de dos dígitos.

Termino eso, y saco de las pilas los dos siguientes, 8 y 3. Los sumo y me da 11, pero a eso tengo que sumarle el Carry que venía de la suma anterior. Entonces me queda 11 + 1 que da 12. Y ahora lo mismo que antes; como no puedo poner 12, hago 12 - 10, que da 2 y es lo que pongo en la PilaSuma. Además, el Carry va a seguir valiendo 1, porque me volví a exceder

Supongamos que los siguientes numeros eran 4 y 3. Al sumarlos, me da 7, con el que no tengo ningún problema en ponerlo directo en la PilaSuma. Entonces ademas de ponerlo directo, sin restarle nada, tenía que cambiar el valor de Carry a 0

Después bueno, esto se iba a hacer en un ciclo que se repetía hasta que una de las dos Pilas se termine. Dependiendo de cual terminaba, al salir del ciclo había que simplemente poner los numeros de la Pila que quedaba con valores (y en el caso de que el Carry valiese 1, sumarselo, como antes), y hacer el mismo proceso.

Al terminar de procesar las dos Pilas, había que hacer una última pregunta por si el Carry era igual a 1. Si era 1, lo mandaba a la Pila, y si era 0 no hacia nada

No se si se entendió del todo bien, pero bueno la clave estaba en darse cuenta, o mejor dicho recordar lo que nos enseñaron a todos en la primaria al sumar. Que se yo: 9 más 9, 18; pongo el 8, me llevo 1. 4 más 3, 7 más uno que me llevaba 8. Era avivarse eso y después salía solo

De última si no se me entiende una mierda dibujo el algoritmo y listo


3. Esta no me acuerdo bien y en la foto no sale, pero era algo asi como:
- Explique si es posible pasar argumentos por referencia (los que van con VAR) como parametros in, out e inout

Y bueno acá era poner que:
Spoiler: Mostrar
...el VAR se puede usar para cualquiera de los tipos de variable, pero que para las de entrada (in) no era necesario. Para las de salida (out) y entrada/salida (inout), si era necesario


Bueno eso era nomás. Como les dije antes, no era muy dificil, salvo el punto 2 que había que avivarse eso del Carry. Yo igual me saqué un 8, así que la estrategia en ese puede no estar del todo perfecta, pero bueno.

Saludos!
(Este mensaje fue modificado por última vez en: 04-10-2013 17:48 por Tian.)
30-09-2013 23:52
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
[-] Tian recibio 2 Gracias por este post
OrnellaSnm (20-12-2013), Raziel_yo (18-02-2014)
Jonthan.Castillo Sin conexión
Empleado del buffet
Sin estado :(
*

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1
Agradecimientos dados: 0
Agradecimientos: 0 en 0 posts
Registro en: Sep 2012
Mensaje: #2
RE: [Aporte] [Algoritmos] Final 27/09/13 + posible resolución
..
(Este mensaje fue modificado por última vez en: 28-11-2013 15:10 por Jonthan.Castillo.)
27-11-2013 20:54
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
rihardmarius Sin conexión
Secretario de la SAE
Por qué no me derivas el loga...
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 415
Agradecimientos dados: 100
Agradecimientos: 378 en 66 posts
Registro en: Oct 2011
Mensaje: #3
RE: [Aporte] [Algoritmos] Final 27/09/13 + posible resolución
aca esta el enunciado en pdf y las resoluciones en c++

http://www.utnianos.com.ar/foro/tema-apo...08-29-09-c

(Este mensaje fue modificado por última vez en: 06-12-2013 13:43 por rihardmarius.)
06-12-2013 13:42
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




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



    This forum uses Lukasz Tkacz MyBB addons.