SERIE DE FIBONACCI

SERIE DE FIBONACCI

En matemáticas, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:

El primer elemento es 0, el segundo es 1 y cada elemento restante es la suma de los dos anteriores. A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos.

Antes de que Fibonacci escribiera su trabajo, la sucesión de los números de Fibonacci había sido descubierta por matemáticos indios tales como Gopala (antes de 1135) y Hemachandra (c. 1150), quienes habían investigado los patrones rítmicos que se formaban con sílabas o notas de uno o dos pulsos. El número de tales ritmos (teniendo juntos una cantidad n de pulsos) era fn + 1, que produce explícitamente los números 1, 2, 3, 5, 8, 13, 21, etc.
La sucesión fue descrita por Fibonacci como la solución a un problema de la cría de conejos: "Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también".
De esta manera Fibonacci presentó la sucesión en su libro Liber Abaci, publicado en 1202. Muchas propiedades de la sucesión de Fibonacci fueron descubiertas por Édouard Lucas, responsable de haberla denominado como se la conoce en la actualidad.
También Kepler describió los números de Fibonacci, y el matemático escocés Robert Simson descubrió en 1753 que la relación entre dos números de Fibonacci sucesivos fn + 1 / fn se acerca a la relación áurea fi () cuanto más se acerque n a infinito; es más: el cociente de dos términos sucesivos de toda sucesión recurrente de orden dos tiende al mismo límite. Esta serie ha tenido popularidad en el siglo XX especialmente en el ámbito musical, en el que compositores con tanto renombre como Béla Bartók u Olivier Messiaen la han utilizado para la creación de acordes y de nuevas estructuras de frases musicales.

La serie de Fibonacci es una progresión numérica tal que para todo n perteneciente a N
F(1) = 1 F(2) = 1 F(n) = F(n-1) + F(n-2) ; para todo n > 2
Es decir, que los dos primeros términos de la sucesión son 1 y 1, y cada término sucesivo es la suma de los dos anteriores. Los primeros términos de esta sucesión son:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309...

ALGORITMO

var= res,vc,nt,a,b=entero

inicio

leer"numero de terminos=",nt

a<----0

b<----1

repetir con vc desde 1 hasta nt

si vc=1 entonces

escriba("0,1")

sino

res<---a+b

escribir("res")

a<---b

b<---res

finsi

fin repetir

terminar

SERIE DE FIBONACCI EN JAVA

package seriefibonacci;//paquete
import javax.swing.JOptionPane;//librerias

public class Serie {
private int res;//variable respuesta
private String num;//variable numero de terminos
private int a;//0
private int b;//1
public Serie(){
a=0;//inicializacion
b=1;
Solucion();//ir al metodo solucion
}
public static void main (String args[])
{
Serie x= new Serie();
}
public void Solucion(){
int num1;
num=JOptionPane.showInputDialog("Digite numero de terminos");//pedir el numero
num1=Integer.parseInt(num);//convertir a entero
if(num1==1){
JOptionPane.showMessageDialog(null,"0,1");
}
else{
for(int i=0;ires=a+b;//sumar los numeros de terminos
a=b;
b=res;
String salida="0,1"+"\nsiquiente:"+res;
JOptionPane.showMessageDialog(null,salida);
}
}
}
}

TORRES DE HANOI

TORRES DE HANOI

Las Torres de Hanoi es un juego matemático que consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en una varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento. El juego consiste en pasar todos los discos a otra varilla colocados de mayor a menor ascendentemente.

Leyenda: Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanoi divina. El día que estos monjes consigan terminar el juego, el mundo acabará. El mínimo número de movimientos que se necesita para resolver este problema es de 264-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en poco menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

Resolución: el problema de las Torres de Hanoi es curioso porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos. Para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:

El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).
La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

RESOLUCION

