Torres de Hanoi

Torres de Hanoi

¿Que son?

El juego matemático de las Torres de Hanoi consiste en un dispositivo que consta de tres varillas verticales A, B y C y un número variable de discos. Los n discos son todos de diferente tamaño y, en la posición de partida del juego, todos los discos están colocados en la varilla A ordenados de mayor a menor tamaño, esto es, el mayor en el lugar más bajo y el menor arriba. En el mundo de la informática se emplea como el ejemplo de recursividad por excelencia.

Del número de discos depende la complejidad de la solución. El juego consiste en lo siguiente: Comenzando en la posición de partida. Trasladar todos los discos a la varilla B, pero colocados también de mayor a menor, en el mismo orden en el que estaban colocados en la varilla A. Para el traslado de discos podemos utilizar la varilla C, pero se debe cumplir siempre la condición de que sólo se puede mover un disco cada vez y que en ningún caso y en ningún paso se podrá colocar un disco mayor sobre otro de menor radio que él.

¿Como se resuelve?

a solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2ⁿ - 1, donde n es la cantidad de discos.

Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.

Solución simple

Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la varilla auxiliar. El disco 2.^o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.^o 1 se mueve también a la varilla destino para que quede sobre el disco n.^o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.^o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.^o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.

Mediante recursividad

Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

