Ejercicio 1

func prob1(a: array de [n] Entero; c: Entero) dev (r: Entero)
var
inf, sup, i: Entero
fin: Lógico
alg
fin := falso //1 OE
inf := 1 //1 OE
sup:=n //1 OE
mientras sup >= inf Y NO fin //2 OE
i := (inf + sup) div 2 //3 OE
si a[i] = c: //2 OE
<> := <> //2 OE
| a[i] > c: //2 OE
sup := i – 1 //2 OE
| otras: //2 OE
inf := i + 1 //2 OE
fsi
fmientras
si NO fin: //1 OE
r := 0 //1 OE
fsi
fin

(a) Calcular el tiempo de ejecución en los casos mejor, peor y medio.

Caso Mejor:

T(n) = 3+1+1+1=5 OE

Caso Peor:

T(n)= 3 + ((sum i=1,n) 2+3+2+2+2) +2+1+1=11n+7

Caso Medio:

T(n) = 3 + 11n/2 + (12n+4)/(n+1)

El 11n/2, sale del cálculo del /IB y el (12n+4)/(n+1) es el /CF

No estoy seguro del que el /CF se tenga que calcular.


(b) Dar las cotas asintóticas para esos tiempos.

Problema Ventas P1

Descripción:

Una tienda establece una filosofía de ofertas dependiendo de la época del año y de otras
cuestiones internas:

• Dependiendo del mes que se realizan las compras se le asignará un porcentaje de descuento:

1. PorcentajeDescuento si ocurre en los primeros 6 meses del año.
2. Una cantidad absoluta (DescuentoAbsolutoSobreUmbral) si ocurre en los últimos 6 meses del año.

• Implementa la interfaz IEstrategiaFijarPreciosVenta, y las clases descuentoAbsolutoSobreUmbral y PorcentajeDescuento.
• Completa el método realizarVenta() de la clases Ventas. Dicho método resolverá el problema con los descuentos en función del mes del año tal como se ha explicado.

Solución:

public class Principal {
public static void main(String[] args) {
Fecha f = new Fecha(20, 10, 2004);
// creamos una venta
Ventas v = new Ventas(210, f);
int valorFinal = v.realizarVenta();
System.out.println(valorFinal);

Fecha f1 = new Fecha(20, 5, 2004);
// creamos una venta
Ventas v1 = new Ventas(210, f1);
int valorFinal1 = v1.realizarVenta();
System.out.println(valorFinal1);
}
}

public class Fecha {
private int dia=0;
private int mes=0;
private int año=0;

public Fecha(int dia, int mes, int año){
if(dia < 32 && mes < 13){
this.dia = dia;
this.mes = mes;
this.año = año;
}else
System.out.println("Fecha incorrecta");
}
public int getMes(){
return this.mes;
}
public int getDia(){
return this.dia;
}
public int getAño(){
return this.año;
}
}

public class Ventas {

private Fecha fecha;
private IEstrategiaFijarPreciosVenta estrategia;
private int cantidad;

public Ventas(int cantidad, Fecha f){
this.cantidad = cantidad;
this.fecha = f;
}
public int realizarVenta(){
//TODO
int res;
if(this.fecha.getMes() < 7){
this.estrategia = new PorcentajeDescuento((float) 0.15);
res=this.estrategia.getTotalVenta(this.cantidad);
}else{
this.estrategia = new DescuentoAbsolutoSobreUmbral(3,(float)0.25);
res=this.estrategia.getTotalVenta(this.cantidad);
}
return res;

}
public int getTotalAntesDto(){
return cantidad;
}
}

public interface IEstrategiaFijarPreciosVenta {
int getTotalVenta(int in);
}

public class PorcentajeDescuento implements IEstrategiaFijarPreciosVenta{

private float p;
public PorcentajeDescuento(float p){
this.p=p;
}

public int getTotalVenta(int in) {
return (int) (in*(1-p));
}

}


