martes, 9 de diciembre de 2014
unidad 3 trabajo de investigación recursividad
ZZ
Dirección
General de Educación Superior Tecnológica
INSTITUTO TECNOLÓGICO DE SALINA CRUZ
TEMA:
Investigación “recursividad”
FACILITADOR:
Susana Monica Roman najera
NOMBRE:
Asignatura:
Estructuras y
organización de datos
SEMESTRE:
3RO GRUPO: 3E
CARRERA: ING. EN TEC. DE LA INFORMACION Y
COMUNICACIÓN.
Recursividad
Primero debemos decir
que la recursividad no es una estructura de datos, sino que es una técnica de
programación que nos permite que un bloque de instrucciones se ejecute n veces.
Remplaza en ocasiones a estructuras repetitivas.
Este concepto será de
gran utilidad para el capítulo de la estructura de datos tipo árbol.
La recursividad es un
concepto difícil de entender en principio, pero luego de analizar diferentes
problemas aparecen puntos comunes.
En Java los métodos
pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí
mismo decimos que el método es recursivo.
Cuando un método se
llama a sí mismo, se asigna espacio en la pila para las nuevas variables
locales y parámetros.
Al volver de una llamada
recursiva, se recuperan de la pila las variables locales y los parámetros
antiguos y la ejecución se reanuda en el punto de la llamada al método. Recursión es una
técnica de programación en el cual un método puede llamarse a sí mismo. La recursión es muy interesante
y una técnica efectiva en programación ya que puede producir algoritmos cortos
y eficientes.
Algo es recursivo si se define en términos de sí mismo
(cuando para definirse hace mención a sí mismo).
Si la invocación de un subprograma (función o subrutina) se
produce desde el propio subprograma se dice que se trata de un subprograma
recursivo.
Un método recursivo es un método, directa o indirectamente,
se hace una llamada a sí mismo.
La recursión consiste en el uso de métodos recursivos.
Procedimientos
recursivos
Los
procedimientos recursivos o recurrentes se pueden clasificar en dos formas
distintas:
- Recursividad
directa o
- Recursividad
indirecta
La recursividad
directa se presenta cuando el método se manda llamar a sí mismo dentro
de su propio cuerpo de instrucciones.
public int Metodo(int n)
{
:
n
= Metodo(n-1);
}
La recursividad
indirecta se manifiesta cundo un método llama a otro y dentro del
segundo se manda llamar al primero. O cuando existe la llamada a métodos de
forma encadenada y al terminar el último método llamado, transfiere el control
al anterior, hasta llegar al método que inicio la serie de llamadas.
public int Metodo1(int n)
{
:
n
= Metodo2(n-1);
}
public int Metodo2(int n)
{
:
n
= Metodo1(n-1);
}
Analizando
el concepto de recursividad y su clasificación, puede indicar que es
un procedimiento infinito, que solo se detendrá en el momento que se agote la
memoria, generando un error de programación y la interrupción del mismo.
Pero
esto no es así, ya que debe existir un elemento que indica el retorno de un
resultado concreto y no el retorno de la llamada al método recursivo o
recurrente.
Forma
de generar la recursividad
Un problema clásico:
El factorial de un número.
Todos conocemos que
la definición matemática del factorial de un número n se obtiene de la
siguiente forma:
n! = 1*2*3*.......*n
ó n! = n*(n-1)*(n-2)*.....1
Por definición
matemática, también sabemos que:
0! = 1
Con lo que tendríamos
la siguiente definición de factorial:
|
n!
|
1
|
Si n=0
|
Caso Base
|
|
n*(n-1)
|
Otros casos
|
Parte Recursiva
|
Un problema que
puede resolverse de manera recursiva, debe tener por lo menos caso base y 1
parte recursiva, sino no hay recursión.
Ahora,
para implementarlo en un lenguaje de programación como Java, solo tenemos que
traducir nuestros casos bases y partes recursivas:
Funcionamiento del proceso
|
n
|
Llamado a factorial
|
|
4
|
4*factorial(3)
|
|
3
|
3*factorial(2)
|
|
2
|
2*factorial(1)
|
|
1
|
1*factorial(0)
|
|
0
|
1
|
En
general el proceso es (4*factorial(3*factorial(2*factorial(1*factorial(0)))))
Realizar
de manera recursiva la sumatoria de n números naturales de manera recursiva.
La
sumatoria de n números se realiza de la siguiente forma:
n=10
1+2+3+4+5+6+7+8+9+10
= 10+9+8+7+6+5+4+3+2+1
De
tal forma que podemos determinar que:
1 si
n = 1 paso
básico
n +
(n-1) si
n > 1 paso
inductivo o proceso recursivo
//5+suma(4+suma(3+suma(2+suma(1))))
Imprimir
de manera recursiva la serie de fibonnaci
La serie de fibonacci
trabaja de la siguiente forma:
Paso 1: Si tenemos
dos semillas formadas por s1=0 y s1=1
0 1
Paso 2. Se suman para
obtener el resultado
0 1 1
Ahora la semilla 1 se
queda con el valor de la semilla 2 y el resultado se asigna a la semilla 2 y se
vuelve a realizar el paso 2. De tal forma que la serie queda de la
siguiente forma:
0 1 1 2 3 5 8 13 21
34 55 89 ………….
Fibonnacci de manera
recursiva
Fibonacci(0,1,21)=1
Fibonacci(1,1,21)=2
Fibonacci(1,2,21)=3
Fibonacci(2,3,21)=5
Fibonacci(3,5,21)=8
Fibonacci(5,8,21)=13
Fibonacci(8,13,21)=21
Realizar
de manera recursiva la potencia de un número para n.
El
cálculo de la potencia de un número se resuelve de la siguiente manera.
Xp=X*X(p-1)*X(p-2)*X(p-3)……=
25= 2 * 2 * 2 * 2 * 2
Sabemos
que 20= 1 por lo que determinamos
1 si
p = 0 paso
básico
n *
(n,
p-1) si
p > 0 paso
inductivo
24 2*potencia(2*potencia(2*potencia(2*potencia(2,0))
Potencia(2,4)=2*potencia(2,3)=16
Potencia(2,3)=2*potencia(2,2)=8
Potencia(2,2)=2*potencia(2,1)=4
Potencia(2,1)=2*potencia(2,0)=2
Potencia(2,0)=1
Realizar
el producto de un número por sumas sucesivas de manera recursiva.
El
producto de un número (3*9) se realiza de la siguiente forma:
1 2 3 4 5 6 7 8 9
3+3+3+3+3+3+3+3+3
cant
=0 0 caso
base
n+(cant-1) proceso
recursivo
Realizar
de manera recursiva como calcular un número en binario a través de
desplazamientos sucesivos
La
manera de convertir a binario un número es de la siguiente forma:
Si es
para un número de ocho bits el rango de valores abarca de 0 a 255, si es en ese
caso se debe de utilizar una máscara de 0x80. Que representa a un
número en binario 10000000 es decir el último bit en 1.
Se
realiza una operación (AND)& a nivel de bits del número a convertir y si el
resultado es cero entonces ese representa al primer valor del número en binario
y si no es cero entonces este lo representa.
Posterior
a esto se desplaza el bit una posición a la derecha y se vuelve a hacer la
misma operación & y nos vuelve a dar como resultado 0 o un numero diferente
de 0.
Este
proceso se repite hasta que se llegue hasta el final # de bits. En este caso 8
iteraciones.
Ejemplo:
Numero
a convertir es 13
La
máscara es 0x80=10000000
13
en binario es 00001101
La
máscara es 10000000
Resultado & 00000000 da
el primer valor del número convertido 0
Se
repite el mismo proceso pero con el bit 1 de la máscara recorrido una posición
a la derecha.
13
en binario es 00001101
La
máscara es 01000000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00100000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00010000
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00001000
Resultado & 00001000 da
el primer valor del número convertido 1
13
en binario es 00001101
La
máscara es 00000100
Resultado & 00000100 da
el primer valor del número convertido 1
13
en binario es 00001101
La
máscara es 00000010
Resultado & 00000000 da
el primer valor del número convertido 0
13
en binario es 00001101
La
máscara es 00000001
Resultado & 00000000 da
el primer valor del número convertido 1
unidad 4 programa metodo busqueda
ASIGNATURA:
ESTRUCTURA Y ORGANIZACIÓN DE DATOS
CLAVE:
TIC-1002
PROFESORA:
ING. ROMÁN NÁJERA SUSANA MÓNICA
TEMA:
EJEMPLO UN PROGRAMA QUE EMPLEE UN MÉTODO DE BÚSQUEDA EN
JAVA
(BÚSQUEDA BINARIA)
NOMBRE:
MELÉNDEZ CLARA DANEL
SEMESTRE: 3er GRUPO:3E
SALINACRUZ,
OAXACA; DICIEMBRE DEL 2014.
METODOS DE BUSQUEDA
La
búsqueda es la operación más importante en el procesamiento de información, ya
que permite recuperar datos previamente almacenados. El resultado de una
búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no
la encuentra.
La
búsqueda se puede aplicar sobre elementos previamente ordenados o sobre
elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio
en el segundo se dificulta un poco más el proceso, sobre todo cuando de se
trata de encontrar una cantidad de elementos similares.
Los
métodos de búsqueda se clasifican en:
- Búsqueda interna.
- Búsqueda externa.
Búsqueda
interna.
La
búsqueda interna es aquella en la que todos los elementos de la estructura
estática (arreglo) o dinámica (lista ligada o árbol) se encuentran almacenados
en la memoria principal de la computadora.
Los
métodos de búsqueda interna más importantes son:
- Secuencial o lineal.
- Binaria.
- Hash (transformación de claves)
Secuencial.
El
método de búsqueda secuencial consiste en revisar la estructura de datos
elemento por elemento hasta encontrar el dato que estamos buscando, o hasta
llegar al final de la estructura de datos.
Normalmente
cuando una función de búsqueda concluye con éxito, lo que interesa es conocer
en qué posición fue encontrado el elemento buscado.
La
búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o
desordenadas.
Si
se aplica a una estructura desordenada y el elemento que se está buscando
existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta que se llegue al fin de la estructura.
El método de búsqueda binaria divide
el total de los elementos en dos, comparando el elemento buscado con el
central, en caso de no ser iguales, se determina si el elemento buscado es
menor o mayor al central, para determinar si la búsqueda continua del lado
izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de
división y comparación, hasta encontrar el elemento buscado o que la división
ya no sea posible.
Debemos destacar que este método de búsqueda
solo funciona con estructuras de datos previamente ordenadas, dividiendo cada
vez a la mitad el proceso de búsqueda, lo que hace que el método sea más
eficiente.
Ejemplo. Si tenemos una
estructura ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el número
5, el resultado de la búsqueda nos mostraría la posicione 4 y el
proceso terminaría ya que el elemento buscado no es diferente al que esta en la
posición central.
|
Elementos
|
0
|
1
|
2
|
3
|
5
|
5
|
5
|
7
|
8
|
9
|
|
Posiciones
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
Posiciones donde
encontró el número 5
|
i
|
|
|
|
√
|
|
|
|
|
F
|
Este proceso debe sumar la posición inicial y la
final, dividiendo el resultado de la suma entre dos para obtener la posición central
generada por el cociente de la división, en este caso es (0+9)/2 = 4, esta
posición se compara con el elemento que estamos buscando y como son iguales la
búsqueda se detiene mostrando la posición donde lo encontró.
EJEMPLO
DE UN PROGRAMA EN JAVA (METODO BINARIO)
Este
método es una técnica eficaz para realizar búsquedas en vectores o archivos que
contengan un mayor número de datos. Este método divide el vector en mitades de
manera sucesiva hasta que encuentra el dato buscado, es decir, el método divide
el vector y se examina el elemento central del vector.
Si
es el elemento que se busca, entonces la búsqueda finaliza, pero si no se
determina si el dato buscado está en la primera o la segunda mitad del vector y
se repite el proceso en la nueva mitad, buscando su elemento central. Para
realizar la búsqueda binaria el vector debe estar ordenado y se comienza
comparando con el elemento central.
Implementación
del algoritmo de búsqueda binaria de manera no recursiva en Java. Se utiliza
una función estática de la clase BusquedaAlgoritmo. Recordar que para que
funcione correctamente los valores del arreglo deben estar ordenados.
public static int buscar( int
[] arreglo, int dato) {
int inicio = 0;
int fin = arreglo.length - 1;
int pos;
while (inicio <= fin) {
pos = (inicio+fin) / 2;
if ( arreglo[pos] == dato )
return pos;
else if ( arreglo[pos] < dato ) {
inicio = pos+1;
} else {
fin = pos-1;
}
}
return -1;
}
}
public static void main (String args[]) {
// Llenar arreglo
int [] edades = new int [35];
for (int i = 0; i < edades.length ;
i++)
edades[i] = i*i ;
// Mostrar arreglo.
for (int i = 0; i < edades.length ;
i++)
System.out.println ( "edades["+i+"]: "+
edades[i]);
int resultado =
BusquedaAlgoritmo.buscar(edades, 9);
if (resultado != -1) {
System.out.println ( "Encontrado en: "+
resultado);
} else {
System.out.println ( "El dato no se encuentra en el
arreglo, o el arreglo no está ordenado."
);
}
}
}
Para
poder ejecutar el Método de Búsqueda Binaria, se debe de contar con un Array
ordenado. El procedimiento que se realiza es el siguiente:
•EL
Programa internamente selecciona el elemento central del Array.
•Si
el elemento a buscar es el dato central el proceso termina. •Si el elemento a
buscar no coincide con el elemento central, continua la búsqueda:
•Se
subdivide en dos partes al Array.
•Si
el elemento a buscar es menor que el dato central, entonces selecciona la mitad
de la parte izquierda.
•La
parte seleccionada se subdivide nuevamente y se repite todo el proceso.
•El
proceso termina cuando el dato es encontrado; teniendo en cuenta que el dato a
buscar no puede encontrarse en el Array.
Suscribirse a:
Entradas (Atom)