Diferencia entre revisiones de «Práctica 3: Técnicas Algorítmicas (Algoritmos III)»
Línea 113: | Línea 113: | ||
==Ejercicio 03.08:== | ==Ejercicio 03.08:== | ||
<br>a) | <br>a) | ||
<br>b) | <pre> | ||
Nota: costo=int, pred: <int,int> | |||
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..f} 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; | |||
sig = <m,n>; | |||
mientras (sig.pred != <0,0>) // reconstruyo camino | |||
camino = sig.pred U camino; | |||
sig = sig.pred; | |||
</pre> | |||
<br>b) O(m*n) | |||
<br>c) | <br>c) | ||
La matriz R seria: | |||
<pre> | |||
2 10 13 17 | |||
7 10 14 19 | |||
8 10 12 13 | |||
11 14 18 18 | |||
</pre> | |||
==Ejercicio 03.09:== | ==Ejercicio 03.09:== | ||
<br>a) | <br>a) |
Revisión del 22:13 18 nov 2006
Ejercicio 03.01:
Version recursiva
int fib (n) si (n==0 || n==1) devolver n; sino devolver fib(n-1)+fib(n-2);
Version no recursiva
int fib (n) int mfib[n]; mfib[0] = 0; mfib[1] = 1; para i = 2..n fib[i] = fib[n-1]+fib[n+2]; devolver fib[n];
Ejercicio 03.02:
a) Para mover n discos desde i hasta j usando k:
Mover( inout i: Pila(nat), inout j: Pila(nat), inout k: Pila(nat), in n: nat ) Si n = 1 Apilar(tope(i),j) sino Mover(i, k, j, n-1) Mover(i, j, k, 1) Mover(k, j, i, n-1)
b)
c) O(2^n)
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!!)
Ejercicio 03.03:
a)
d_más_chica(Arreglo de puntos PS) Sort(PS,CoordX); si #PS = 2 devolver distancia(PS[1], PS[2]); sino dA = d_más_chica(P[1..n/2]); dB = d_más_chica(P[n/2+1..n]); dM = infinito para i=1..n/2 para j=n/2+1..n si d(P([i],P[j]) < dM dM = d(P([i],P[j]); devolver mínimo(dA, dB, dM);
b)
c) O(n log n)
Ejercicio 03.04:
a)
b)
Ejercicio 03.05:
i)
ii)
iii)
Ejercicio 03.06:
a)
Tomamos monedas de 25,10,5,1
Sol. Optima V = (v1,v2,..,vn) / v1 >= v2 >= .. >= vn
Sol. Optima G = (g1,g2,..,gn) / g1 >= g2 >= .. >= gn
qvq Sol. del Goloso G = V
Puede Pasar (G inc V) o (V inc G)? NO (suma de G = suma de V)
Vj < Gj (sino el goloso lo hubiera elegido)
Gj > Vj >= Vj+1 >= ... >= Vm
Ex. j / Vj != Gj Vi = Gi i<j
Gj | 25 | 10 | 5 |
---|---|---|---|
Vj | 10,5,1 | 5,1 | 1 |
1) Vj = 1 -> Vj+1 .. Vm
No puede ocurrir porque la suma tenia que ser la misma, tampoco puede haber un 10 o 5
2) Vj = 5
No puedo tener otro 5 (para eso pongo un 5), tampoco puede haber un 25 en Gj
3) Vj = 10
Tampoco, ya que 10,10,5 no seria optimo
Conclusion: V = G
b)
Ejercicio 03.07:
a)
Coef(n,k) si (calculado(n,k)) devolver mCoef[n,k]; si (k == 0 || k == n) res = 1; sino res = Coef(n-1, k-1) + Coef(n-1, k); mCoef[n,k] = res; devolver res;
b) O(n*k)
c) Mira vos
Ejercicio 03.08:
a)
Nota: costo=int, pred: <int,int> 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..f} 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; sig = <m,n>; mientras (sig.pred != <0,0>) // reconstruyo camino camino = sig.pred U camino; sig = sig.pred;
b) O(m*n)
c)
La matriz R seria:
2 10 13 17 7 10 14 19 8 10 12 13 11 14 18 18
Ejercicio 03.09:
a)
b)
Ejercicio 03.10:
Ejercicio 03.11:
Ejercicio 03.12:
Ejercicio 03.13:
a)
b)
dist("",v[1..m]) = m dist(u[1..n],"") = n dist(u[1..n],v[1..m]) = min (1+dist(u[1..n],v[1..m-1]), (insertar Vm) 1+dist(u[1..n-1],v[1..m]), (borrar Vm) if u[n]=v[m] then 0 else 1+ dist(u[1..n-1],v[1..m-1]) (cambiar/nada con Vm) )
Algoritmo:
M[0,j] = j
M[i,0] = i
M[i,j] = dist(u[1..i],v[1..j]) = min ( 1+M[i,j-1], .. )
Correctitud:
(Otro dia)
Ejercicio 03.14:
Ejercicio 03.15:
a)
b)
Ejercicio 03.16:
Ejercicio 03.17:
a)
b)
c)
Ejercicio 03.18:
a)
b)
c)