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 mfib[i] = mfib[n-1]+mfib[n-2]; devolver mfib[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) para demostrar la correctitud del algoritmo, lo podemos hacer por inducción basándonos que en n pasos nuestro algoritmo deja n-discos en la pila 3 de la forma correcta(es decir, el mas pesado debajo de todo y así con los de menor peso).
CB: Muevo un disco de la pila 1 a la pila 3, vale.
PI: Se asume que se dejaron n-1 discos correctamente ubicados en la pila 3, por lo que solo me queda mover un disco de la pila 1 a la 3, y como en esta ultima el orden era el correcto, vale para todo n.
Lo importante a notar es que el algoritmmo mantiene invariante lo que realiza paso a paso, es decir, hace un montón de movimientos entre los distintos discos pero al final de cuentas los termina dejando acomodas en orden correcto en la pila3.
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) usando Teorema Maestro tenemos: T(n) = 2 * T(n/2) + n^2, que entra en el tercer caso, quedándonos: O(n^2)
Ejercicio 03.04
Codigo c++
a) NOTA: Matriz es una clase que hice y que es muy larga como para poner aca.
void aux_3_4(Matriz &fix, int d, int h, int dia) {
if(h > d) {
aux_3_4(fix, d, (d+h)/2, dia/2);
aux_3_4(fix, (d+h)/2 + 1, h, dia/2);
int i = d;
int s = 0;
while(i <= (d+h)/2){
int j = (d+h)/2 + 1;
int c = s;
while(j <= h){
fix.asignar(i, j, dia - abs(c) - 1);
fix.asignar(j, i, dia - abs(c) - 1);
j++;
c++;
}
i++;
s--;
}
}
else
fix.asignar(d, d, 0); //la diagonal se rellena de ceros
}
void ejercicio_3_4_a(Matriz &fixture, int n){
aux_3_4(fixture, 0, n-1, n);
}
b)
Ejercicio 03.05
i) NO. Contraejemplo:
P1: s1=10, pi1=2
P2: s2=20, pi2= 8
Luego T = c*[2*10 + 8*(10 + 20)] = c*260 y si hubiesemos ordenado al reves, daria c*[8*20 + 2*(20 + 10)] = c*220 < T
ii) NO. Contraejemplo:
P1: pi1=2, s1=20
P2: pi2= 8, s2=10
Luego T = c*[2*20 + 8*(20 + 10)] = c*280 y si hubiesemos ordenado al reves, daria c*[8*10 + 2*(10 + 20)] = c*140 < T
iii) Funciona bien, pues lo ideal es s_i creciente y pi_i decreciente, entonces, pi_i/s_i decreciente
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) Si tomamos por ejemplo un vuelto de 15 centavos, el goloso nos daria el siguiente resultado: 15 = 1 moneda de 12 cent. + 3 de 1 cent, o sea 4 monedas.
Usando otro criterio, y asumiendo que cuento con monedas de 10 y 5 centavos, puedo dar el vuelto con 2 monedas: 15 = 1 moneda 10 centavos + 5 centavos.
Por lo tanto el criterio goloso no encuentra la solución óptima en este contexto.
Ejercicio 03.07
a) Pseudocodigo
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;
Codigo Cpp
#include <iostream>
#include <stdlib.h>
#include <cstdio>
using namespace std;
void ej7(int n);
void ej7(int n)
{
int tabla[100][100];
//PROCESAR
//O(n)
for(int i = 0; i<n+1; i++)
{
tabla[i][0] = 1;
tabla[i][i+1] = 0;
}
//O(n)
for(int i = 1; i<n+1; i++)
{
//O(i)
for(int j = 1; j<=i; j++)
{
tabla[i][j] = tabla[i-1][j-1] + tabla[i-1][j];
}
}
//MOSTRAR RESULTADOS
for(int i = 0; i<10; i++) {
cout << endl;
for(int j = 0; j<10; j++)
cout << tabla[i][j] <<" ";
}
cout << endl;
cout << endl;
cout << "Resultado: ";
for(int i = 0; i<n+1; i++)
{
cout << tabla[n][i] <<" ";
}
}
b) O(n*k)
c) Se pueden usar 2 variables auxiliares con el fin de ir guardandome los calculos necesarios para calcular cada termino de fibonacci, hago un pseudocodigo:
fibo(n)
si n == 0 o n == 1, devolver 1 //caso base
sino
termino1 = 1, termino2 = 1
para i desde 2 hasta n,
hacer:
suma = termino1 + termino2;
termino2 = termino1l;
termino1 = suma;
fin para
devolver termino1;
Como programación dinámica es botton up, voy construyendo la solución de menor termino hasta el n-esimo.
Ejercicio 03.08
a)
Nota: costo=int, pred: <int,int>
camMinimo(int M[m][n])
Tupla<costo, pred> R[m][n];
Lista<int, 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[f-1,c].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 (R<sig>.pred != <0,0>) // reconstruyo camino
camino = R<sig>.pred U camino;
sig = R<sig>.pred;
b) O(m*n)tanto temporal como espacial.
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) Primero pensemos en la funcion recursiva. TIP: veamos la version booleana y luego si sale, se puede hacer la version con los operandos.
i es el indice del vector v de valores a los cuales se les van a aplicar los operandos.
f(i,w) = { true si i=1 y W=v1
false si i = 1 y W !=v1
f(i-1,w-vi) || f(i-1, w/ri) || f(i-1, nroot(w)) //hacemos un or
b) Se puede ahcer pseudo-polinomial en O(nW)
Ejercicio 03.10
Codigo Cpp
#include <iostream>
#include <stdlib.h>
#include <cstdio>
using namespace std;
enum ciudades {NY = 0,
COL = 1, LOUIS = 2, NASH = 3,
KANSAS = 4, OMAHA = 5, DALLAS = 6,
SA = 7, DENVER = 8,
LA = 9};
void ej10();
int dist (ciudades c1, ciudades c2);
int dist (int c1, int c2);
void ej10()
{
//INICIALIZACION
int tabla[10];
tabla[NY]= 0;
// DIA 1
for (int i = 1; i<4; i++)
tabla[i] = dist(NY, (ciudades)i);
// DIA 2
for (int i = 4; i < 7; i++)
{
int minDist = dist(i,1) + tabla[1];
for (int j = 2; j<4; j++)
if (minDist > dist(i,j) + tabla[j])
minDist = dist(i,j) + tabla[j];
tabla[i] = minDist;
}
// DIA 3
for (int i = 7; i < 9; i++)
{
int minDist = dist(i,4) + tabla[4];
for (int j = 5; j<7; j++)
if (minDist > dist(i,j) + tabla[j])
minDist = dist(i,j) + tabla[j];
tabla[i] = minDist;
}
// DIA 4
tabla[9] = (dist(9,7) + tabla[7] < dist(9,8) + tabla[8])
? dist(9,7) + tabla[7]
: dist(9,8) + tabla[8];
// MOSTRAR RESULTADOS
for (int i = 0; i<10; i++)
{
cout << endl << i << ": " << tabla[i];
}
cout << endl << endl << "Valor final a LA: " << tabla[9] << endl;
}
int dist (int c1, int c2)
{
return dist ((ciudades)c1, (ciudades)c2);
}
int dist (ciudades c1, ciudades c2)
{
if (c1 > c2)
{
ciudades aux;
aux = c1;
c1 = c2;
c2 = aux;
}
else if (c1 == c2)
{
return 0;
}
if (c1 == NY)
{
switch (c2)
{
case COL: return 550;
case NASH: return 900;
case LOUIS: return 770;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == COL)
{
switch (c2)
{
case KANSAS: return 680;
case OMAHA: return 790;
case DALLAS: return 1050;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == NASH)
{
switch (c2)
{
case KANSAS: return 580;
case OMAHA: return 760;
case DALLAS: return 660;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == LOUIS)
{
switch (c2)
{
case KANSAS: return 510;
case OMAHA: return 700;
case DALLAS: return 830;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == KANSAS)
{
switch (c2)
{
case DENVER: return 610;
case SA: return 790;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == OMAHA)
{
switch (c2)
{
case DENVER: return 540;
case SA: return 940;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == DALLAS)
{
switch (c2)
{
case DENVER: return 790;
case SA: return 270;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == DENVER)
{
switch (c2)
{
case LA: return 1030;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else if (c1 == SA)
{
switch (c2)
{
case LA: return 1390;
default:
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
else
{
cout << "Error en dist: " << c1 << " y " << c2;
return 0;
}
}
Ejercicio 03.11
Codigo Cpp
#include <iostream>
#include <stdlib.h>
#include <cstdio>
using namespace std;
void ej11();
void ej11()
{
// INICIALIZACIONES
int costo[3] = {10*100, 10*100, 12*100};
int req[3] = {2, 5, 8};
int costoStock = 150;
int costoInit = 250;
int tablaCost[3][9];
int tablaPred[3][9];
for (int i = 0; i<3; i++)
{
for (int j = 0; j < 9; j++)
{
tablaCost[i][j] = 0;
tablaPred[i][j] = 0;
}
}
// PROCESO
for (int mes = 0; mes < 3; mes++)
{
for (int prod = req[mes]; prod < 9; prod++)
{
if (mes == 0)
{
tablaCost[mes][prod] = costo[mes] * prod + costoInit;
}
else
{
int costoMin = (prod - req[mes-1]) * costoStock + tablaCost[mes-1][prod];
int pred = prod;
// if (mes == 2) cout << "Stock mes anterior " << prod << "; costo " << costoMin << endl;
for (int stock = req[mes-1]; stock < prod; stock++)
{
int costoAct = (stock - req[mes-1])* costoStock;
costoAct+= costo[mes] * (prod-stock) + costoInit;
costoAct+= tablaCost[mes-1][stock];
// if (mes == 2) cout << "Mes " << mes << " a producir " << prod << ". Stock mes anterior " << stock << "; costo " << costoAct << endl;
if (costoMin > costoAct)
{
costoMin = costoAct;
pred = stock;
}
}
tablaCost[mes][prod] = costoMin;
tablaPred[mes][prod] = pred;
}
}
}
// MOSTRAR RESULTADOS
cout << endl << "Tabla de Prog Dinamica: " << endl;
for(int i = 0; i<9; i++) {
cout << endl;
for(int j = 0; j<3; j++)
cout << tablaCost[j][i] <<" ";
}
cout << endl << endl << "Tabla de Predecesores: " << endl;
for(int i = 0; i<9; i++) {
cout << endl;
for(int j = 0; j<3; j++)
cout << tablaPred[j][i] <<" ";
}
cout << endl << endl << "Resultado: " << tablaCost[2][8] << endl;
cout << endl << "Esquema de produccion: " << endl;
int mesAct = 2;
int prodAct = 8;
while (mesAct >= 0)
{
// cout << "Prod Act " << prodAct;
cout << "Mes " << mesAct +1 << " producir " << (prodAct - tablaPred[mesAct][prodAct]) * 100 << " unidades." << endl;
prodAct = tablaPred[mesAct][prodAct];
mesAct--;
}
cout << endl;
}
Ejercicio 03.12
Ejercicio 03.13
a) no es optimo ya que se puede realizar con solo 2 operaciones. Insertando una 'c' entre las 'b' y borrando la ultima '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)
