PDF de programación - Ejercicios resueltos de Programación

Ejercicios resueltos de programación

Mariano Fernández López

Escuela Politécnica Superior, Universidad San Pablo CEU

18 de marzo de 2015

Índice general

1. Implementación de un método recursivo

1.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Implementación de una cola

taVacia e insertar

2.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación de la cola con un array . . . . . . . . . . . .
2.2.
2.2.1. Primera versión de la clase Cola y de los métodos es-
. . . . . . . . . . . . . . . . . . . .
2.2.2. Primera versión del método borrar . . . . . . . . . . .
2.2.3. Primera versión del método primero . . . . . . . . . .
2.2.4. Refinamiento de indicePrimero e indiceUltimo . . . . .
2.2.5. Primera versión del método tamanno . . . . . . . . . .
2.3. Tratamiento de excepciones . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
2.4. La cola con un array móvil
2.5. La cola con un array circular
. . . . . . . . . . . . . . . . . .
2.6. Añadido de pruebas para hacer más robusto el software
. . .
2.7. Código final con los tests y la cola . . . . . . . . . . . . . . .

2
2
2

5
5
5

5
7
8
8
10
11
14
15
16
18

1

Capítulo 1

Implementación de un método
recursivo

1.1. Enunciado

Siguiendo la técnica de desarrollo dirigido por pruebas, implemente un
método recursivo que permita calcular la suma de los n primeros números
naturales.

1.2. Resolución

En primer lugar se escribe la clase donde va a estar ubicado el método a

implementar:

package numeros;

public class Numero {

}

A continuación, se escribe un test para forzar la creación del método:

package numeros;

import org.junit.Test;
import static org.junit.Assert.*;

public class NumeroTest {

@Test
public void testSumaHasta0() {

assertEquals(0, Numero.sumaNPrimeros(0));

}

}

2

CAPÍTULO 1. IMPLEMENTACIÓN DE UN MÉTODO RECURSIVO 3

El código incial del método tiene lo mínimo para permitir la compilación
del test, y para verlo fallar. Recuérdese que, para garantizar que el test es
útil, es importante verlo fallar al menos una vez.

static Object sumaNPrimeros(int i) {

throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.

}

A continuación, se escribe el código mínimo en el método para que pase

el test. De hecho, se devuelve una constante:

public static int sumaNPrimeros(int i) {

return 0;

}

Se lleva ahora a cabo la triangulación mediante un test que obliga a

generalizar el código del método.

@Test
public void testSumaHasta3() {

assertEquals(6, Numero.sumaNPrimeros(3));

}

Este test lo vemos fallar con el código actual del método.
Para generalizar el código del método se utiliza la técnica vista en clase
para los métodos recursivos. En primer lugar, se escribe el caso básico y, para
el caso complejo, se asume que hay un duende que resuelve el problema con
la entrada reducida.

public static int sumaNPrimeros(int n) {

if (n == 0) return 0;
else return n + sumaNPrimeros(n - 1);

}

Luego, se añade el siguiente test para tratar los casos anómalos:

@Test(expected = ArithmeticException.class)
public void testSumaHastaMenos3() throws ArithmeticException {

Numero.sumaNPrimeros(-3);

}

La versión actual del método permite ver fallar el test.
A continuación, hay que modificar el método para que pase el test:

public static int sumaNPrimeros(int n) throws ArithmeticException {

if (n < 0) throw new ArithmeticException("Este método no permite "

+ "números menores que 0");

if (n == 0) return 0;
else return n + sumaNPrimeros(n - 1);

}

CAPÍTULO 1. IMPLEMENTACIÓN DE UN MÉTODO RECURSIVO 4

Por último, se introduce otro test para dotar de más robustez al código
realizando una comprobación sobre un número de varios órdenes de magnitud
mayor que los de las pruebas anteriores:

@Test
public void testSumaHasta10000() throws ArithmeticException {

assertEquals(50005000, Numero.sumaNPrimeros(10000));

}

Para asegurarse de que este test es útil, hay que hacerlo fallar modificando
el código del método a implementar, aunque luego, obviamente, hay que
restaurarlo.

Capítulo 2

Implementación de una cola

2.1. Enunciado

De acuerdo con la técnica de desarrollo dirigido por pruebas, implemente

una estructura de cola con las siguientes operaciones:

Está vacía: devuelve verdadero si la cola está vacía, y falso en otro
caso.

Insertar: introduce un elemento al principio de la cola.

Borrar: elimina un elemento del final de la cola.

Primero: obtiene el primer elemento de la cola.

Tamaño: devuelve el número de elementos que tiene la cola.

Para entender esta estructura de datos podemos pensar en la cola de
un determinado servicio. Van llegando individuos a la cola (insertar en la
cola), y se van atendiendo individuos (eliminar de la cola). La política de
esta estructura de datos es FIFO: el primero que entra es el primero que
sale, es decir, el primero que llega a la cola es el primero en ser atendido.

2.2.

Implementación de la cola con un array

2.2.1. Primera versión de la clase Cola y de los métodos

estaVacia e insertar