Mediante recursividad

Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi(origen,auxiliar,destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:
Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
Si no: hanoi({0...n+1},destino,auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
mover disco n-1 a destino //mover la ficha grande hasta la varilla final
hanoi(auxiliar,origen,destino) //mover todas las fichas restantes, {0...n+1}, encima de la ficha grande (n+1)
terminar
Resolución de la torre de cuatro discos

Iterativa

Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:
El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).
La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

Curiosidades

A la hora de resolver matemáticamente el problema, nos encontramos con muchas curiosidades matemáticas respecto a la resolución. Son las siguientes:
La ficha número n (siendo 1 la más pequeña) se mueve por primera vez en el paso número 2^(n-1), y después de ese primer movimiento, se moverá cada 2^n movimientos. De este modo, la ficha 1, se mueve en 1, 3, 5, 7, 9... etc. La ficha 3, se mueve en 4, 12, 20, 28, 32... etc
Todas las fichas impares (siendo 1 la más pequeña) se mueven siguiendo el mismo patrón. Asimismo, todas las fichas pares se mueven siguiendo el patrón inverso a las impares. Por ejemplo: si queremos mover un numero impar de piezas desde la columna 1 hasta la 3, sucederá lo siguiente:
· Todas las fichas impares seguirán este patrón de movimiento: 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1.
· Todas las fichas pares seguirán este patrón de movimiento: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3
Estos patrones dependen únicamente del número de piezas. Si el número de piezas es par, los patrones de las impares serán los de las pares, y viceversa.
Uniendo la primera regla con la segunda, sabemos siempre qué pieza hay que mover y a qué columna hay que desplazarla, luego el problema está resuelto.

ALGORITMO EN JAVA DE LAS TORRES DE HANOI

package torreshanoi;//paquete
import javax.swing.JOptionPane;//importar libreria

public class Hanoi {
private String disco;//variable de numero de discos
public Hanoi(){
Solucion();//ir al metodo solucion
}
public static void main (String args[])
{
Hanoi x= new Hanoi();
}
public void Solucion(){
int discos;
disco= JOptionPane.showInputDialog("Cuantos discos:");//preguntar cuantos discos
discos=Integer.parseInt(disco);
if (discos==1){//cuando el disco es igual a 1
JOptionPane.showMessageDialog(null,"Disco uno ponerlo al:"+ "c");
}
else
//todas los pasos que se debe hacer segun el numero de discos
JOptionPane.showMessageDialog(null,"Disco" +discos+ "ponerlo al destino");
JOptionPane.showMessageDialog(null,"Mover todas las fichas menos:" +discos+ "a auxiliar");
JOptionPane.showMessageDialog(null,"Mover todas las fichas restantes encima de la numero:" +discos+ "que esta en destino");
Torre( discos);
}
public void Torre(int discos){
int num;
num=discos-1;
for(int i=1; iint par=2*i;
int impar=(2*i)-1;
if(imparJOptionPane.showMessageDialog(null,"Discos:"+ impar);
JOptionPane.showMessageDialog(null,"Pasarlos a destino, luego al auxliar y luego al origen");
}
if(parJOptionPane.showMessageDialog(null,"Discos:"+ par);
JOptionPane.showMessageDialog(null,"Pasarlos a auxiliar,luego destino y despues oriegen");
}
}
}
}

ESTRUCTURA DE DATOS:

Forma de organizar datos (clase).

DEFINICIONES BASICAS:

DATO: Unidad básica de información(objeto).

TIPO DE DATO ABSTRACTO: Nombramos el objeto con el nombre en el programa y ocultamos sus caracteristicas y propiedades.

Se les conoce como:

TDA/TAD

PROPIEDADES: dato + operacion: - funcion
- procedimiento


NIVELES DE ESTUDIO:

1.NIVEL DE ABSTRACCIÓN: Lógico: - Algoritmo Iterativo
- Algoritmo Recursivo
Para cada uno se requiere una prueba de escritorio.

2.NIVEL DE IMPLEMENTACIÓN:

- Instrucciones, operaciones que se hace en el nivel de abstración.
- Codificar en un lenguaje de programación.

3. NIVEL DE APLICACIÓN:

Usuario= solucion del problema por intermedio de la aplicacion

EJERCICIO:

"BIBLIOTECA"
"coleccion de libros"----->clase

1. ABSTRACCION:
¿que?---->Que es una biblioteca?
Que servicios me ofrece una biblioteca?
Prestamo de un libro
Consulta de un libro
Crear una cuenta en la biblioteca

2. IMPLEMENTACION:
¿Como?---->Como estan ordenados los libros en la biblioteca?
Como hace el bibliotecario para organizar el prestamo de libros?

3. APLICACION:

"Programa de manejo de la biblioteca"

FACTORIAL

Factorial!---->n !
Factorial (n)=n! si n>0
Factorial(n)=n*n-1*n-2*...... si n>0
Factorial(0)=1
Factorial(n)=1--->n=0
Factorial(n)=n*Factorial(n-1) si n>0

EJEMPLO
Factorial(5)=5*Factorial(4)=120
Factorial(4)=4*Factorial(3)=24
Factorial(3)=3*Factorial(2)=64
Factorial(2)=2*Factorial(1)=1
Factorial(1)=1*Factorial(0)=1

CODIGO FACTORIAL EN JAVA:


package factorial;//paquete de la clase

import javax.swing.JOptionPane;
//importar libreria JOptionPane

public class Factorial {
private int fact; // variable en la que se guarda el factorial escrito por el usuario
private int resp; // varible que contiene la respuesta

public Factorial(){ //constructor de la clase
fact=0; //inicializar variable fact
resp=1; //inicializar variable resp
hacerFact(); //ir al metodo factorial
}

public void hacerFact(){ // metodo en el que se hace la operacion
fact= Integer.parseInt(JOptionPane.showInputDialog("Digite el numero al que desea sacar factorial")); //aqui se pide el dato al usuario y se guarda
// la variable fac
if (fact==0) { //si el numero escrito por el usuario es 0 entonces:
resp=1; //respuesta es igual a 1 porque factorial de cero es 1
}
else { //sino
while (fact>=1) { //mientras que sea mayor o igual a uno haga
resp=resp*fact; //multiplicar la respuesta por la variable que reduce el factorial
fact=fact-1; //contador que reduce en uno el factorial
}
}
JOptionPane.showMessageDialog(null, "El factorial es "+resp);
//en esta line se da la respuesta despues de hacer toda la operacion
}
public static void main(String args[]) {
Factorial x= new Factorial(); //metodo main que corre el programa
}
}