Warning: Illegal string offset 'userid' in [path]/includes/functions.php on line 509

Warning: Illegal string offset 'userid' in [path]/includes/functions.php on line 512

Warning: Illegal string offset 'membergroupids' in [path]/includes/functions.php on line 441

Warning: Illegal string offset 'membergroupids' in [path]/includes/functions.php on line 443

Warning: Illegal string offset 'usergroupid' in [path]/includes/functions.php on line 452

Warning: Illegal string offset 'usergroupid' in [path]/includes/functions.php on line 518

Warning: Illegal string offset 'userid' in [path]/includes/functions.php on line 518

Warning: Illegal string offset 'usergroupid' in [path]/includes/functions.php on line 518

Warning: Illegal string offset 'userid' in [path]/includes/functions.php on line 518
Fibonacci
Comunidad Underground Hispana  

Retroceder   Comunidad Underground Hispana > Programacion > Batch


Respuesta Crear Nuevo Tema
 
Compartir en twitter LinkBack Herramientas Desplegado
Antiguo 21-ago-2008, 06:47   #1
ECDundy
Guest
 
Amigos
Mensajes: n/a
Predeterminado Fibonacci

He elaborado este método que devuelve el término n-ésimo de la sucesión de Fibonacci. El primer y segundo términos de la sucesión de Fibonacci son 1. El término k de la sucesión de Fibonacci se obtiene sumando los términos k-1 y k-2 de la sucesión de Fibonacci. {1, 1, 2, 3, 5, 8, 13, 21, …}
Para los que no estan relacionados con el tema pueden aprender sobre la sucesión de Fibonacci en

[Solo usuarios registrados pueden ver los links. REGISTRARSE]


aunque no estoy seguro que la fuente sea confiable ya que erroneamente asegura que el primer termino de la sucesión es 0 inclusive en la grafica la ponen como que comienza en 0 pero luego mas abajo se contradice(Cosas que pasan en wikipedia :).
Cita:
:Fibonacci
if %1 leq 0 (echo Invalid Operation Exception&goto:END)
if %1 lss 3 (echo 1&goto:END) else (call :major %1&goto:END )
:major
set minusone=1
set minustwo=1
FOR /L %%a IN (3, 1, %1) do call :sum
echo %fib%
:sum
set /A fib=%minusone% + %minustwo%
set minustwo=%minusone%
set minusone=%fib%
goto:END
para poder ver los 10 primeros terminos puede hacerlo de la siguiente manera...
Cita:
@echo off
FOR /L %%a IN (0, 1, 10) do Call :Fibonacci %%a
pause
saludos
  Responder Citando
Antiguo 21-ago-2008, 07:03   #2
alesteir
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Buen modulo.
  Responder Citando
Antiguo 21-ago-2008, 12:44   #3
Miembro
 
Fecha de Ingreso: julio-2008
Amigos 0
Mensajes: 74
Gracias: 0
Agradecido 0 veces en 0 mensajes.
Predeterminado Re: Fibonacci

Mira lo k sucede con la sucesion de fibonacci es k cmo el siguiente termino es igual a la suma d elos dos anteriores osea 1,1,2,3 si nos fijamos 2 es igual a 1+1, y 3=2+1 en tonces en caso de k hubiera un cero al inicio no seria algo loco del todo, ya k el segundo mienbro es uno y 1+0=1, por esa razon es k en algunos lugares aparece el cero en la sucesion, pero en la mayoria de los lenguaje ssi usas cero t dara un error¡

esta muy bien tu programa lo unico k me encuentro k en batch es uy complicado una vez yo hice la serie de fivonacci pero en visual basic 6.0 y es mucho mas facil XD
__________________
Dile no a las drogas somos muchos y hay poca¡¡¡<br />att:CooL MasteR
master28 está desconectado   Responder Citando
Antiguo 22-ago-2008, 22:44   #4
SMARTGENIUS
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

esto es lo que se llama recursividad... ???

corrrijanme..porfa xD xD
  Responder Citando
