Práctica 6: Recursión

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

Escribe una clase llamada mx.itesm.cem.recursion.RecursiveAlgorithms. En esta clase deberás colocar únicamente operaciones de utilería (métodos estáticos) para resolver los problemas que se describen a continuación usando recursión.

Métodos a implementar

1. public static int gcd(int m, int n)

   Devuelve el máximo común divisor (GCD por sus siglas en inglés: greatest common divisor) de m y n usando el algoritmo de Dijkstra. Dicho algoritmo se define matemáticamente como:

   

2. public static int pow(int base, int exponent)

   Devuelve el resultado de elevar base a la potencia exponent. La operación pow se define así: si exponent es igual a 0, devuelve 1; de otra forma, devuelve el resultado de multiplicar base por el resultado de la llamada recursiva de pow con la misma base y exponent decrementado en uno.

3. public static int max(List<Integer> list)

   Devuelve el elemento más grande de list. El elemento más grande de una lista es el mayor de entre el primero de la lista y el más grande del resto de la lista. Devuelve Integer.MIN_VALUE si list está vacía.

4. public static int consecutiveAddition(int start, int end)

   Devuelve la suma todos los enteros consecutivos entre start y end inclusive. Devuelve 0 si start es mayor que end.

5. public static String toBinary(int n)

   Devuelve una cadena de caracteres con la representación binaria del número entero n (n ≥ 0). Por simplicidad, si n es cero devuelve la cadena vacía; para cualquier otro caso devuelve el resultado de la llamada recursiva de toBinary, con el cociente de n entre 2 como argumento, concatenado con el residuo de n entre 2.

6. public static boolean isPalindrome(String s)

   Devuelve true si la cadena s contiene un palíndromo, o false en caso contrario. Un palíndromo es una palabra, número o frase que se lee igual hacia adelante que hacia atrás. Un ejemplo clásico es: “Anita lava la tina”. La idea básica consiste en verificar si la primera y última letra de la cadena s son iguales; en caso afirmativo, la cadena completa es un palíndromo solo si todo lo que está contenido entre ambas letras es también un palíndromo. Una cadena vacía y una cadena con una sola letra es un palíndromo. Hay un par de casos especiales que se deben considerar. Si el primer o último carácter de la cadena s no es una letra, debes verificar si es un palíndromo la cadena resultante después de remover dicho carácter. Así mismo, la comparación de las letras se debe llevar a cabo sin hacer distinción entre mayúsculas y minúsculas.

   Revisa el API de Java para recordar los métodos para manipular cadenas de caracteres y caracteres individuales.

Pruebas unitarias

Prueba tu código usando la siguiente clase de JUnit:

package mx.itesm.cem.recursion;

import static org.junit.Assert.*;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;

public class TestRecursiveAlgorithms {

    @Test
    public void testGcd() {
        assertEquals(3, RecursiveAlgorithms.gcd(6, 15));
        assertEquals(42, RecursiveAlgorithms.gcd(42, 42));
        assertEquals(1, RecursiveAlgorithms.gcd(97, 23));
        assertEquals(1, RecursiveAlgorithms.gcd(1, 8));
        assertEquals(20, RecursiveAlgorithms.gcd(40, 100));
        assertEquals(2, RecursiveAlgorithms.gcd(1000, 666));
    }

    @Test
    public void testPow() {
        assertEquals(1, RecursiveAlgorithms.pow(100, 0));
        assertEquals(100, RecursiveAlgorithms.pow(100, 1));
        assertEquals(1, RecursiveAlgorithms.pow(1, 1000));
        assertEquals(10000,
                RecursiveAlgorithms.pow(100, 2));
        assertEquals(125, RecursiveAlgorithms.pow(5, 3));
        assertEquals(1073741824,
                RecursiveAlgorithms.pow(2, 30));
    }

