Posts tagged ‘recursivo’

enero 13, 2010

Conversión de Millas a Kilómetros con Números Fibonacci

por Josue Ortega

En mi fría y ociosa tarde he aprendido un fact muy interesante: con los números de la serie de fibonacci podemos hacer conversiones de millas a kilómetros o viceversa.

Nunca creí que esta serie que más de alguna vez nos hizo pensar en un ejercicio de programación recursivo, o en la clase de matemáticas discretas cuando se ven ecuaciones de recurrencia, seria tan divertida  😛

bueno aquí viene la magia:

Tomamos 2 números de la serie consecutivos, por ejemplo 8 y 13, y YA! haha, 8 millas son el equivalente a 13 kilometros. sorprendente huh?

Para convertir de millas a kilómetros, tomamos el numero siguiente en la serie fibonacci, de kilómetros a millas tomamos el anterior en la serie…

Bueno seré mas exacto tomare otros 2 números: 21 y  34, según nuestro metodo 21 millas es el equivalente  a 34 km, haciendo calculos varios, 21 millas  son equivalentes a 33.7962 km  :D, una aproximación bastante buena :).

Pero que pasa cuando queremos calcular el equivalente de un número que no se encuentre en la serie, solo debemos expresar el numero que elegimos, en una suma de números fibonacci, por ejemplo, el numero si queremos saber el numero de millas que hay en 100 kilómetros, Para expresar 100 en numeros fibonacci seria: 89+8+5.

Cuando ya tenemos estos numeros calculamos el siguiente fibonacci de cada uno:

Siguiente de 89->144, siguiente de  8->13,siguiente de 5->8 (OJO NO SON PUNTEROS  HAHA )

ahora sumamos los siguientes de cada fibonacci: 144+13+8=162 km, al hacer nuestro calculo 100 millas son equivalentes a 160.93 km, bastante cerca de nuestro resultado :).

Ahora veamos que es lo que pasa, si calculamos las raíces de la ecuación de recurrencia de fibonacci  Fn = Fn-1 + Fn-2 obtenemos que una de las raíces es (1+√5)/2. Esta raíz es conocida en matemática como numero aureo:

Se trata de un número algebraico que posee muchas propiedades interesantes y que fue descubierto en la antigüedad, no como “unidad” sino como relación o proporción entre segmentos de rectas. Esta proporción se encuentra tanto en algunas figuras geométricas como en la naturaleza en elementos tales como caracolas, nervaduras de las hojas de algunos árboles, el grosor de las ramas, etc.

El número áureo repersentado con la letra griega φ(phi) es: 1.618033…

Y si notamos,es bastante cercano a la relación que existe entre millas y kilómetros(1.609), por lo que obtenemos resultados bastante aproximados entre los números de fibonacci y la relación que existe entre millas y kilómetros.

Casualidades de la vida.. 🙂

Anuncios
septiembre 28, 2009

Turorial: Parser Descendente Recursivo

por Josue Ortega

Bueno para los que se preguntan como hacer un parser a partir de una gramática que hemos diseñado, aquí le enseñare brevemente como hacer un parser descendente recursivo

Tenemos que tomar en cuenta lo siguiente:

1. Nuestra gramática no debe ser recursiva a la izquierda.Por ejemplo la producción

E::=Er

es recursiva  la izquierda, para este tipo de gramáticas nuestro parser no sería funcional, asi que hay que quitarle la recursividad a la izquierda

2.Debemos construir los conjuntos: First, Follow, para cada producción de nuestra gramatica.

Estructura del parser:

LookAhead: Esta variable(global), inicialmente es el token de mas a la izquierda de la entrada.

Por cada NO TERMINAL de la gramática debe existir un procedimiento del parser.Para hacer mas fácil su programación, el nombre del procedimiento tendrá el nombre del no terminal.

Cada una de las opciones del no terminal formaran el cuerpo del procedimiento.

Procedimiento Match: Con este procedimiento sabremos si es el TERMINAL correcto, lo detallare a continuación

void Match(token simbolo){
if(lookahead==simbolo)
lookahead=siguienteSimbolo;/* para obtener el siguiente simbolo se puede hacer un procedimiento para pedir el siguiente toke que recibimos del analizador lexico*/
else
ERROR
}

Bueno, ahora a programar, escribiré un parser para la siguiente gramática:

terminales: x,y,z;

E:=xP | H     /*  E produce x segido de la producción P ó la producción H       */

P:=Tz

H:=y

T:=yx;

****************************************************************

var token lookahead;//variable del tipo del token que ustedes utilicen

void main {

//Iniciar Scanner si s necesario

lookahead=nexToken() // funcion que devuelve el token siguiente

E();
}
void E(){
if(lookahead==x)
Match(x);
P();
else
H();
}
void P(){
T();
Match(z);
}
void T(){
Match(y);
Match(x);
}
void H(){
Match(z);
}

Y así de sencillo es un parser descendente Recursivo 🙂

Si se dan cuenta el parser recorre el árbol de arriba hacia abajo de allí viene descendente,

Y Recursivo se debe a que el parser puede llamarse a si mismo directa o indirectamente por medio de sus funciones 🙂

Espero que les sirva de algo,

Dudas, comentarios o sugerencias, no duden en escribir

saludos