Ejercicio 2.a.v

Ejercicio 2.a.v

de Florencia Carle Vitale -
Número de respuestas: 6

Buenas, queria saber si esta implementacion de caminoMasLargo es correcta o estoy perdiendo algo

int largoLista(Lista l){
    if (l == NULL)
        return 0;
    else{
        int cont = 0;
        Lista auxl = l;
        while(auxl != NULL){
            cont++;
            auxl = auxl->sig;
        }
        return cont;
    }
}
Lista ListaMasLarga(lista l, lista p){
    if (largoLista(l) >= largoLista(p))
        return l;
    else return p;
}
Lista caminoMasLargo(AB a){
    Lista l = NULL;
    if (a != NULL){
        l = new nodoLista;
        l->elem  = a->elem;
        l->sig = ListaMasLarga(caminoMasLargo(a->izq), caminoMasLargo(a->der));/*Le asigno a l->sig la lista que sea mas larga entre las dos que contienen a los caminos mas largos de a->izq y a-der*/
    }
    return l;

En respuesta a Florencia Carle Vitale

Re: Ejercicio 2.a.v

de Ignacio Lopez Echetto -

Hola, no detecté ningún error, me sonó un poco raro la creación de una lista nueva en cada llamada recursiva de caminoMasLargo, pero por como la usaste creo que funciona bien...

Aprovecho a compartir mi solución que es diferente, también me gustaría que pudieran verla para avisarme si encuentran algún error, ya que este ejercicio no tiene una solución en video y no he podido generar, como para los prácticos anteriores, subprogramas para testeo “casero”.

Mis solución es:

Lista caminoMasLargo (AB a) {
	Lista res = NULL;
	caminoMasLargoRec(a, res);
	return res;
}
Lista caminoMasLargoRec (AB a, Lista & l) {
	if (a != NULL) {
		if (altura(a->izq) >= altura(a->der))
			insertarAlPpo(caminoMasLargoRec(a->izq, l), a->elem);
		else
			insertarAlPpo(caminoMasLargoRec(a->der, l), a->elem);
	}
	
	return l;
}

donde el procedimiento insertarAlPpo sigue las especificaciones esperables, recibe una lista l y un unsigned int n, e inserta un nodo que cuyo elem es n, al principio de l, “corriendo” los elementos que ya estaban a “posiciones” siguientes; y la función altura es la misma que se describe en el material teórico.

En respuesta a Ignacio Lopez Echetto

Re: Ejercicio 2.a.v

de Matias Richart -

Hola.

Tu solución tiene un problema y es que no veo que estés utilizando o modificando la lista l que pasas por parámetro en la función recursiva.

Luego, pensando que eso se puede corregir, estaría bueno que intentaras no recorrer tantas veces el árbol. Fijate que por cada llamada, recorres el árbol una vez para calcular la altura y luego haces una recorrida (muy similar) para armar la lista del camino mas largo.

Recién subimos soluciones de este práctico. Intentá pensar una nueva solución y si querés luego mirá nuestra propuesta para tener una versión alternativa.

En respuesta a Matias Richart

Re: Ejercicio 2.a.v

de Ignacio Lopez Echetto -

Gracias por la respuesta. La lista l que paso por parámetro la voy modificando a través del procedimiento insertarAlPpo que, no aclaré, recibe como segundo argumento una lista por referencia (simulada), donde en el encabezado usé el &.

Pensé mucho en la eficiencia, como dices, no tener que recorrer tantas veces el árbol... No sabía cómo lograr determinar qué nodo elegir para agregar a la lista, sin saber su altura a partir de dicho nodo digamos, y para ello, implementé la función altura del teórico, que recorre la lista...

Pero ahora que están las soluciones del práctico voy corriendo a ver la de este ejercicio porque ya no se me ocurre más nada!

Gracias de nuevo, saludos!

En respuesta a Ignacio Lopez Echetto

Re: Ejercicio 2.a.v

de Matias Richart -

Hola Ignacio.

Ten cuidado que esa forma de modificar la lista l que propones no funcionará.

Entiendo que insertarAlPpo (por como está el código) recibe una lista como primer parámetro:

insertarAlPpo(caminoMasLargoRec(a->izq, l), a->elem);
El problema que tienes ahí es que como parámetro de entrada estas pasando el resultado de caminoMasLargoRec. Esa función devolverá una copia del puntero, por lo que puedes no estar modificando la lista original.
Además, tu código es un poco confuso en el sentido que tienes la lista que pasas por referencia (entiendo que para poder modificarla) pero además la función retorna esa lista.

Espero se entienda.

Saludos

En respuesta a Florencia Carle Vitale

Re: Ejercicio 2.a.v

de Matias Richart -

Hola.

Tu solución parece correcta. Puede ser un poco ineficiente, en el sentido que estas en todas las llamadas, recorriendo las listas para calcular su tamaño.

Recién subimos soluciones de este práctico. Mirá nuestra propuesta para tener una versión alternativa.

Saludos