Edición de «Práctica 3: Técnicas Algorítmicas (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

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:
{{Back|Algoritmos y Estructuras de Datos III}}
==Ejercicio 03.01:==
 
<table><tr><td>
==Ejercicio 03.01==


Version recursiva
Version recursiva
Línea 11: Línea 10:
devolver fib(n-1)+fib(n-2);
devolver fib(n-1)+fib(n-2);
</pre>
</pre>
</td><td>


Version no recursiva
Version no recursiva
Línea 18: Línea 19:
para i = 2..n
para i = 2..n
mfib[i] = mfib[n-1]+mfib[n-2];
fib[i] = fib[n-1]+fib[n+2];
devolver mfib[n];
devolver fib[n];
</pre>
</pre>


Complejidad temporal O(n), complejidad espacial O(n)
</td></tr></table>


Otra manera no recursiva
==Ejercicio 03.02:==
<pre>
<br>a)
int fib (n)
<br>b)
if ( n <= 1 ) devolver 1
<br>c)
else
<br>d)
            int x = 1;
==Ejercicio 03.03:==
            int y = 1;
            para i = 2..n
suma = x + y;
                y = x;
                x= suma;
    devolver  suma
</pre>
 
Complejidad temporal O(n), complejidad espacial O(1)
 
==Ejercicio 03.02==
<br>a) Para mover n discos desde i hasta j usando k:
<pre>
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)
</pre>
<br>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.
<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!!)
 
==Ejercicio 03.03==
<br>a)
<br>a)
<pre>
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);
</pre>
<br>b)
<br>b)
<br>c) usando Teorema Maestro tenemos:  T(n) = 2 * T(n/2) + n^2, que entra en el tercer caso, quedándonos: O(n^2)
<br>c)
 
==Ejercicio 03.04:==
==Ejercicio 03.04==
<br>a)
Codigo c++
<br>a) NOTA: Matriz es una clase que hice y que es muy larga como para poner aca.
<pre>
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);
}
</pre>
<br>b)
<br>b)
 
==Ejercicio 03.05:==
==Ejercicio 03.05==
<br>i)
<br>i) NO. Contraejemplo:
<br>ii)
        P1: s1=10, pi1=2
<br>iii)
        P2: s2=20, pi2= 8
==Ejercicio 03.06:==
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
 
 
<br>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
 
<br>iii) Funciona bien, pues lo ideal es s_i creciente y pi_i decreciente, entonces, pi_i/s_i decreciente
 
==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 159: Línea 70:
Conclusion: V = G
Conclusion: V = G


<br>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.
<br>b)
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==
==Ejercicio 03.07:==
<br>a) Pseudocodigo
<br>a)
<pre>
<br>b)
Coef(n,k)
<br>c)
si (calculado(n,k))
==Ejercicio 03.08:==
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;
</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>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:
 
<pre>
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.
</pre>
 
==Ejercicio 03.08==
<br>a)
<br>a)
<pre>
<br>b)
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;
</pre>
<br>b) O(m*n)tanto temporal como espacial.
<br>c)
<br>c)
La matriz R seria:
==Ejercicio 03.09:==
<pre>
<br>a)
2 10 13 17
<br>b)
7 10 14 19
==Ejercicio 03.10:==
8 10 12 13
==Ejercicio 03.11:==
11 14 18 18
==Ejercicio 03.12:==
</pre>
==Ejercicio 03.13:==
 
<br>a)
==Ejercicio 03.09==
<br>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
 
<br>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==
<br>a) no es optimo ya que se puede realizar con solo 2 operaciones. Insertando una 'c' entre las 'b' y borrando la ultima 'a'.
<br>b)
<br>b)
<pre>
<pre>
Línea 606: Línea 107:
<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:==
 
 
[[Category: Prácticas]]
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página:

Obtenido de «https://www.cubawiki.com.ar/index.php/Práctica_3:_Técnicas_Algorítmicas_(Algoritmos_III)»