Recursividad Java - Ejercicio gusanito viajero por lomas con pendientes

[Fernando]

Hola, quisiera dominar los arrayList de arraylist con recursividad y me encontré con un porblema el cual dice así:

"Hay un gusanito viejito y viajero que quiere visitar una zona que esta conformada por varias lomas , sin embargo para el es dificil subir las cuestas enpinadas por muy chicas que sean incluso bajarlas y ha decidido visitar solamente una loma de la zona por lo que se te ha pedido que que le puedas decir cual es la loma cual es la loma que deberia visitar de manera que no implique mucho es fuerzo por el tema de las pendientes, ya sea al subir o al bajar.
 
Debes considerar que para el gusanito si se tiene una pendiente mayor o igual a p, esa ya no es una loma deseable para el, Debes indicar cual es la loma de mayos superficie que puede visitar y que no incumpla ninguna cuestion de la pendiente. La pendiente entre dos puntos se puede calcular como la diferencia entre ellos.

En definitiva para resolver el problema, te darán la secuencia de numeros que representarán las lomas y la pendiente p que simepre sera un numero entero positivo.

Por Ejemplo:

sec ={3,5,4,3,3,2,3,5,7,8,7,5,3,2,3,5,6,7,3,1,3,7,9,7,1}
p = 3

Entonces hay cuatro posibles lomas de visita:

loma1 = {3,5,4,3,3,2}
loma2 = {2,3,5,7,8,7,5,3,2}
loma3 = {2,3,5,6,7,3,1}
loma4 = {1,3,7,9,7,1}

La loma1 y la loma2 cumplen la condicion de la pendiente, sin embargo la loma 3 y la loma4 no, ya que al bajar la loma de 7 a 3 hay una pendiente mayor a p, lo mismo en la loma 4, subir de 3 a 7, o bajar de 7 a 1 son mayores que p

Entre las lomas validas la mejor es la loma 2 por que cubre mayor superficie por lo que el resultado es : {2,3,5,7,8,7,5,3,2}, en caso de no existir una loma valida para el gusanito el resultado es : {}

Se te pide el o los metodos recursivos para poder encontrar la loma que cumpla con las condiciones del gusanito"

Me costó mucho entender arrayList<ArrayList<Integer>> y con recursividad me perdi si alguien sabe una solucion le agradezco de antemano

[Alex Rodríguez]

Hola, hay una cosa que no me queda clara. Escribes esto:

sec ={3,5,4,3,3,2,3,5,7,8,7,5,3,2,3,5,6,7,3,1,3,7,9,7,1}
p = 3

Entonces hay cuatro posibles lomas de visita:

loma1 = {3,5,4,3,3,2}
loma2 = {2,3,5,7,8,7,5,3,2}
loma3 = {2,3,5,6,7,3,1}
loma4 = {1,3,7,9,7,1}

¿Por qué son esas las lomas de visita? Es decir, ¿cómo sabes cuáles son las lomas posibles dada una secuencia de números y un valor de p?

Saludos

[Fernando]

Los dates que the Dan es un int pendiente y un array o arraylist  que simbolizan la altura ponte que tenemos el arraylist {1,5,7} y que entre 1 y5 hay una distancia digamos de 1 cm y cada elemento representa su altura a una distancia y para que se la considere loma de debe empezar en un número menor que la pendiente que para el caso de p =3 las Lomas empiezan en 1 o 2 y su terminación lo mismo

[Alex Rodríguez]

Creo que ya lo he entendido. Por ejemplo aquí:

sec ={3,5,4,3,3,2,3,5,7,8,7,5,3,2,3,5,6,7,3,1,3,7,9,7,1}
p = 3

Las lomas son series de números que van de un número más pequeño a un número más grande y luego vuelven a descender hasta un número más pequeño, por ejemplo:

Empezamos con 3, luego un número más grande el 5, como no hay uno más grande estamos en la cima de la loma y ahora empezamos a descender, pasamos al 4, seguimos al 3, seguimos en otro 3, luego al 2 y como no baja más se terminó la loma y tenemos la loma  loma1 = {3,5,4,3,3,2}

Ahora comenzamos en otro número {3,5,4,3,3,2,3,5,7,8,7,5,3,2,3,5,6,7,3,1,3,7,9,7,1}

Ese 2 puede verse como el inicio de una loma. Iría subiendo: 2, 3, 5, 7, 8 y ha llegado a la cima de la loma y empieza a descender: 7, 5, 3, 2 y se terminó la loma, tenemos loma2 = {2,3,5,7,8,7,5,3,2}

