ALGORITMOS PYTHON-páginas-55

Vista previa del material en texto

[249]
c. los elementos son los siguientes:
Elemento Peso Beneficio Cantidad
frutas 0.73 50 8
carpa 3 90 2
termo stanley 1.5 75 3
sable de luz 1.3 175 1
mapa holograma 1.1 93 1
traje Jedi 0.9 87 4
bolsa de créditos galácticos 5 100 3
lata de alimento 0.79 75 10
galletitas 1 60 15
yerba canarias 0.64 70 7
pan 2.5 65 5
botella de agua 1.9 99 5
soga 2.3 40 3
mate 0.8 75 6
blaster 8.3 85 2
3. Desarrollar un algoritmo que indique los alimentos que se deben llevar para un campamento, 
suponiendo que todos los alimentos son fraccionables y la capacidad de la mochila es de 21 
kilos –no hay límite respecto de las cantidades de cada uno–, pero además se debe tener en 
cuenta la duración de dichos alimentos antes de ponerse en mal estado –considere 30 días 
como máximo –:
Alimento Peso Beneficio Duración
arroz 5 250 30
manzana 3 231 19
caramelo 15 20 20
papa 6 215 23
galletita 10 50 30
fideo 7 175 30
cereales 13 150 15
zanahoria 4 245 20
choclo 7 166 27
queso 8 207 10
helado 9 90 0
lechuga 10 188 5
pollo 6 235 1
aceituna 17 117 11
pan 4 220 7
[250]
fiambre 15 124 1
tomate 9 193 6
carne 10 190 1
atún 9 230 1
4. Implemente un algoritmo para resolver el problema de la mochila en el cual, además de conside-
rar el beneficio y el peso de cada elemento, se considere la cantidad de espacios que ocupa cada 
uno de estos. Entonces la mochila además de tener un peso máximo tendrá una cantidad máxi-
ma de lugares –considere que los objetos no son fraccionables para simplificar el problema–.
5. Resuelva el problema de colocar las n-reinas sin que las mismas se amenacen, para tableros de 
las siguientes dimensiones –solo es necesario encontrar una de las soluciones –:
a. 4 reinas tablero de 4 x 4;
b. 8 reinas tablero de 8 x 8;
c. 16 reinas tablero de 16 x 16.
6. Desarrollar un algoritmo del tipo divide y vencerás, que permita resolver el producto matrices 
de [2 x 2] y [3 x 3]. Este algoritmo debe ser del orden de O(n2) por lo cual debe evitar el tercer 
ciclo, sabiendo que las matrices solo pueden ser de las dimensiones indicadas.
7. Implementar un algoritmo para la multiplicación de enteros grandes que permita configurar 
el tamaño mínimo de la partición de los números enteros –utilizando la técnica divide y vence-
rás–. El algoritmo debe aceptar números de distinto largo, pruebe con los siguientes tamaños 
de partición si el algoritmo funciona: 2, 3, 5, 7.
8. Resuelva el problema de la torre de Hanói –ejercicio 23 de la guía de recursividad– de manera 
iterativa utilizando una de las técnicas vistas –a excepción de divide y vencerás cuyo mecánica 
es recursiva–.
9. Implementar un algoritmo del tipo divide y vencerás, que permita calcular la potencia de un 
número n elevado a la k, es decir (nk) de manera eficiente.
10. Implementar un algoritmo que permita elaborar el calendario de los torneos de básquet y vó-
ley de todos los equipos que asistieron al campus de verano, teniendo en cuenta las siguien-
tes cuestiones:
a. durante el torneo todos los equipos deben enfrentarse contra todos lo demás;
b. cada equipo jugara un partida por día;
c. Los equipos de básquet son 10 y los de vóley 7.
[251]
11. Implementar un algoritmo que permita resolver el problema del turista, el cual consiste en 
visitar todas las ciudades una sola vez y volver a la ciudad de partida recorriendo la menor 
distancia posible. Contemple lo siguiente:
a. las ciudades son: Concepción del Uruguay (Argentina), Rodas (Grecia), Tulum (México), 
Phuket (Tailandia), Tokio (Japón), Atenas (Grecia), Orlando (Estados Unidos), Santiago 
(Chile), Moscú (Rusia), Bombinhas (Brasil), Londres (Reino Unido), Paris (Francia), Sídney 
(Australia), Berlín (Alemania);
b. debe considerar las distancias reales en kilómetros;
c. ciudad de salida Concepción del Uruguay;
d. ahora además de considerar la menor distancia, mejore el algoritmo para que también 
considere el menor costo.
12. Nick Fury se encuentra en los cuarteles generales de S.H.I.E.L.D. y debe visitar a varios su-
perhéroes para convencerlos de unirse para formar un grupo de vengadores, dado que es un 
asunto de suma importancia nos solicita implementar un algoritmo que permita determinar el 
recorrido de menor distancia –el menor posible, no importa que sea el más óptimo– y terminar 
dicho recorrido de vuelta en los cuarteles (solo se puede pasar una vez por cada lugar).
a. Considere los siguientes superhéroes: S.H.I.E.L.D. (a), Tony Stark (b), Natasha Romanoff 
(c), Steve Rogers (d), Carol Danvers (e), Bruce Banner (f ), Scott Lang (g), Peter Quill (h);
b. las distancias entre la localización de cada superhéroe está cargada en la siguiente matriz:
a b c d e f g h
a 675 400 166 809 720 399 233
b 675 540 687 179 348 199 401
c 400 540 107 752 521 385 280
d 166 687 107 111 540 990 361
e 809 179 752 111 206 412 576
f 720 348 521 540 206 155 621
g 399 199 385 990 412 155 100
h 233 401 280 361 576 621 100
13. Resuelva el problema del laberinto –ejercicio 22 de la guía de recursividad– de manera iterati-
va, utilice la técnica que crea más conveniente.
14. Desarrollar un algoritmo numérico iterativo que permita calcular el método de la bisección de 
una función f(x).
15. Desarrollar un algoritmo numérico iterativo que permita calcular el método de la secante de 
una función f(x).
[252]
16. Desarrollar un algoritmo numérico iterativo que permita calcular el método de Newton-Raph-
son de una función f(x).
17. Comparar los tres algoritmos anteriores para resolver la siguiente función: x3 + x +16 = 0, res-
pecto de la cantidad de iteraciones necesarias por cada método para converger. ¿Cuánto es la 
diferencia en decimales entre las distintas soluciones?
Método Cantidad de iteraciones Solución
Secante
Bisección
Newton-Raphson