Fortaleza Reznor
algoritmos FLVP3jF¡Bienvenido a Fortaleza Reznor!
¿Que es Fortaleza Reznor?
Fortaleza Reznor es un foro de SMWH (Super Mario World Hacking) Aquí modificamos (hackeamos) el juego de Mario World a nuestro gusto y enseñamos a otros a saber a manejar el hacking de SMW usando la famosa herramienta "Lunar Magic".

¡Regístrate!
Únete a nuestra comunidad!, te ayudaremos en cada duda que tengas respecto al SMWH. Aparte podrás participar en eventos que hay en el foro y descargar los recursos que crean nuestros usuarios.

¡ANÍMATE! ¡Te divertirás en nuestro foro!

Atte:
La administracion.


¡Super Mario World Hacking en español! ¡Ayuda, tips, diversión y más!
 
ÍndiceMiembrosRegistrarseConectarseBuscar

Comparte
 

 algoritmos

Ver el tema anterior Ver el tema siguiente Ir abajo 
AutorMensaje
anonimzwx
Blue Masked Koopa
Blue Masked Koopa
anonimzwx

Posts Posts : 1214


algoritmos Empty
MensajeTema: algoritmos   algoritmos EmptyDom Sep 16, 2012 2:22 pm

para los interesados en el area de investigacion en computacion y recien parten en este rollo les dejo algunos algoritmos que son utiles para algunas cosas.
Todo estara en pseudocodigo.

ordenamiento:

quick sort:

parametros: un arreglo desordenado de cosas que tengan algun factor para ordenarlos supongase numeros
retorna: el mismo arreglo pero en orden

metodo:

pivote = primer elemento del arreglo (enrealidad este puede cualquier elemento del arreglo y se puede mejorar mucho el metodo dependiendo de la eleccion del pivote)

listamenores

listamayores

for(int i = 0;i if(arreglo[i] < pivote)
listamenores.add(arreglo[i])
else
listamayores.add(arreglo[i])
endFor

listamenores = quicksort(listamenores)
listamayores = quicksort(listamayores)

retornar concatenacion(listamenores,pivote,listamayores)

Orden caso promedio: O(n*log(n))
Orden peor caso: O(n^2)

Heaps y Heapsort

un heap es un arbol binario que tiene 2 propiedades especiales.
primera propiedad: cada hijo de un nodo es menor que su padre.
segunda propuedad: el arbol se llena por nivel de izquierda a derecha siempre.
como resultado de esto el nodo raiz siempre es el menor elemento del arreglo.

Restricciones:
El heap solo tiene accseso al nodo menor. aunque internamente los metodos pueden usar otros nodos aunque esto se ocupa solo para el ultimo.

metodos de un heap:
insertar: se inserta el nodo y se ordena para que cumpla esas propiedades no dejare el algoritmo aca.
remover: se remueve el primer nodo, para hacer esto se remueve el ultimo nodo para evitar problemas con la estructura del heap y luego se cambia el primer nodo con el ultimo y se ordena el heap.
Get: solo tiene informacion del nodo menor.

Orden de cada algoritmo: O(log(n))

Heap Sort:
parametro un arreglo.
retorna el arreglo ordenado.

insertar todos los elementos del arreglo en un heap.
eliminar el arreglo
remover cada elemento del heap al arreglo
retornar el arreglo.

Orden general: O(n*log(n))

no pondre merge sort no otro algoritmo por que por lo general es inferior a estos algoritmos ademas que no me gusta xd.

Busqueda:

arbol binario de busqueda:

un arbol binario de busqueda es un arbol con una propiedad especial.
el hijo izquierdo es menor al padre y el hijo derecho es mayor al padre.

Busqueda en un arbol binario:
parametro: arbol binario de busqueda, elemento que se busca.
retorna: el nodo con el elemento que se busca

aux = raiz del arbol

while(aux!=null)
if(aux.e= elemento)
retorna aux
if(aux.e aux = aux.hijoizq
else
aux = aux.hijoder
endWhile
retorna null

Orden: O(log(n))

Busqueda binaria:
parametro: arreglo en orden, elemento que se busca
retorna elemento

int inicio = 0
int final = arreglo.length-1
while(inicio < final)
pivote = arreglo[(inicio+final)/2]
if(pivote.e == elemento) retornar pivote
if(pivote.e < elemento)
final = (inicio+final)/2 -1
else
inicio = (inicio+final)/2 +1
retornar nulo

Orden: O(log(n))

Busqueda de caminos o soluciones

Busqueda ciega en general:
parametros: posicion inicial o estado inicial y posicion o estado final
retornar camino

Lista Closed = null
Lista open = primer nodo con el estado inicial

mientras no se encuentre el estado final o no alla mas elementos a revisar

reviso si el prime elemento de open es el estado final

Extender el primer elemento de open (osea ver que nodos de el primer elemento de open revisare)

a closed le agrego el elemento extendido de open

open le quito el elemento extendido

a open le agrego los elementos que fueron extendidos al final de la lista

formas de usar este algoritmo:

Busqueda por alcanze:

Extiendo los elementos de forma de que los elementos extendidos son todos los hijos del el elemento que extiendo.

ventajas: siempre encuentro el camino mas corto.
desventaja: mucho uso de memoria

Busqueda en profundida:

cuando extiendo un voy en orden de izquierda a derecha, osea extiendo a 1 solo camin a la ves de izquierda a derecha.

Ventaja: poco uso de memoria:
Desventaja: no es el mejor camino.

Busqueda en profundidad con restriccion.

uso Busquedad en profundidad pero hasta cierto nivel, si la respuesta no esta en ese nivel o menor, amplio la restriccion a un nivel mas abajo.

Ventaja: poco uso de memoria y el camino es 1 de los mas cortos
Desventaja: sigue siendo busqueda ciega.


lo demas lo ire llenando cuando tenga tiempo espero les sirva igual es un poco basico para los que estan en esta area pero para los que no saben nada, o recien estan aprendiendo les puedo echar una mano.
Volver arriba Ir abajo
 

algoritmos

Ver el tema anterior Ver el tema siguiente Volver arriba 
Página 1 de 1.

Permisos de este foro:No puedes responder a temas en este foro.
Fortaleza Reznor ::  Convivencia Seria :: Computación y tecnología-