Practica 5 ASPP

.386
.MODEL flat
OPTION CASEMAP:N
.CODE
PUBLIC _int2fp
_int2fp PROC
; Cuerpo del pro
push ebp
mov ebp,esp
push eax
push ebx
push ecx
push edx

xor eax,eax
xor ebx,ebx
xor ecx,ecx
xor edx,edx

mov ecx, [ ebp
mov eax, [ ebp

cmp eax,0
je Cero

cmp eax,0
jge Bucle
mov dh,1
neg eax

Bucle: cmp eax
je Fb
shrd ebx,eax,1
shr eax,1
add dl,1
jmp Bucle

Cero: mov eax,
jmp Fin

Fb:add dl,127
xor eax,eax
mov ax,dx
shld eax,ebx,

Fin:mov [ ecx]

pop edx
pop ecx
pop ebx
pop eax
pop ebp

ret



_int2fp ENDP
END

Problema 6 Practica 2

public class Practi02E6 {
public static void main(String[ ] args) {
int [ ] size = {10000, 100000, 1000000, 10000000};
long [ ] tiempos= new long [ 3*size.length];
Temporizador t = new Temporizador(5);
CronometraMetodoBinarySearch CMBN = new CronometraMetodoBinarySearch(1,1);

for(int i=0;i < size.length;i++){
CMBN.setTamaño(size[ i]);
for(int j=0;j<3;j++){
CMBN.setCaso(j);
t.cronometra(CMBN);
tiempos[ 3*i+j]=t.getTiempoMinimo();
}
}
for(int i=0;i < size.length;i++){
System.out.println("Caso: EP, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i]+" ns");
System.out.println("Caso: EM, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i+1]+" ns");
System.out.println("Caso: EF, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i+2]+" ns");
}
}
}


public class CronometraMetodoBinarySearch implements EstrategiaSolucion{

public static final int EXITO_PRINCIPIO = 0;
public static final int EXITO_MITAD = 1;
public static final int EXITO_FINAL = 2;
public static final int SIN_EXITO_PRINCIPIO = 3;
public static final int SIN_EXITO_MITAD = 4;
public static final int SIN_EXITO_FINAL = 5;

private int numElem;
private int casoDeBusqueda;
private int [] datos;
private int numBuscado;

public CronometraMetodoBinarySearch(int numElem, int casoDeBusqueda) {

// TODO
this.numElem=numElem;
this.casoDeBusqueda=casoDeBusqueda;
this.datos= new int[this.numElem];
this.inicializaDatos();
this.generaNumBuscado();

}

public void setTamaño(int tam){
this.numElem=tam;
this.datos= new int[this.numElem];
this.inicializaDatos();
}

public void setCaso(int casoBusqueda) {

// TODO
this.casoDeBusqueda=casoBusqueda;
this.generaNumBuscado();
}

private void generaNumBuscado() {
switch(casoDeBusqueda) {
case EXITO_PRINCIPIO:
numBuscado = datos[0];
break;
case EXITO_MITAD:
numBuscado = datos[(numElem - 1) / 2];
break;
case EXITO_FINAL:
numBuscado = datos[numElem - 1];
break;
case SIN_EXITO_PRINCIPIO:
numBuscado = datos[0] - 1;
break;
case SIN_EXITO_MITAD:
numBuscado = datos[numElem / 2] - 1;
break;
case SIN_EXITO_FINAL:
numBuscado = datos[numElem - 1] + 1;
break;
default:
// no puede darse ningún otro caso
}
}

private void inicializaDatos() {
for(int i = 0; i < numElem; i++) {
// tomando pares dejamos sitio para las búsquedas fallidas
datos[i] = 2 * (i + 1);
}
}

public void procesamientoFinal() {

}

public void procesamientoInicial() {

}

public void solucion() {
Arrays.binarySearch(this.datos, this.numBuscado);

}

}

Problema 5 Practica 2

public class Practi02E5 {
public static void main(String[ ] args) {
int [ ] size = {1000, 10000, 100000};
long [ ] tiempos= new long [ 2*size.length];
Temporizador t = new Temporizador(1);
CronometraObjetosString COS=new CronometraObjetosString(1);
CronometraObjetosStringBuilder COSB=new CronometraObjetosStringBuilder(1);

for(int i=0;i < size.length;i++){
COS.setRepeticiones(size[ i]);
COSB.setRepeticiones(size[ i]);
t.cronometra(COS);
tiempos[ 2*i]=t.getTiempoMinimo();
t.cronometra(COSB);
tiempos[ 2*i+1]=t.getTiempoMinimo();
}
for(int i=0;i < size.length;i++){
System.out.println("Tiempo de String para "+size[ i]+" elementos: "+tiempos[ 2*i]+" ns");
System.out.println("Tiempo de StringBuilder para "+size[ i]+" elementos: "+tiempos[ 2*i]+" ns");
}


}

}

public class CronometraObjetosString implements EstrategiaSolucion{
private int n;

public CronometraObjetosString(int n){
this.n=n;
}

public void setRepeticiones(int n){
this.n=n;
}

public void procesamientoFinal() {
}

public void procesamientoInicial() {
}

public void solucion() {
String s="";
for (int c = 0; c < n; c++)
s +="A";
}

}


public class CronometraObjetosStringBuilder implements EstrategiaSolucion{

private int n;

public CronometraObjetosStringBuilder(int n){
this.n=n;
}

public void setRepeticiones(int n){
this.n=n;
}

public void procesamientoFinal() {

}

public void procesamientoInicial() {

}

public void solucion() {
StringBuilder sb = new StringBuilder("");
for (int c = 0; c < n; c++)
sb.append("A");
}

}

Problema 4 Practica 2

public class Practi02E4 {
public static void main(String[ ] args) {
int [ ] size = {100, 1000, 10000};
long [ ] tiempos= new long [4*size.length];
CronometraAccesoArray CAA= new CronometraAccesoArray(1);
CronometraAccesoLista CAL= new CronometraAccesoLista(1);
CronometraCreacionArray CCA= new CronometraCreacionArray(1);
CronometraCreacionLista CCL= new CronometraCreacionLista(1);
Temporizador t = new Temporizador(5);

for(int i=0;i < size.length;i++){
CCA.setTamañoArray(size[ i]);
CCL.setTamañoLista(size[ i]);
CAA.setArray(size[ i]);
CAL.setLista(size[ i]);
t.cronometra(CCA);
tiempos[ 4*i]=t.getTiempoMinimo();
t.cronometra(CCL);
tiempos[ 4*i+1]=t.getTiempoMinimo();
t.cronometra(CAA);
tiempos[ 4*i+2]=t.getTiempoMinimo();
t.cronometra(CAL);
tiempos[ 4*i+3]=t.getTiempoMinimo();
}
for(int i=0;i < size.length;i++){
System.out.println("Tiempo de creacion array de "+size[ i]+" elementos, es: "+tiempos[ 4*i]+" ns");
System.out.println("Tiempo de creacion lista de "+size[ i]+" elementos, es: "+tiempos[ 4*i+1]+" ns");
System.out.println("Tiempo de acceso array de "+size[ i]+" elementos, es: "+tiempos[ 4*i+2]+" ns");
System.out.println("Tiempo de acceso lista de "+size[ i]+" elementos, es: "+tiempos[ 4*i+3]+" ns");
}

}
}

public class CronometraAccesoArray implements EstrategiaSolucion {

private int n;
private int[ ] array;
private int aux;

public CronometraAccesoArray(int n){
this.n=n;
this.array=new int[ this.n];
this.aux=(int)this.n/2;
if(this.n%2 == 0)
this.aux++;
for(int i=0;i < n;i++)
this.array[ i]=i;
}

public void setArray(int n){
this.n=n;
this.array=new int[ this.n];
this.aux=(int)this.n/2;
if(this.n%2 == 0)
this.aux++;
for(int i=0;i < n;i++)
this.array[ i]=i;
}

@Override
public void procesamientoFinal() {
// TODO Auto-generated method stub

}

@Override
public void procesamientoInicial() {
// TODO Auto-generated method stub

}

@Override
public void solucion() {
// TODO Auto-generated method stub
System.out.print(this.array[ 0]+", ");
for(int i=1;i < this.aux;i++){
System.out.print(this.array[ this.n-i]+", ");
if(!((this.n-i)==i))
System.out.print(this.array[ i]+", ");
}
System.out.println("]");
}


}

public class CronometraAccesoLista implements EstrategiaSolucion{

private int n;
private LinkedList lista;
private int aux;

public CronometraAccesoLista(int n){
this.n=n;
this.lista=new LinkedList();
this.aux=(int)this.n/2;
if(this.n%2 == 0)
this.aux++;
for(int i=0;i < n;i++)
this.lista.add(i);
}

public void setLista(int n){
this.n=n;
this.lista = new LinkedList();
this.aux=(int)this.n/2;
if(this.n%2 == 0)
this.aux++;
for(int i=0;i < n;i++)
this.lista.add(i);
}

@Override
public void procesamientoFinal() {
// TODO Auto-generated method stub

}

@Override
public void procesamientoInicial() {
// TODO Auto-generated method stub

}

@Override
public void solucion() {
// TODO Auto-generated method stub
System.out.print("["+this.lista.get(0)+", ");
for(int i=1;i < this.aux;i++){
System.out.print(this.lista.get(n-i)+", ");
if(!((this.n-i)==i))
System.out.print(this.lista.get(i)+", ");
}
System.out.println("]");
}

}

public class CronometraCreacionArray implements EstrategiaSolucion {

private int n;

public CronometraCreacionArray(int n){
this.n=n;
}

public int getTamañoArray(){
return this.n;
}

public void setTamañoArray(int n){
this.n=n;
}

@Override
public void procesamientoFinal() {
// TODO Auto-generated method stub

}

@Override
public void procesamientoInicial() {
// TODO Auto-generated method stub

}

@Override
public void solucion() {
// TODO Auto-generated method stub
int [ ] array= new int[ this.n];
for(int i=0;i < n;i++)
array[ i]=i;
}

}


public class CronometraCreacionLista implements EstrategiaSolucion{

private int n;

public CronometraCreacionLista(int n){
this.n=n;
}

public int getTamañoLista(){
return this.n;
}

public void setTamañoLista(int n){
this.n=n;
}

@Override
public void procesamientoFinal() {
// TODO Auto-generated method stub

}

@Override
public void procesamientoInicial() {
// TODO Auto-generated method stub
}

@Override
public void solucion() {
// TODO Auto-generated method stub
LinkedList< Integer> l=new LinkedList< Integer>();
for(int i=0;i < n;i++)
l.add(i);
}

}

Problema 1 Practica 2

public static void main(String[ ] args) {
int [ ] size = {10000, 100000, 1000000, 10000000};
ProblemaBusqueda busquedaProblema;
BusquedaLineal bl;
BusquedaBinaria bb;
Temporizador t;
// TODO Crear un objeto temporizador; el argumento del
// constructor es numPruebas
t = new Temporizador(5);

for (int i = 0; i < 4; i++) {
// TODO Generar un problema para el tamaño dado
busquedaProblema = new ProblemaBusqueda(size[ i],1);

for (int j = 0; j < 3; j++) {
// TODO Establecer un caso para el tamaño de problema generado
busquedaProblema.setCaso(j);

// TODO Crea un objeto solución siguiendo la estrategia de la
// búsqueda lineal. Este objeto implementa la interfaz
// Temporizable
bl = new BusquedaLineal(busquedaProblema);

// TODO Crea un objeto solución siguiendo la estrategia de la
// búsqueda dicotómica. Este objeto implementa la interfaz
// Temporizable
bb = new BusquedaBinaria(busquedaProblema);

// TODO Imprimir el problema
System.out.print("Tamaño: "+size[ i]+" Problema:"+j+" NumBus: "+busquedaProblema.getNumBuscado());

// TODO Ejecutar la busqueda lineal, midiendo su tiempo de
// ejecución
t.cronometra(bl);

// TODO Imprimir la solución encontrada
// y el tiempo de ejecución
System.out.print(" Tiempo mínimo Lineal: "+t.getTiempoMinimo());

// TODO Ejecutar la busqueda dicotómica, midiendo su tiempo de
// ejecución
t.cronometra(bb);

// TODO Imprimir la solución encontrada
// y el tiempo de ejecución
System.out.println(" Tiempo mínimo Dicotomico: "+t.getTiempoMinimo());
}
}
}


public ProblemaBusqueda(int numElem, int casoDeBusqueda) {

// TODO
this.numElem=numElem;
this.casoDeBusqueda=casoDeBusqueda;
this.datos= new int[ this.numElem];
this.inicializaDatos();
this.generaNumBuscado();

}

public void setCaso(int casoBusqueda) {

// TODO
this.casoDeBusqueda=casoBusqueda;
this.generaNumBuscado();
}

Función Buscar

func buscar(a:array [ 1...n] de Entero, c: Entero) dev (r: Entero){
var
j:Entero
alg
j:=1 //1 OE
mientras a[ j]Y j < style="font-weight: bold;">fmientras
si a[ j]=c //2 Oe
r:=j //1 OE
| otras
r:=0 //1 OE
fsi
falg

Caso Mejor:
T(n) = 1+2+2+1 = 6 OE

Caso peor:
T(n) = 1 + 6(n-1) +4+2+1 = 6n+2

Caso medio:
T(n) = 3n +6 Ya que todos los casos son equiprobables.

Practica3

.386
.model flat,stdcall
option casemap:none
.data
Tabla db 41h, 5h, 69h, 0FEh, 0Fh, 28h, 0EFh, 011h
db 22h, 3h, 25h, 0E4h, 77h, 0Ah, 78h, 015h
Mayor db ?
Menor db ?
.code
start:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Ej1: Mayor y Menor de Tabla.-
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
xor eax, eax
xor edx, edx; indice i
mov al, Tabla[ eax]
mov Mayor, al
mov Menor, al
Bucle: cmp edx, 10h
je Fin
mov al,Tabla[ edx]
add edx, 1
cmp al,Mayor
ja Max
Mex: cmp al,Menor
jae Bucle
mov Menor,al
jmp Bucle
Max: mov Mayor,al
jmp Mex
Fin:mov al, Tabla[ 10h]
mov ah, Menor
xor eax,eax
xor edx,edx
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Ej2: Tabla[ i] <- Tabla [i ] AND 0x0F.-
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Bucle2: cmp edx, 10h
je Fin2
mov eax, dword ptr Tabla[ edx]
and eax, 0F0F0F0Fh
mov dword ptr Tabla[ edx], eax
add edx, 4h
jmp Bucle2
Fin2: xor eax,eax
xor edx,edx
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Ej3: Burbuja.-
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
xor ecx,ecx
mov dl, 10h
Bucle3: cmp al,0Eh
ja Fin3
mov ch,dl
sub ch,2h
sub ch,al
Bucle31: cmp dh,ch
ja Fin31
mov cl, byte ptr Tabla[ edx];indices con registro entero
cmp cl,Tabla[ dh+1h]
jb FSI
mov ah,Tabla[ dh+1h]
mov Tabla[ dh+1h],cl
mov Tabla[ dh],ah
FSI: add dh,1h
jmp Bucle31
Fin31: add al,1h
jmp Bucle3
Fin3: xor eax,eax
xor edx,edx
xor ecx,ecx
end start
end

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;

}