Antiguo 23-ago-2008, 01:33   #5
ECDundy
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

no brother eso es una iteracion comun y corriente. En bath me costo un poco darme cuenta. Ya que de todas todas yo tenia que lograr la recurcion en bath. Pero no se puede hacer recursividad en todo su rango. Aunque si en algunas cosas.
Recursividad es cuando un metodo se llama asi mismo en un proseso totalmente independiente en cada llamada. Para resolver un problema...
Luego en bath una vez que llamas a la etiqueta desde dentro. El codigo se detiene y regresa como lo que es un bucle, no de manera independiente...
Este ejemplo que te hago desde el punto de vista recursivo es lo minimo que supongo se puede hacer en bath y aun asi sigue perteneciendo a la familia bucle...
Cita:
@echo off
call :Rotate 1 2 3
:Rotate %1 %2 %3
set p=0
:recur
echo %1 %2 %3
set /a p+=1
if not %p% == 4 (call :recur %2 %3 %1)
pause
Cita:
Salida
1 2 3
2 3 1
3 1 2
1 2 3
Esto definitivamente se puede ver como recursividad desde un punto de vista. Pero desde otro menos abstracto solo es un salto de codigo que se le ordena al compilador. Quizas por eso en los otros lenguajes los programadores piden la eliminacion del goto...
increiblemente la funcion goto es algo que aparece en casi todos los lenguajes
pero ha sido historicamente criticado. Con call haces lo mismo que con goto pero en su lugar le estas diciendo al compilador que tome los parametros. Es por eso que en bath no existen metodos mas bien etiquetas por que en resumen el metodo viene siendo todo el codigo. Se que fue a proposito inclusive a veces me aventuro a programar cosas en bath que se que no tienen sentido en este lenguaje. Pero fue creado solo para eso. Para que sea una herramienta de otros programas para trabajar con windows ...
La verdad es que no hay que subestimar. No al bath(por que en realidad es obsoleto) sino a la imaginacion de los programadores.
Ya han dicho que bath no tiene compilador y es un error. Que sucede, que la parte de compilacion de bath es muy pobre y es lo que nos impide hacer tantas cosas como quisieramos... Todo cuanto ciclo for haces, todos los comandos y todas las llamadas que realizas requieren de un compilador por tanto lo tiene...
ok saludos
  Responder Citando
Antiguo 23-ago-2008, 02:48   #6
SMARTGENIUS
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

bien, grax por la explicacion....
  Responder Citando
Antiguo 23-ago-2008, 11:04   #7
Scofield
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

igual smart te aclara mas esto.

Un algoritmo recursivo es aquel que implementa un procedimiento por el cual, se invoca a si mismo.

Por ejemplo:
Código:
factorial 0 = 1            <-------- caso basico
factorial x = x*factorial(x-1) <------- recursividad
  
para implementar la recursivodad en un lenguaje de programacion, han de poder definirse procedimientos o funciones para que ellas puedan invocarse a si mismas.
Como puedes ver, la recursividad seria un bucle infinito (que acabaria dando una excepcion control stack overflow al agotar la memoria) si no conseguimos detenerla en algun momento, para salir de un bucle recursivo es necesario poner un caso basico.

Por ejemplo, supongamos que invocamos a factorial con el argumento 3:

factorial(3)
no es caso basico => se guarda en la pila (memoria) del programa el valor 3 y se invoca a factorial(2).
no es caso basico => se guarda en la pila (memoria) del programa el valor 2 y se invoca a factorial(1).
no es caso basico => se guarda en la pila (memoria) del programa el valor 1 y se invoca a factorial(0).
si es caso basico => se guarda en la pila (memoria) del programa el valor 1 y se multiplican los valores acumulados en la pila => 3*2*1*1.
se devuelve el valor 6.

es decir:
factorial(3)=3*factorial(2)=3*2*factorial(1)=3*2*1 *factorial(0)=3*2*1*1=6

hay lenguajes que van acumulando el resultado y lo van multiplicando en lugar de hacerlo al final, pero que sirva como ejemplo.

