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
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:
Procedure Merge(a,b: T, var c:T)
.
.
.
Begin
.
.
.
end.
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:
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:
...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!
![[-]](images/collapse.gif)
Tian recibio 2 Gracias por este post