    @Test
    public void testMax() {
        List<Integer> empty = Arrays.asList();
        List<Integer> a = Arrays.asList(16, 23, 4, 42, 8,
                15);
        List<Integer> b = Arrays.asList(-16, -23, -4, -42,
                -8, -15);
        List<Integer> c = Arrays.asList(780, 560, 726, 524,
                794, 454, 628, 335, 786, 992, 559, 798, 427,
                382, 900, 391, 981, 432, 963, 727, 863, 861,
                38, 567, 29, 805, 711, 926, 902, 97, 469,
                644, 687, 605, 503, 530, 145, 161, 425, 417,
                410, 963, 729, 899, 57, 366, 600, 721, 536,
                125, 491, 192, 961, 749, 785, 271, 660, 646,
                73, 894, 74, 574, 993, 239, 384, 347, 390,
                695, 469, 965, 685, 865, 605, 518, 572, 380,
                895, 625, 410, 804, 681, 190, 351, 889, 155,
                389, 289, 984, 950, 694, 953, 222, 372, 752,
                367, 771, 386, 645, 614, 93, 386, 21, 444,
                123, 332, 236, 227, 57, 896, 321, 428, 978,
                726, 598, 516, 539, 316, 461, 288, 930, 806,
                480, 197, 111, 206, 86, 875, 254, 936, 156,
                566, 719, 244, 662, 133, 860, 654, 445, 479,
                755, 37, 57, 208, 383, 502, 794, 538, 742,
                760, 355, 52, 530, 128, 359, 298, 847, 794,
                660, 721, 84, 498, 225, 296, 60, 511, 427,
                905, 118, 542, 572, 708, 334, 377, 648, 983,
                327, 127, 578, 756, 113, 936, 737, 950, 982,
                905, 317, 372, 745, 83, 169, 134, 552, 850,
                198, 707, 680, 977, 599, 276, 714);
        assertEquals(Integer.MIN_VALUE,
                RecursiveAlgorithms.max(empty));
        assertEquals(42, RecursiveAlgorithms.max(a));
        assertEquals(-4, RecursiveAlgorithms.max(b));
        assertEquals(993, RecursiveAlgorithms.max(c));
    }

    @Test
    public void testConsecutiveAddition() {
        assertEquals(75, RecursiveAlgorithms
                .consecutiveAddition(10, 15));
        assertEquals(5050, RecursiveAlgorithms
                .consecutiveAddition(1, 100));
        assertEquals(0, RecursiveAlgorithms
                .consecutiveAddition(6, 5));
        assertEquals(42, RecursiveAlgorithms
                .consecutiveAddition(42, 42));
    }

    @Test
    public void testToBinary() {
        assertEquals("", RecursiveAlgorithms.toBinary(0));
        assertEquals("1", RecursiveAlgorithms.toBinary(1));
        assertEquals("101",
                RecursiveAlgorithms.toBinary(5));
        assertEquals("11111",
                RecursiveAlgorithms.toBinary(31));
        assertEquals("100000",
                RecursiveAlgorithms.toBinary(32));
        assertEquals("1010011010",
                RecursiveAlgorithms.toBinary(666));
        assertEquals("1010101010101",
                RecursiveAlgorithms.toBinary(5461));
    }

    @Test
    public void testIsPalindrome() {
        assertTrue(RecursiveAlgorithms.isPalindrome(""));
        assertTrue(RecursiveAlgorithms.isPalindrome("a"));
        assertTrue(RecursiveAlgorithms.isPalindrome("ana"));
        assertTrue(RecursiveAlgorithms
                .isPalindrome("Anita lava la tina."));
        assertTrue(RecursiveAlgorithms
                .isPalindrome("La moral, claro, mal."));
        assertTrue(RecursiveAlgorithms.isPalindrome(
                "¿Subo tu auto o tu autobus?"));
        assertTrue(RecursiveAlgorithms.isPalindrome(
                "A mama Roma le aviva el amor a papa, "
                        + "y a papa Roma le aviva el "
                        + "amor a mama."));
        assertFalse(RecursiveAlgorithms.isPalindrome("la"));
        assertFalse(RecursiveAlgorithms
                .isPalindrome("Yo no hago yoga hoy."));
        assertFalse(RecursiveAlgorithms.isPalindrome(
                "Anita no quiere lavar la tina."));
    }
}

¿Qué se debe entregar?

Tu archivo fuente de Java debe comenzar con un comentario que contenga el título de la práctica, la fecha y los datos personales de los autores (nombre y matrícula). Por ejemplo:

/*----------------------------------------------------------
 * Práctica 6: Recursión
 * Fecha: 06-Abr-2018
 * Autores:
 *           A01166611 Pepper Pots
 *           A01160611 Anthony Stark
 *----------------------------------------------------------*/

Si la práctica fue desarrollada en pareja, basta que solo uno de los miembros la entregue.

La fecha límite es el lunes 9 de abril.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

-10	No se incluyó en comentario los datos de los autores.
10-100	Dependiendo del número de métodos correctamente implementados.
10	El programa no compila.
1	El programa es un plagio total o parcial.