En un proyecto que ya tengamos de estructuras de datos o en un proyecto

nuevo, empezamos creando la clase Cola en el paquete cola:

package colas;

public class Cola {
}

5

CAPÍTULO 2. IMPLEMENTACIÓN DE UNA COLA

6

A continuación, vamos creando los tests que necesitamos para ir dotando
de contenido a la clase Cola. El primer test, que permite comprobar si una
cola recién creada está vacía, nos fuerza a crear el método estaVacia. La
clase ColaTest, con el método testEstaVaciaColaRecienCreada, se muestra a
continuación:

package colas;

import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;

/**
*
* @author mariano
*/
public class ColaTest {

Cola cola;

public ColaTest() {
}

@Before
public void setUp() {

cola = new Cola();

}

@Test
public void testEstaVaciaColaRecienCreada() {

assertEquals(true, cola.estaVacia());

}

}

Tal y como se puede comprobar, se crea siempre una cola antes de cada

test (véase el código de setUp).

con Netbeans es el siguiente:

El método estaVacia, de la clase Cola, que generamos automáticamente

Object estaVacia() {

throw new UnsupportedOperationException("Not supported yet.");
}

Como se puede comprobar, el método estaVacia todavía no tiene conte-
nido, y su tipo de retorno no es el adecuado. El único propósito del código
anterior es que el test compile y lo veamos fallar. Ahora modificamos esta-
Vacia para hacer funcionar el test:

public boolean estaVacia() {

return true;

}

CAPÍTULO 2. IMPLEMENTACIÓN DE UNA COLA

7

A continuación, se procede a la triangulación para generalizar el método

estaVacia, con el siguiente test:

@Test
public void testNoEstaVaciaColaConUnUnElemento()
{

cola.insertar("Juan");
assertEquals(false, cola.estaVacia());

}

Con el código que teníamos antes del método estaVacia, vemos fallar el

Para hacerlo funcionar, tenemos que pensar en un código general para la

test.

clase Cola:

public class Cola {

int indiceUltimo, indicePrimero = -1;
int tamMax = 100;
Object[] array = new Object[tamMax];

public boolean estaVacia() {

return indicePrimero==-1;

}

public void insertar(Object elemento) {

array[indiceUltimo++] = elemento;
indicePrimero++;

}

}

2.2.2. Primera versión del método borrar

Seguimos escribiendo tests para implementar el método borrar. El pri-
mero de ellos comprueba si, después y de insertar y eliminar en una cola, la
cola se queda vacía.

@Test
public void testInsertarYBorrarDejaLaColaVacia()
{

cola.insertar("Juan");
cola.borrar();
assertEquals(true, cola.estaVacia());

}

El código de borrar que generamos automáticamente con Netbeans es el

que se muestra a continuación:

void borrar() {

throw new UnsupportedOperationException("Not supported yet.");

}

CAPÍTULO 2. IMPLEMENTACIÓN DE UNA COLA

8

Con este código conseguimos compilar y ver fallar el test. Ahora, creamos

un código que permite hacer funcionar el test:

public void borrar() {

indicePrimero--;

}

2.2.3. Primera versión del método primero

A continuación, escribimos un test para provocar la creación del método

primero:

@Test
public void testPrimeroDeUnaColaConUnElemento()
{

cola.insertar("Juan");
assertEquals(0, ((String) cola.primero()).compareTo("Juan"));

}

Con el siguiente código conseguimos que compile el test y verlo fallar:

Object primero() {

throw new UnsupportedOperationException("Not supported yet.");

}

Ahora, corregimos el código de primero para hacerlo funcionar.

public Object primero() {

return array[indicePrimero];

}

2.2.4. Refinamiento de indicePrimero e indiceUltimo

En este momento surge un problema: ¿cómo puede ser que en el método
de insertar siempre incrementemos el indicePrimero si lo que debe ocurrir es
que, salvo para el primer individuo que entra en la cola, sólo se incremente
el indiceUltimo?

Para forzar la corrección de este código, combinamos dos inserciones y la

recuperación del primero de la cola mediante el siguiente test:

@Test
public void testPrimeroDeUnaColaConDosElementos()
{

cola.insertar("Juan");
cola.insertar("Miguel");
assertEquals(0, ((String) cola.primero()).compareTo("Juan"));

}

Para que el test funcione, tenemos que modificar el código de insertar

para que quede de la siguiente manera:

CAPÍTULO 2. IMPLEMENTACIÓN DE UNA COLA

9

public void insertar(Object elemento) {

array[indiceUltimo++] = elemento;
if (estaVacia()) indicePrimero=0;

}

Obsérvese que la modificación del índice del primero sólo se produce

cuando se inserta en una cola vacía.

No obstante, el tratamiento del indicePrimero sigue sin estar afinado.
No puede ser que sólo cambie cuando se inserta la primera vez. Cuando se
realicen borrados, también hay que modificar este índice. De hecho, se puede
comprobar que el test que se muestra a continuación:

@Test
public void testPrimeroDeUnaColaDespuesDeAnnadir2EltosYBorrarUno()