en caso de que no hubiera caso basico, el programa continuaria una vez llegado al cero:
se guarda en la pila (memoria) del programa el valor 1 y se invoca a factorial(0).
se guarda en la pila (memoria) del programa el valor 1 y se invoca a factorial(-1).
se guarda en la pila (memoria) del programa el valor -1 y se invoca a factorial(-2).
se guarda en la pila (memoria) del programa el valor -2 y se invoca a factorial(-3).

y, como no hay condicion de parada, el programa no terminaria nunca. Como la memoria es limitada, llega un momento que la memoria asignada al programa se agota y este "se rompe" dando un error o excepcion, el cual es como decia un "control stack overflow".

Eso mismo puede ocurrir si invocamos al programa con un valor demasiado grande, agotamos la memoria y el programa se va a la mierda.

saludos!
  Responder Citando
Antiguo 24-ago-2008, 04:10   #8
ECDundy
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Si como te ha dicho sami... Hay 1 cosa que no puede faltar en recursividad...
el caso base y el caso de parada que en multiples ocaciones es el mismo...

mi solucion a Fibonacci recursivo en c#
Cita:
public static long Fibonacci(int n)
{
if (n <= 0) throw new InvalidOperationException();
else return (n <= 2) ? 1 : Fibonacci(n - 2) + Fibonacci(n - 1);
}
public static long fibonacci(int n) es el metodo que recibe un parametro n de tipo int....
luego el codigo solo tiene 2 comodas lineas para la solucion...
Ahora una solucion iterativa nueva mente public static long Fibonacci2(int n)
es el metodo que recibe un objeto n de tipo int...
Cita:
public static long Fibonacci2(int n)
{
if (n <= 0) throw new InvalidOperationException();
if (n < 3) //los dos primeros terminos son 1
return 1;
else // a partir del tercero
{
int eneMenosUno = 1;
int eneMenosDos = 1;
int contador = 2;
int fib;
do
{
contador++; //término que calcula esta iteración
fib = eneMenosDos + eneMenosUno; //calcular término
//preparo las variables para la próxima vuelta
eneMenosDos = eneMenosUno;
eneMenosUno = fib;
} while (n != contador);
return fib;
} //fin else
}
para este caso el costo recursivo es mucho menor que el iterativo...
luego recusividad es algo de lo cual yo en especial no podria precindir...
quizas si en bath hubiera alguna manera de asignarle valores a los parametros que recibimos en las etiquetas la recursividad seria un hecho menos anacronico...
  Responder Citando
Antiguo 28-ago-2008, 21:22   #9
plof
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Cita:
Iniciado por ECDundy
luego recusividad es algo de lo cual yo en especial no podria precindir...
...y más aún si trabajas con árboles .

Resulta que andaba ojeando unos apuntes para los examenes y me encontré con un método Divide y Vencerás que resuelve el problema de la sucesión de Fibonacci de forma más eficiente.
La técnica Divide y Vencerás se centra en dividir el problema en varios subproblemas del mismo tipo que el original y deben tener casi el mismo tamaño. Después va racombinando las soluciones de los subproblemas.
Menudo rollo :-\\

¿¿Pero como se divide el problema de Fibonacci con la técnica DIV??
La resolución trivial es fn = fn-1 + fn-2 , que es bastante ineficiente.

Pero podemos considerar el siguiente sistema de ecuaciones:

fn = fn
fn-1 + fn = fn+1

....que se puede expresar por su notación matricial:

[ 0 1 ] [ fn-1 ] [ fn]
[ 1 1 ] [ fn ] = [ fn+1]

Sabiendo que f0=0 y f1=1, al aplicar la fórmula anterior n veces tenemos:
n
[ 0 1 ] [ 0 ] [ fn ]
[ 1 1 ] [ 1 ] = [ fn+1]

o, lo que es lo mismo:
n
[ 0 1 ] [ fn-1 fn ]
[ 1 1 ] = [ fn fn+1]

