FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de datos Y Programación TRABAJO PRÁCTICO Nº 4

14/08/2012

Tema: Recursividad. Objetivo: Que los alumnos logren…  Habilidad para identificar las distintas estructuras de tipo recursivas y capacidad para utilizar el concepto de recursión.  Entender los pasos que siguen los lenguajes de programacion al llamar a un metodo recursivo.  Capacidad para verificar la solución de algoritmos desarrollados usando POO 

Capacidad para usar, en forma eficiente, los distintos métodos de clasificación y de búsqueda.



Destreza en el uso del entorno de desarrollo Netbeans y el lenguaje de programación Java.  Capacidad para implementar correctamente las soluciones algorítmicas, en lenguaje de programación Java. Fecha de presentación: 2 semanas a partir de la fecha del practico. Consideraciones Generales:  Este trabajo práctico debe realizarse en forma individual.  La presentación implicará la entrega del material abrochado, o en una carpeta, contando con los siguientes ítems: o Carátula. Identificación completa del trabajo práctico con todos los datos del alumno y la asignatura, año, carrera, etc. o Desarrollo del práctico con hojas numeradas e identificadas, que deberá incluir:  Los algoritmos deben estar completamente desarrollados, de manera prolija, e incluyendo las descripciones necesarias para su mejor seguimiento (identificación, variables utilizadas y sus funciones, etc.), cumpliendo las indicaciones relativas a la diagramación estructurada y modular. 

El Código de las aplicaciones solicitadas deberá enviarse al correo de la materia [email protected]. El nombre del código deberá estar conformado de acuerdo al siguiente esquema: carrera_ ApellidoNomdelAlumno_NumPrac_NumEjerc

Conceptos basicos Recursividad (recursión) : es la propiedad que posee un metodo por la cual dicho metodo puede llamarse a si mismo. En muchos casos el uso de la recursión permite especificar soluciones naturales, sencillas, que serian en caso contrario difíciles de resolver. Un metodo recursivo es aquel que se llama a si mismo, bien directamente o bien a traves de otro metodo.

Para todos los ejercicios:



Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.



Realizar la programación y la ejecución del programa en lenguaje Java, utilizando el entorno de desarrollo (IDE) Netbeans

Resolver los siguientes problemas de tipo teórico, practico y experimental 2. Desarrolle un metodo que acepte como parámetro un número natural (n), y devuelva como resultado la suma de sus divisores. 3. Desarrolle un metodo que acepte como parámetro una palabra de N letras, y la muestre en forma inversa. Pag:1

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de datos Y Programación TRABAJO PRÁCTICO Nº 4

14/08/2012

4. Escriba un metodo que calcule de modo recursivo un numero de la serie de Fibonacci dada la posición que ocupa en la serie. ¿Cuál es la secuencia numerica generada por el metodo recursivo?. Implemente en Java. 5. Escriba un planteo recursivo e implemente en Java de los siguientes incisos: a) Una función recursiva que cuente la cantidad de apariciones de un dígito D en un número entero N. Ej.: si N=13234, D=3; el resultado es 2.

b) Un metodo que cuente la cantidad de dígitos impares en un número entero. Ej.: si el número es 22005 el resultado es 1, y si fuera 35 el resultado es 2.

6. Algoritmo de vuelta atrás(Backtracking): Problema de la mochila Dado un conjunto de pesos p1,p2,..,pn(enteros positivos) determinar si existe una selección de pesos que totalice exactamente un valor dado como objetivo V. Ejemplo si V=12, y los pesos son 4,3,6,2,1, se pueden elegir 4,6,2. La representación de los pesos se realiza con un vector de numeros enteros. La funcion basica del algoritmo es añadir un peso nuevo, probar si con ese peso se alcanza la solucion, caso contrario se produce situación de impasse, en la que no se consigue el objetivo, porque siempre es superado, entonces se retrocede para eliminar el peso añadido y se prueba con otro peso para inspeccionar si a partir de él se consigue el objetivo. Pruebe el algoritmo según lo planteado en el libro “Estructura de datos”-Joyanes Aguilar-Zahonero Martinez. Parte III. Cap.9 .pag.291. Realice un comentario sobre su funcionamiento, tener en cuenta aspectos como: eficiencia en terminos de tiempo y operaciones, sencillez del algoritmo recursivo, condiciones de terminacion del algoritmo adecuada

7. Desarrolle un metodo recursivo para la búsqueda binaria de una clave (valor buscado) dentro de un array ordenado de n elementos.

8. Ordenacion rapida : El metodo de Quicksort. El algoritmo se basa en dividir los n elementos de la lista a ordenar en 2 partes separadas por un elemento (pivote). Una partición izquierda con los elementos menores que todos los elementos de la partición derecha. Las dos listas se ordenan independientemente. Estas dos listas parciales se ordenan recursivamente utilizando el mismo algoritmo quicksort. Escriba y ejecute el siguiente codigo en JAVA, analize su funcionamiento y represente el algoritmo con diagramas de flujo. public class Quick { private int miArreglo[]; int indice; int n=10; Scanner ingreso; public Quick(){ miArreglo = new int[n]; ingreso = new Scanner(System.in); } public void cargar() { int numero; System.out.print("\n\n Ingresar datos: \n"); Pag:2

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS CARRERA: Licenciatura en Sistemas de Información

ASIGNATURA: Estructura de datos Y Programación TRABAJO PRÁCTICO Nº 4

14/08/2012

for(int i = 0; i < miArreglo.length; i++){ System.out.print("\n\n Ingresar el elemento "+i +": "); numero = ingreso.nextInt(); miArreglo[i] = numero; } quicksort(miArreglo,0,n-1); //convoca al método para ordenar } public void imprimir(){ System.out.print("\n\n Listado del Arreglo \n"); for(int i = 0; i < miArreglo.length; i++){ System.out.print("\n El numero almacenado en la posicion: " +i + " es: "+ miArreglo[i]); } }

//método de ordenamiento quicksort public void quicksort(int A[], int primero, int ultimo){ int i, j,central; int pivote; central=(primero+ultimo)/2; pivote=A[central]; i=primero; j=ultimo; do{ while(A[i]< pivote) { i=i+1; } while(A[j]> pivote){ j=j-1; } if (i