public class DescuentoAbsolutoSobreUmbral implements IEstrategiaFijarPreciosVenta{
private float porcentaje;
private int umbral;

public DescuentoAbsolutoSobreUmbral(int umbral, float porcentaje){
this.umbral=umbral;
this.porcentaje=porcentaje;
}
public int getTotalVenta(int in) {
int res = (int)(in*(1-this.porcentaje));
if(res
res=this.umbral;
return res;

}

}

Problema Cafetería P1

Problema de Patrón-Plantilla de la práctica 1 de ADA

Descripción:

• Una cafetería siempre utiliza el mismo procedimiento para poner café, pero los ingredientes concretos dependerán del tipo de café.
• Implementa la clase PreparaCafe y la clase ConLeche que hereda de ella.
• Completa el método main de la clase Cafeteria, para imprimir también la secuencia de acciones para preparar un café con leche

Solución:

public class Cafeteria {

/**
* @param args
*/
public static void main(String[] args) {
//TODO
ConLeche c1=new ConLeche();
c1.prepararCafe();
}

}


public abstract class PrepararCafe {
protected abstract void echarCafe();
protected abstract void añadirLeche();
protected abstract void añadirEdulcorante();

public void prepararCafe(){
echarCafe();
añadirLeche();
añadirEdulcorante();
}


}


public class ConLeche extends PrepararCafe{
public void echarCafe(){
System.out.println("Café natural");
};
public void añadirLeche(){
System.out.println("Con Leche");
};
public void añadirEdulcorante(){
System.out.println("Con azúcar");
};

}


public class Descafeinado extends PrepararCafe{
public void echarCafe(){
System.out.println("Café descafeinado");
};
public void añadirLeche(){
System.out.println("Con Leche");
};
public void añadirEdulcorante(){
System.out.println("Con azúcar");
};
}


public class Solo extends PrepararCafe{
public void echarCafe(){
System.out.println("Café natural");
};
public void añadirLeche(){
System.out.println("Sin Leche");
};
public void añadirEdulcorante(){
System.out.println("Con sacarina");
};
}

Problema Torres de Hanoi P1

Código que resuelve el problema de las Torres de Hanoi, para cualquier número de niveles.

Descripción:

Dada una serie de discos y tres postes: A, B y C, en el poste A se colocan n discos de diámetro diferente de tal manera que un disco de diámetro mayor siempre queda debajo de uno de diámetro menor. El objetivo es mover los discos al poste C usando B como auxiliar.

Se deben cumplir las siguientes restricciones:

• Sólo se puede mover un disco a la vez
• Los discos deben estar colocados siempre en uno de los postes
• Nunca puede estar un disco mayor sobre otro menor

Solución:

private static void hanoi(int n, String inicial, String auxiliar, String fin) {
if (n > 0) {
hanoi(n-1,inicial, fin, auxiliar);
System.out.println("Mover disco " + n + " de " + inicial + " a "
+ fin);
hanoi(n-1, auxiliar,inicial, fin);
}
}

Problema Robot P1

Problema que calcúla el número de caminos posibles para llegar en una matriz desde el punto 1,1 hasta el extremo opuesto.

El robot sólo puede ir dos posiciones hacia abajo o tres a la derecha.

Descripción:

Caminos para un Robot. Partiendo de una matriz de n*m , un robot situado en dicha matriz puede hacer diferentes movimientos. Los movimientos permitidos son tres posiciones a la derecha o dos posiciones abajo. Si el origen del robot es siempre la casilla de más arriba a la izquierda, y tiene que llegar a la de más abajo a la derecha, implemente un algoritmo basado en la recursividad que muestre todos los caminos posibles que puede realizar el robot.

Solución:

private static int robot(int n, int m) {
int res;
if((n==4 && m==1)||(n==1 && m==3))
res=1;
else if(n==1 && m>2)
res=robot(n,m-2);
else if (m==1 && n>3)
res=robot(n-3,m);
else if(n<4 || m<3)
res=0;
else
res=robot(n-3,m)+robot(n,m-2);
return res;
}

Problema Fibonacci P1

Descripción:

Diseña un programa recursivo final que calcule el nésimoelemento de la sucesión de Fibonacci.

• Según se ha visto, la técnica consiste en usar parámetros acumuladores, en el presente problema necesitamos dos: uno que almacene fib(n-2) (lo llamaremos f0), y otro que almacene fib(n-1) (lo llamaremos f1).
• La función principal llamará a una auxiliar dándole valores iniciales a los acumuladores. También usaremos un parámetro i, que se incrementará en cada llamada.
• El caso base: i = n, devolveremos el acumulador que contenga f1 + f0
• Caso recursivo: con cada acumulador ocurrirá la transformación esperada al pasar de n a n+1
• Diseña un programa iterativo que calcule el n-ésimo elemento de la sucesión de Fibonacci, transformando el recursivo final del ejercicio anterior.
• Para resolver este ejercicio nos basaremos en una transparencia anterior donde se mostraba la transformación a iterativo del factorial recursivo final.
  

Solución:

private static long fibRec0(long n) {
long r;

if (n <= 1) {
r = n;
} else {
r = fibRec0(n - 1) + fibRec0(n - 2);
}
return r;
}

private static long fibFinal(long n) {
long res = 0;
if (n < 2) {
// TODO
res=n;
} else {
// TODO
res=fibFinalAux(n,1,0,1);
}
return res;
}

private static long fibFinalAux(long n, long i, long f0, long f1) {
long res = 0;

if (i == n) {
// TODO
res=f1;
} else {
// TODO
res=fibFinalAux(n,i+1,f1,f0+f1);
}
return res;
}

private static long fibIter(long n) {
long f0 = 0;
long f1 = 1;
long i = 1;
long faux = 0;
long res = 0;

if (n < 2) {
// TODO
res=n;
} else {
while (i < n) {
// TODO
faux=f1;
f1+=f0;
f0=faux;
i++;
}
// TODO
res=f1;
}
return res;
}
}

