Práctica 3: Técnicas Algorítmicas (Algoritmos III)

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];

Complejidad temporal O(n), complejidad espacial O(n)

Otra manera no recursiva

int fib (n)
	if ( n <= 1 ) devolver 1	
	else
           		int x = 1; int y = 1;
            para i = 2..n
			suma = x + y; y = x; x= suma;
	devolver  suma

Complejidad temporal O(n), complejidad espacial O(1)

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

Valores Posibles

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..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;				
	
	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.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.15:

a)
b)

Ejercicio 03.17:

a)
b)
c)

Ejercicio 03.18:

a)
b)
c)