De la misma forma sacamos loma3 = {2,3,5,6,7,3,1} y loma4 = {1,3,7,9,7,1}

La superficie de la loma me imagino que es el número de elementos que tiene, por ejemplo una loma que fuera {2,4,2} tendría menos superficie que otra que fuera {1,2,4,2,1}

Y la pendiente indica que no debe haber una diferencia mayor que el valor de p entre dos números consecutivos. Por ejemplo si p=3 la loma {5,6,4} sería válida porque 6-5=1 y no supera 3, y porque 4-6 = -2 (el signo negativo indicaría que está en bajada, podríamos tomarlo el valor absoluto 3) y no supera el valor 3.

En cambio con p=3 la loma {5, 9, 7} no sería una loma válida porque 9-5=4 es un valor superior a p.

Esto es más o menos lo que he entendido ¿es así?

[Fernando]

si ahora lo que necesito es programa recursivo que resuelva el problema usando arraylist<arraylist<integer>> y yo medio que no entiendo esto

[Alex Rodríguez]

Trata de no abordar todo el problema de golpe porque es complejo. En lugar de abordarlo todo, intenta definir primero las partes del programa. Por ejemplo necesitarás una clase Java que se puede denominar <<Loma>> que tenga como atributo un ArrayList de integer y que tenga métodos para recuperar un elemento del arrayList a partir del índice, para obtener las pendientes existentes dentro de la loma (esto puede ser un método que devuelva un ArrayList de integer que contenga las pendientes de la loma), para recuperar la loma completa, para establecer la loma completa, etc.

Una vez tengas esto, pasarías al diseño de la siguiente clase y así sucesivamente hasta que el proceso recursivo lo definas al final ya usando todas las clases previas que hayas creado. Vete pegando el código que vayas creando para tratar de corregirte o ayudarte donde tengas problemas.

Saludos

[Fernando]

mmm si eso podria facilitarme mas yo intente hacer la clase recursiva despues los metodos de complemento ah y una duda donde puedo aprender mas de arraylist bidimensional es que lo veo algo complicado de entender y peor usarlos recursivamente

[Alex Rodríguez]

En este curso tienes todos los conceptos básicos que necesitas: http://aprenderaprogramar.com/index.php?option=com_content&view=category&id=68&Itemid=188

El ArrayList que necesitas dices que es bidimensional ¿por qué tiene que ser bidimensional? Si simplemente vas a almacenar series de números ¿no te vale con un ArrayList unidimensional?

[Fernando]

al crear mi metodo pedi introducir un metodo que me pide un apendiente y un array y me apararece error illegal initializer for java.util.ArrayList<java.lang.integer> como le introdusco un arrayList<Integer>

[Alex Rodríguez]

Hola, pega el código de las clases que estés utilizando (para que podamos compilarlo y ver cuál es el problema). Para ello escribe el nombre de la clase, deja una línea en blanco y pulsa el botón # del editor del foro. Pega el código entre las etiquetas [cod] ... [/cod] Luego pulsa previsualizar para comprobar que se ve bien y luego pulsa publicar.

Debe quedar algo así:

Clase 1

Código: [Seleccionar]

cod
cod
lineas de codigo...
Clase 2

Código: [Seleccionar]

cod
cod
lineas de codigo...
Saludos

[Fernando]

#
[cod]
    public ArrayList<Integer> mejor(ArrayList<Integer> lomas, int p)
    {
        ArrayList<Integer> loma = new ArrayList<Integer>();
        if(loma.size() ==1)
        {
            loma = lomas;
        }
        else
        {
            ArrayList<Integer> primLoma = primera(lomas,p,true);
            loma = mejor(lomas,p);
            if(primLoma.size()>loma.size())
            {
                loma = primLoma;
            }
        }
        return loma;
    }
[/cod]
la cosa es que el metodo tengo que ingresar un ArrayList de tipo Integer como le hago eso

[Alex Rodríguez]

Si pulsas el botón # encima del espacio donde escribes te aparecerán las etiquetas y dentro de esas etiquetas escribe el código. Luego pulsa previsualizar y se tiene que ver así:

Código: [Seleccionar]

if(loma.size() ==1)
        {
            loma = lomas;
        }
        else
        {
            ArrayList<Integer> primLoma = primera(lomas,p,true);
            loma = mejor(lomas,p);
            if(primLoma.size()>loma.size())
            {
Por otro lado, el código que has pegado no es la clase completa, no se puede compilar. Pega el código de la clase completa para poder intentar compilarlo, si no no se puede compilar.

Saludos