Problema ¿qué hace éste programa? P1

private static void queHace(String cad, int i) {
if ( i< cad.length()) {
queHace(cad, i + 1);
System.out.print(cad.charAt(i));
}
}

Éste programa muestra la cadena de carácteres al revés, ejemplo:

Hola Mundo

odnuM aloH

Problema Euclides P1

Descripción:
Usa el algoritmo de Euclides para encontrar el máximo común divisor (mcd) de dos números a y b. Se basa en que si a > b, entonces el mcd de a y b es el mismo que de b y a – b. Si b > a, será el mismo que de a y b – a. Esta regla se debe aplicar sucesivamente hasta que a sea igual a b, y entonces se cumplirá que mcd = a = b.

Para plantearnos el problema estudiamos:

1. Casos bases. Sólo hay uno: a y b coinciden. Claramente devolvemos a (o b)
   
2. Casos recursivos. Hay dos: a > b y a < b. En cada caso haremos la llamada recursiva según la definición dada más arriba
   

Solución:

private static int mcd(int a, int b) {
int mcd = 0;
if (a == b) {
mcd=a;
} else if (a > b) {
mcd=mcd(a-b,b);
} else {
mcd=mcd(a,b-a);
}
return mcd;
}

Problema Conejos P1

Descripción:

Un granjero ha comprado n parejas de conejos para criarlos y luego venderlos. Si cada pareja de conejos produce una nueva pareja cada mes y la nueva tarda un mes más en ser también productiva, realice un algoritmo recursivo para conocer cuántas parejas de conejos podrá vender a los m meses de comenzar la producción.

Solución:

Entendida como sucesión de Fibonacci:

private static int conejos(int meses, int conejos) {
int f0=0;
int f1=conejos;
int auxf;
int aux=meses - 1;
while(aux > 0){
auxf=f1;
f1+=f0;
f0=auxf;
aux--;
}
return f1;

}


Entendida como exponencial:

private static int conejos(int meses, int conejos) {
int res=conejos;
for (int i=0;i < meses;i++)
res*=2;
return res;

}