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 1: | Línea 1: | ||
==Ejercicio 03.01== | ==Ejercicio 03.01== | ||
Línea 18: | Línea 16: | ||
para i = 2..n | para i = 2..n | ||
mfib[i] = mfib[n-1]+mfib[n | mfib[i] = mfib[n-1]+mfib[n+2]; | ||
devolver mfib[n]; | devolver mfib[n]; | ||
</pre> | </pre> | ||
Línea 29: | Línea 27: | ||
if ( n <= 1 ) devolver 1 | if ( n <= 1 ) devolver 1 | ||
else | else | ||
int x = 1; int y = 1; | |||
para i = 2..n | para i = 2..n | ||
suma = x + y; y = x; x= suma; | |||
devolver suma | |||
</pre> | </pre> | ||
Línea 51: | Línea 46: | ||
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 68: | ||
</pre> | </pre> | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) O(n log n) | ||
==Ejercicio 03.04== | ==Ejercicio 03.04== | ||
<br>a) | |||
<br>a) | |||
<br>b) | <br>b) | ||
==Ejercicio 03.05== | ==Ejercicio 03.05== | ||
<br>i) NO. Contraejemplo: | <br>i) NO. Contraejemplo: | ||
Línea 159: | Línea 120: | ||
Conclusion: V = G | Conclusion: V = G | ||
<br>b) | <br>b) | ||
==Ejercicio 03.07== | ==Ejercicio 03.07== | ||
Línea 230: | Línea 189: | ||
<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 196: | ||
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 230: | ||
==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 521: | ||
==Ejercicio 03.12== | ==Ejercicio 03.12== | ||
==Ejercicio 03.13== | ==Ejercicio 03.13== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<pre> | <pre> | ||
Línea 620: | Línea 555: | ||
<br>c) | <br>c) | ||
==Ejercicio 03.19== | ==Ejercicio 03.19== | ||