Diferencia entre revisiones de «Práctica 3: Técnicas Algorítmicas (Algoritmos III)»
(No se muestran 4 ediciones intermedias del mismo usuario) | |||
Línea 1: | Línea 1: | ||
==Ejercicio 03.01 | ==Ejercicio 03.01== | ||
Version recursiva | Version recursiva | ||
Línea 35: | Línea 35: | ||
Complejidad temporal O(n), complejidad espacial O(1) | Complejidad temporal O(n), complejidad espacial O(1) | ||
==Ejercicio 03.02 | ==Ejercicio 03.02== | ||
<br>a) Para mover n discos desde i hasta j usando k: | <br>a) Para mover n discos desde i hasta j usando k: | ||
<pre> | <pre> | ||
Línea 50: | Línea 50: | ||
<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!!) | ||
==Ejercicio 03.03 | ==Ejercicio 03.03== | ||
<br>a) | <br>a) | ||
<pre> | <pre> | ||
Línea 70: | Línea 70: | ||
<br>c) O(n log n) | <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) | <br>i) | ||
<br>ii) | <br>ii) | ||
<br>iii) | <br>iii) | ||
==Ejercicio 03.06 | ==Ejercicio 03.06== | ||
<br>a) | <br>a) | ||
<br>Tomamos monedas de 25,10,5,1 | <br>Tomamos monedas de 25,10,5,1 | ||
Línea 108: | Línea 108: | ||
<br>b) | <br>b) | ||
==Ejercicio 03.07 | ==Ejercicio 03.07== | ||
<br>a) | <br>a) Pseudocodigo | ||
<pre> | <pre> | ||
Coef(n,k) | Coef(n,k) | ||
Línea 123: | Línea 123: | ||
devolver res; | devolver res; | ||
</pre> | </pre> | ||
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] <<" "; | |||
} | |||
} | |||
<br>b) O(n*k) | <br>b) O(n*k) | ||
<br>c) Mira vos | <br>c) Mira vos | ||
==Ejercicio 03.08 | ==Ejercicio 03.08== | ||
<br>a) | <br>a) | ||
<pre> | <pre> | ||
Línea 154: | Línea 205: | ||
sig = sig.pred; | sig = sig.pred; | ||
</pre> | </pre> | ||
<br>b) O(m*n) | <br>b) O(m*n)tanto temporal como espacial. | ||
<br>c) | <br>c) | ||
La matriz R seria: | La matriz R seria: | ||
Línea 164: | Línea 215: | ||
</pre> | </pre> | ||
==Ejercicio 03.09 | ==Ejercicio 03.09== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 03.10:== | ==Ejercicio 03.10== | ||
==Ejercicio 03.11:== | |||
==Ejercicio 03.12 | Codigo Cpp | ||
==Ejercicio 03.13 | |||
#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== | |||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 191: | Línea 527: | ||
<br>(Otro dia) | <br>(Otro dia) | ||
==Ejercicio 03.14 | ==Ejercicio 03.14== | ||
==Ejercicio 03.15 | ==Ejercicio 03.15== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 03.16 | ==Ejercicio 03.16== | ||
==Ejercicio 03.17 | ==Ejercicio 03.17== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 03.18 | ==Ejercicio 03.18== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 03.19 | ==Ejercicio 03.19== |
Revisión del 15:11 20 abr 2007
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
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) 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) 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)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)
b)
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)
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)