..... ¿¿y qué quiere decir todo esto??
Pues que la solución de fibonacci consiste en calcular una matriz elevada a la n-ésima potencia:
n
[ 0 1 ]
[ 1 1 ]

y para dividir este problema en subproblemas más pequeños pues tendremos en cuenta lo siguiente:

|
| a^n/2 * a^n/2 si n es par
an = -
| a^(n-1)/2 * a^(n-1)/2 * a si n es impar
|
Dónde a puede ser un número real, una matriz....
y a^n/2 se lee 'a' elevado a 'n/2'

El algoritmo quedaría algo como esto:

matriz_fibbo = [ 0 1 ]
[ 1 1 ]

Llamamos a DIV_Fibonacci ( n-1 );

DIV_Fibonacci ( n )
{
Si ( n = 1) <<- Caso Base!
Devolvemos matriz_Fibbo

En caso contrario {
Si ( n % 2 = 0 ) { <<= Tamaño par
matriz = DIV_Fibonacci ( n/2 );
Devolvemos matriz * matriz
}
En caso contrario { <<= Tamaño impar
matriz = DIV_Fibonacci ( n/2 - 1 );
Devolvemos matriz * matriz * matriz_Fibbo
}
}
}

De esta forma DIV_Fibonacci devuelve una matriz solución en la cual la fila 2 y columna 2 se encuentra el término n+1-ésimo de la sucesión (tomando f0 = 0).
Si vas a implementarlo en c, la función recursiva podría devolver un ptro a un vector estático long int.... no hacen falta matrices .
Un vector auxiliar para la multiplicación de matrices y otro para guardar la matriz_fibbo.
No necesitas reserva dinámica de memoria ya que son sólo 3 vectores de tamaño 4.

Si alguien tiene alguna duda.....

*salud

pd. me alegro que andes por aquí otra vez ECDundy.
  Responder Citando
Antiguo 29-ago-2008, 06:17   #10
ECDundy
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Interesante plof. Pero no veo el aquello de que es mas optima...
Ademas como vas a devolver una matriz si lo que se te pide es un termino enesimo...
Apartando que esto sea un foro bath y todo eso...
por que no publicas el codigo en cualquier lenguaje...
a ver si comprendo mejor. Por que he entendido la explicacion pero nada de nada de tu explicacion programable. De hecho destruye toda idea que tenia al respecto de tu manera de solucionar el problema
  Responder Citando
Antiguo 29-ago-2008, 12:08   #11
plof
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Un dato curioso:
Cita:
Iniciado por Fibonacci
Imaginemos una pareja de conejos, macho y hembra, encerrados en un campo donde pueden anidar y criar. Supongamos que los conejos empiezan a procrear a los dos meses de vida, engendrando siempre un único par macho-hembra, y a partir de ese momento, cada uno de los meses siguientes un par más de iguales características. Admitiendo que no muriese ninguno de los conejitos, ¿cuántos pares contendría el cercado al cabo de un año?.
El problema trata de contar cuántos conejos llegan a parir ;D.

Un caso práctico.
Vamos a calcular el término 9 de la sucesión de fibonacci o lo que es lo mismo:
Código:
    9
[ 0 1 ]
[ 1 1 ]
  
Llamadas recursivas....
1. (n=9) Dividimos el problema en 1 subproblema de tamaño (n-1)/2 porque n es impar.
Código:
    9
[ 0 1 ]
[ 1 1 ]
  
2. Dividimos el problema en 1 subproblema de tamaño n/2
Código:
    4
[ 0 1 ]
[ 1 1 ]
  
3. Dividimos el problema en 1 subproblema de tamaño n/2
Código:
    2
[ 0 1 ]
[ 1 1 ]
  
4. CASO BASE!!
Código:
    1
[ 0 1 ]
[ 1 1 ]
  
Retrocedemos en las llamadas recursivas y vamos multiplicando....
3.
Código:
 
    2   
[ 0 1 ]      [ 0 1 ]     [ 0 1 ]    [ 1 1 ]
[ 1 1 ]   =  [ 1 1 ]   *  [ 1 1 ] =  [ 1 2 ]
  