Algoritmo Torres de Hanói (Complejidad ${\displaystyle \Theta (2n-1)}$)

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada Salida: La pila destino sí origen ${\displaystyle \scriptstyle ==\{1\}}$ entonces mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino) terminar si no hanoi(${\displaystyle \scriptstyle \{1,\dots ,n-1\}}$,origen,destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar mover disco n a destino                //mover la ficha grande hasta la varilla final hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n) terminar

El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2ⁿ – 1, siendo n el número de discos.

Serie Fibonacci

Serie de Fibonacci

¿Que es?

La sucesión de Fibonacci, en ocasiones también conocida como secuencia de Fibonacci o incorrectamente como serie de Fibonacci, es en sí una sucesión matemática infinita. Consta de una serie de números naturales que se suman de a 2, a partir de 0 y 1. Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números (Todos los números presentes en la sucesión se llaman números de Fibonacci) de la siguiente manera:

• 0,1,1,2,3,5,8,13,21,34...

Fácil, ¿no? (0+1=1 / 1+1=2 / 1+2=3 / 2+3=5 / 3+5=8 / 5+8=13 / 8+13=21 / 13+21=34...) Así sucesivamente, hasta el infinito. Por regla, la sucesión de Fibonacci se escribe así: xn = xn-1 + xn-2.

¿Quien la creo?

Bien, Fibonacci fue un matemático italiano del siglo XIII, el primero en describir esta sucesión matemática. También se lo conocía como Leonardo de Pisa, Leonardo Pisano o Leonardo Bigollo y ya hablaba de la sucesión en el año 1202, cuando publicó su Liber abaci. Fibonacci era hijo de un comerciante y se crió viajando, en un medio en donde las matemáticas eran de gran importancia, despertando su interés en el cálculo de inmediato.

Se dice que sus conocimientos en aritmética y matemáticas crecieron enormemente con los métodos hindúes y árabes que aprendió durante su estancia en el norte de África y luego de años de investigación, Fibonacci dió con interesantes avances. Algunos de sus aportes refieren a la geometría, la aritmética comercial y los números irracionales, además de haber sido vital para desarrollar el concepto del cero.

¿Como es la serie?

La sucesión de Fibonacci es la sucesión de números que, empezando por la unidad, cada uno de sus términos es la suma de los dos anteriores (1,1,2,3,5,8,13,...). Tal como se ha tratado en diversos tópicos expuestos en esta web, la matemática tiene infinidad de coincidencias (si le puede llamar así) con la naturaleza misma. Como ejemplos y de manera reiterativa podemos citar la distribución de las hojas alrededor del tallo, la reproducción de los conejos o la disposición de las semillas en numerosas flores y frutos se produce siguiendo secuencias basadas exclusivamente en estos números.

Leonardo de Pisa (1170 - 1250), también conocido como Fibonacci, matemático italiano a quien debemos el sistema de numeración que emplea notación posicional (de base 10, o decimal) y un dígito de valor nulo (el cero) que usamos en la actualidad también ideó la sucesión de números que lleva su nombre, la llamada “sucesión de Fibonacci”.

Se trata como se memcionan al inicio de una sucesión muy simple, en la que cada término es la suma de los dos anteriores. La sucesión comienza por el número 1, y continua con 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584..., ya que 1 = 0+1; 2=1+1; 3= 1+2; 5=2+3; 8=3+5; 13=5+8=; 21=8+13... y así sucesivamente. Los números de Fibonacci se aproximan a la denominada “razón dorada”, “sección áurea” o “divina proporción”.

Triangulo de pascal

Triangulo de Pascal

¿Que es?

El triángulo de Pascal es un triángulo de números enteros, infinito y simétrico Se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima. Se supone que los lugares fuera del triángulo contienen ceros, de forma que los bordes del triángulo están formados por unos. Aquí sólo se ve una parte; el triángulo continúa por debajo y es infinito.

Se construye:

Se comienza desde la cúspide con el número «1» hacia abajo(infinito), a modo de "árbol"; se clasifica en filas, empezando por la fila cero(el «1» de la cúspide). Este "árbol" tiene nodos, que son cada número que compone el triángulo. Si sumamos dos nodos nos dará de resultado el nodo situado debajo de estos dos, y así sucesivamente.

Las diagonales que empiezan desde el «1» situado en la cabeza del triángulo valen siempre 1.

Una vez sentadas las bases del intrínseco correlato existente entre estos dos campos de las matemáticas, véanse las propiedades de estos.

 Cada uno de los valores de un triángulo de Pascal escritos en forma de tabla corresponden a un coeficiente de la expansión de una potencia de sumas. Concretamente, el número de la fila n y la columna p, corresponde a ${\displaystyle {\tbinom {n}{p}}}$, o también denotado como ${\displaystyle \mathbf {C} _{n}^{p}}$ (${\displaystyle \mathbf {C} }$ por "combinación") y se dice «n sobre p», «combinación de n en p» o «coeficiente binomial n, p». Las casillas vacías corresponden a valores nulos (0). Usando las propiedades de los coeficientes binomiales, se pueden obtener las siguientes propiedades de cualquier triángulo de Pascal con todo rigor:

• Los valores de cada fila del triángulo guardan simetría respecto al eje vertical imaginario del mismo, debido a que ${\displaystyle {\tbinom {n}{n-p}}={\tbinom {n}{p}}.}$

• Los valores correspondientes a la zona fuera del triángulo tienen valor 0, puesto que ${\displaystyle {\tbinom {n}{p}}=0}$cuando ${\displaystyle p>n}$.

• Y claro, la regla de Pascal de construcción del triángulo da la relación fundamental de los coeficientes binomiales ${\displaystyle {\tbinom {n}{p}}+{\tbinom {n}{p+1}}={\tbinom {n+1}{p+1}}.}$

Una consecuencia interesante del triángulo de Pascal es que la suma de todos los valores de una fila cualquiera del triángulo es una potencia de 2. Esto es debido a que, por el teorema del binomio, la expansión de la n-potencia de ${\displaystyle (1+1)^{n}=2^{n}}$ es

que corresponde precisamente con la suma de todos los valores de la n-ésima fila de un triángulo de Pascal.

Sus aplicaciones son:

Coeficientes binomiales:

Los números en el triángulo de Pascal ofrecen un atajo al expandir los binomios elevados a la n potencia. Los números en la línea n del Triángulo de Pascal enlistan los coeficientes de la expansión de (a + b)^n. Por ejemplo, la cuarta línea del triángulo de Pascal es "1 4 6 4 1"; la expansión del binomio (a + b)^4 es 1x^4 + 4x^3_y + 6x^2_y^2 + 4x*y^3 + 1y^4.

Combinaciones:

El triángulo de Pascal también contiene un atajo para encontrar el valor de una combinación nCr, que es el número de subgrupos con r miembros de un grupo con n miembros. Las combinaciones son una operación básica en Combinatoria, la rama de la matemática que involucra contar grupos de elementos discretos. Por ejemplo, el número de manos posibles de cinco cartas de una baraja de 52 es 52C5. El quinto valor de la línea 52º da el valor de esta combinación: 259.860.

Probabilidad:

El triángulo de Pascal es usado para calcular probabilidades con resultados binomiales, como la probabilidad de tener un niño o una niña. En una serie de n resultados binomiales, como tener n niños, el número de resultados en el que uno de los eventos de los binomios ocurra k veces, es igual a la entrada k-ésima entrada en la línea n del triángulo de Pascal. Por ejemplo, una familia que tiene cinco hijos tiene un total de 2^5 o 32 posibles combinaciones niño-niña. La quinta línea del triángulo de Pascal es "1 5 10 10 5 1". Estos valores indican el número de resultados con 0, 1, 2, 3, 4 y 5 niñas, en ese orden.

Series de numeros:

El triángulo de Pascal también es notable por contener varias series de números importantes como patrones en su forma. Las series de números triangulares 1, 3, 6, 10, 15 y así corresponde a las sumas de los enteros consecutivos: 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4 y así. Los números triangulares se encuentran en la tercera columna del triángulo de Pascal. Colorear todos los números impares en el Triángulo con un número infinito de líneas crea el triángulo de Sierpinski, un patrón fractal famoso.

Probabilidad

El triángulo de Pascal es usado para calcular probabilidades con resultados binomiales, como la probabilidad de tener un niño o una niña. En una serie de n resultados binomiales, como tener n niños, el número de resultados en el que uno de los eventos de los binomios ocurra k veces, es igual a la entrada k-ésima entrada en la línea n del triángulo de Pascal. Por ejemplo, una familia que tiene cinco hijos tiene un total de 2^5 o 32 posibles combinaciones niño-niña. La quinta línea del triángulo de Pascal es "1 5 10 10 5 1". Estos valores indican el número de resultados con 0, 1, 2, 3, 4 y 5 niñas, en ese orden.

Series de números

El triángulo de Pascal también es notable por contener varias series de números importantes como patrones en su forma. Las series de números 

Preguntas

¿Que es el triangulo de Pascal?

Es un triángulo de números enteros, infinito y simétrico Se empieza con un 1 en la primera fila, y en las filas siguientes se van colocando números de forma que cada uno de ellos sea la suma de los dos números que tiene encima. Se supone que los lugares fuera del triángulo contienen ceros, de forma que los bordes del triángulo están formados por unos. Aquí sólo se ve una parte; el triángulo continúa por debajo y es infinito.

¿cuanto suman las entradas de la primera fila del triangulo de pascal? 
1.................fila1 
1.1...............fila2 suma=2 
1.2.1............fila3 sumA=4 
1.3.3.1........fila 4 suma=8 
1.4.6.4.1......fila5 suma=16 

Ejercicio de Diagrama de árbol

https://es.scribd.com/document/401409473/Ejercicio-de-Diagrama-de-Arbol