Edición de «Práctica 3: Técnicas Algorítmicas (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 51: | Línea 51: | ||
Mover(k, j, i, n-1) | Mover(k, j, i, n-1) | ||
</pre> | </pre> | ||
<br>b) | <br>b) | ||
<br>c) O(2^n) | <br>c) O(2^n) | ||
<br>d) Como son 64 discos, el número de movimientos es 2^64 - 1 = 18446744073709551615. Si suponemos que los monjes tienen la suficiente habilidad como para hacer un movimiento en un segundo, en un día harán 60*60*24 movimientos. Y en un año de 365 días: 60*60*24*365. Dividimos el número de movimientos por el resultado de la operación anterior y nos debe dar, aproximadamente, medio billón de años. Sólo falta averiguar cuantos años se estiman que el hombre lleva sobre la tierra y sabremos el tiempo que le queda sobre ella (TSUNAMI DE CHANES!!) | <br>d) Como son 64 discos, el número de movimientos es 2^64 - 1 = 18446744073709551615. Si suponemos que los monjes tienen la suficiente habilidad como para hacer un movimiento en un segundo, en un día harán 60*60*24 movimientos. Y en un año de 365 días: 60*60*24*365. Dividimos el número de movimientos por el resultado de la operación anterior y nos debe dar, aproximadamente, medio billón de años. Sólo falta averiguar cuantos años se estiman que el hombre lleva sobre la tierra y sabremos el tiempo que le queda sobre ella (TSUNAMI DE CHANES!!) | ||
Línea 76: | Línea 73: | ||
</pre> | </pre> | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) O(n log n) | ||
==Ejercicio 03.04== | ==Ejercicio 03.04== | ||
Línea 159: | Línea 156: | ||
Conclusion: V = G | Conclusion: V = G | ||
<br>b) | <br>b) | ||
==Ejercicio 03.07== | ==Ejercicio 03.07== | ||
Línea 230: | Línea 225: | ||
<br>b) O(n*k) | <br>b) O(n*k) | ||
<br>c) | <br>c) Mira vos | ||
==Ejercicio 03.08== | ==Ejercicio 03.08== | ||
Línea 253: | Línea 232: | ||
Nota: costo=int, pred: <int,int> | Nota: costo=int, pred: <int,int> | ||
camMinimo(int M[m][n]) | camMinimo(int M[m][n]) | ||
Tupla<costo, pred> R[m][n]; | |||
Lista<int> camino; | |||
R(1,1)=< M[1,1], <0,0> >; | |||
R(f,1)=< Σ{i=1..f} M[i,1], <f-1,1> >; | |||
R(1,c)=< Σ{i=1..c} M[1,i], <1,c-1> >; | |||
para f=2..m | |||
para c=2..n | |||
si (R[f,c-1].costo < R[c-1,f].costo) | |||
R[f,c].costo = R[f,c-1].costo+M[f,c]; | |||
R[f,c].pred = <f,c-1>; | |||
sino | |||
R[f,c].costo = R[f-1,c].costo+M[f,c]; | |||
R[f,c].pred = <f-1,c>; | |||
res = R[m,n].costo; | res = R[m,n].costo; | ||
sig = <m,n>; | sig = <m,n>; | ||
mientras ( | mientras (sig.pred != <0,0>) // reconstruyo camino | ||
camino = | camino = sig.pred U camino; | ||
sig = | sig = sig.pred; | ||
</pre> | </pre> | ||
<br>b) O(m*n)tanto temporal como espacial. | <br>b) O(m*n)tanto temporal como espacial. | ||
Línea 287: | Línea 266: | ||
==Ejercicio 03.09== | ==Ejercicio 03.09== | ||
<br>a) | <br>a) | ||
<br>b) | |||
<br>b) | |||
==Ejercicio 03.10== | ==Ejercicio 03.10== | ||
Línea 586: | Línea 557: | ||
==Ejercicio 03.12== | ==Ejercicio 03.12== | ||
==Ejercicio 03.13== | ==Ejercicio 03.13== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<pre> | <pre> |