2.
Código:
 
    4   
[ 0 1 ]      [ 1 1 ]     [ 1 1 ]    [ 2 3 ]
[ 1 1 ]   =  [ 1 2 ]   *  [ 1 2 ] =  [ 3 5 ]
  
1.
Código:
 
    9   
[ 0 1 ]      [ 2 3 ]     [ 2 3 ]    [ 0 1 ]   [ 13 21 ]
[ 1 1 ]   =  [ 3 5 ]   *  [ 3 5 ]  *  [ 1 1 ] =  [ 21 34 ]
  
La matriz solución indica que tn-1 = 13, tn=21 y tn+1=34.
Como puedes observar, para encontrar el término n-ésimo de la sucesión de Fibonacci basta con calcular:
n-1
[ 0 1 ]
[ 1 1 ]
...y tomar la fila 2 y columna 2 de la matriz solución, es decir, tn+1.


Dudas:
Cita:
Iniciado por ECDundy
Interesante plof. Pero no veo el aquello de que es mas optima...
Este tipo de diseños se crearon para problemas con un tamaño muy elevado.
Imagina por un momento que queremos calcular el término 1000 de la sucesión de fibonacci. Con un algoritmo 'divide y vencerás' se simplifica el problema en calcular el término 500 de la sucesión y una simple multiplicación de dos matrices. En otra pasada, divide el problema en otro subproblema de tamaño 250 y otra multiplicación........ y así hasta llegar al caso base.

En la práctica se suele calcular lo que se llama el 'umbral' que es un número de entradas por la cual es conveniente usar un algoritmo básico. Es decir, si el umbral es el término 100 de la sucesión de fibonacci, si queremos calcular el término 50 usamos un algoritmo básico como el que planteabas pero si sobrepasamos el umbral queriendo calcular el término 1000, por ejemplo, pues se utiliza el algoritmo 'divide y vencerás'.

El orden de eficiencia para el algoritmo divide y vencerás para resolver la sucesión de fibonacci es O ( log(n) ) .


Cita:
Iniciado por ECDundy
Ademas como vas a devolver una matriz si lo que se te pide es un termino enesimo...
La verdad es que no entiendo bien tu pregunta ya que con una función que llama a otra recursiva se soluciona ese detalle.

La matriz es una idea matemática para diseñar el problema. Si nos ponemos a recortar, con que la función recursiva nos devuelva tres enteros vamos sobrados, ya que en las matrices que se van generando, el término a01 = a10.


Cita:
Iniciado por ECDundy
Apartando que esto sea un foro bath y todo eso...
Vaya....no me había dado cuenta .
Siendo así aqui está el code Divide y Vencerás en batch para los primeros 60 términos de la sucesión:
Código:
@echo off
FOR /L %%a IN (1, 1, 60) do call:fibonacci %%a
pause
exit

:fibonacci
  set /a m00=0
  set /a m01=1
  set /a m11=1
  call:Divide_y_Veneceras %1
  echo (%1) = %m01%
goto:eof

:Divide_y_Veneceras
  set /a n=%1
  set /a par=%n%%%2
  set /a div1=%n%/2
  set /a div2=(%n%-1)/2
 
  if NOT %1 EQU 1 (
    if %par% EQU 0 (
      call:Divide_y_Veneceras %div1%
      call:multiplicar
    ) else (
      call:Divide_y_Veneceras %div2%
      call:multiplicar impar
    )
  )
goto:EOF

:multiplicar
  set /a p00=%m00%*%m00%+%m01%*%m01%
  set /a p01=%m00%*%m01%+%m01%*%m11%
  set /a p11=%m01%*%m01%+%m11%*%m11%

  if "%1"=="impar" (
    set /a m00=%p01%
    set /a m01=%p00%+%p01%
    set /a m11=%p01%+%p11%
  ) else (
    set /a m00=%p00%
    set /a m01=%p01%
    set /a m11=%p11%
  )
goto:EOF
  
