Examen Parcialito - 75.41. Algoritmos y Programación II - 14/12/2012
Cátedra: Wachenchauzer
Fecha: Segunda Oportunidad - (Segundo Cuatrimestre) 2012
Día: 14/12/2012
Enunciado
Resolvé los siguientes problemas en forma clara y legible, respetando sangrías e incluyendo la documentación necesaria. Si te parece que los comentarios no son suficientemente explicativos, podés agregar una descripción del funcionamiento del código. Podés escribir tantas funciones auxiliares como creas necesarias.
Punto I
a) Diseñe un algoritmo que resuelve el problema de las 8 Reinas (colocar 8 reinas en un tablero de 8×8 de manera que no se amenacen entre ellas). Puede considerar que ya posee programada la función valido que recibe una solución parcial e indica si la misma es válida.
Ayuda: puede representar la solución con un arreglo. Ejemplo: [4, 6, 8, 2, 7, 1, 3, 5] indica que las reinas fueron colocadas en las posiciones (1, 4), (2, 6), (3, 8), etc.
b) ¿Qué técnica algorítmica utilizó?
Punto II
a) Muestre una implementación de la funcion heapify, que crea un heap sobre un arreglo, utilizando la función downheap (no hace falta que muestre la implementaciń de downheap)
b) ¿Qué diferencias tiene con la implementación de heapify utilizando la función upheap?
Punto III
¿Qué técnica utilizaría para resolver el problema del cambio, con un sistema de monedas de valores v1, v2, …, vn? ¿Por qué?