Aunque el 'divide y vencerás' está pensado para un número de entradas realmente alto, podrás comprobar que mi algortimo genera los primeros 60 términos bastante más rápido.
De todas formas, el lenguaje batch no permite almacenar algunos términos por encima de 50.
Si te animas a una implementación en otro lenguaje te darás cuenta que a mayor término de la sucesión, mayor será la diferencia entre un algoritmo básico y otro 'divide y vencerás'.

La solución: otro lenguaje de programcación sin duda.

Cita:
Iniciado por ECDundy
por que no publicas el codigo en cualquier lenguaje...
Pense que un pseudocódigo sería lo más acertado...

Cita:
Iniciado por ECDundy
a ver si comprendo mejor. Por que he entendido la explicacion pero nada de nada de tu explicacion programable. De hecho destruye toda idea que tenia al respecto de tu manera de solucionar el problema
Espero que el ejemplo práctico de arriba te halla despejado cualquier duda.

*salud
  Responder Citando
Antiguo 29-ago-2008, 22:35   #12
ECDundy
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Pues hombre que ya lo he entendido.Plof Es que ya me andaba enredando yo con vectores especiales y todo eso ya sabes para poder trabajarlo realmente desde un punto de vista matricial. Y si despues de todo no andaba lejos. Pues de verdad gracias por tu explicacion tan constructiva supongo que ahora a nadie le quedara la menor duda jajjajajaa...
pues muchas gracias(valgame la redundancia)...
He estado observando y quizas parece obvio pero no estas convencido hasta que lo demuestras y la conclucion es simple "Todo problema con solucion iterativa tiene una solucion en bath". Luego en estos dias estare presentando algunas soluciones a problemas comunes...
un abrazo
  Responder Citando
Antiguo 30-ago-2008, 15:57   #13
plof
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

*brindis
  Responder Citando
Antiguo 30-ago-2008, 16:05   #14
Scofield
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Se puede obtener el termino n-esimo de la sucesion con complejidad constante pero no en batch ya que batch no dispone de suficiente potencial aritmetico.

La formula es:

r=raiz(5)
ir=1/r

fn = ir*((1+r)/2)^n - ir*((1-r)/2)^n
  Responder Citando
Antiguo 30-ago-2008, 16:23   #15
SMARTGENIUS
Guest
 
Amigos
Mensajes: n/a
Predeterminado Re: Fibonacci

Cita:
Iniciado por sami
Se puede obtener el termino n-esimo de la sucesion con complejidad constante pero no en batch ya que batch no dispone de suficiente potencial aritmetico.

La formula es:

r=raiz(5)
ir=1/r

fn = ir*((1+r)/2)^n - ir*((1-r)/2)^n
Yo pienso que puede ser posible, implementando una funcion de calculo de raices, mas el code de uso de decimales en batch....

para este: r=raiz(5)

y pues de igual forma una funcion de elevacion de numeros con ^

Saludos.
  Responder Citando
Respuesta

Herramientas
Desplegado

Normas de Publicación
No puedes crear nuevos temas
No puedes responder mensajes
No puedes subir archivos adjuntos
No puedes editar tus mensajes

Los Códigos BB están Activado
Las Caritas están Activado
[IMG] está Activado
El Código HTML está Desactivado
Trackbacks están Activado
Pingbacks están Activado
Refbacks están Activado



Temas Similares
Tema Autor Foro Respuestas Último mensaje
[F][bat] Sucesion de Fibonacci ---saster--- Batch 8 11-dic-2009 16:10
[F][bat]operador aritmetico con fibonacci hunter spectrum Batch 0 07-jun-2009 17:08
Sucesión Fibonacci RockoX Batch 3 11-abr-2009 15:47
Ayuda con conversion de decimal a binario y serie fibonacci jormen Carbide C/C#/C++ 6 26-jun-2007 23:32
Mi programa en MV C++ 6.0 ..Fibonacci WoodyWoodpecker Carbide C/C#/C++ 9 09-oct-2006 01:10



Portal Hacker
Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.6.0