algorithm - serie - sucesion de fibonacci ejercicios
¿Por qué los números de Fibonacci son significativos en informática? (8)
Déjame agregar otra estructura de datos a la tuya: árboles de Fibonacci. Son interesantes porque el cálculo de la siguiente posición en el árbol se puede hacer por mera adición de los nodos anteriores:
http://xw2k.nist.gov/dads/html/fibonacciTree.html
Se relaciona bien con la discusión por templatetypedef en AVL-trees (un árbol AVL puede tener en el peor de los casos una estructura de fibonacci). También he visto buffers extendidos en pasos de fibonacci en lugar de potencias de dos en algunos casos.
Los números de Fibonacci se han convertido en una introducción popular a la recursión para estudiantes de informática y existe un fuerte argumento de que persisten en la naturaleza. Por estas razones, muchos de nosotros estamos familiarizados con ellos.
También existen dentro de la Informática en otros lugares; en estructuras de datos y algoritmos sorprendentemente eficientes basados en la secuencia.
Hay dos ejemplos principales que vienen a la mente:
- Los montones de Fibonacci que tienen un tiempo amortizado mejor que los montones binomiales.
- Búsqueda de Fibonacci que comparte el tiempo de ejecución O (log N) con la búsqueda binaria en una matriz ordenada.
¿Hay alguna propiedad especial de estos números que les dé una ventaja sobre otras secuencias numéricas? ¿Es una cualidad espacial? ¿Qué otras aplicaciones posibles podrían tener?
Me parece extraño ya que hay muchas secuencias de números naturales que ocurren en otros problemas recursivos, pero nunca he visto un montón de Catalan .
Las secuencias de Fibonacci se encuentran en todas partes en la naturaleza / vida. Son útiles para modelar el crecimiento de las poblaciones de animales, el crecimiento de células vegetales, la forma del copo de nieve, la forma de la planta, la criptografía y, por supuesto, la informática. He oído que se lo conoce como el patrón de ADN de la naturaleza.
Los montones de Fibonacci ya han sido mencionados; el número de hijos de cada nodo en el montón es a lo sumo log (n). También el subárbol que comienza un nodo con m hijos es al menos (m + 2) el número de fibonacci.
Los protocolos de tipo torrente que utilizan un sistema de nodos y supernodos utilizan un fibonacci para decidir cuándo se necesita un nuevo supernúndo y cuántos subnodos gestionará. Hacen gestión de nodo basada en la espiral de fibonacci (proporción áurea). Vea la foto a continuación sobre cómo se dividen / fusionan los nodos (particionados de un cuadrado grande en los más pequeños y viceversa). Ver foto: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi
Algunas ocurrencias en la naturaleza
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF
http://img.blogster.com/view/anacoana/post-uploads/finger.gif
http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif
Los números de Fibonacci tienen todo tipo de propiedades matemáticas realmente agradables que los hacen excelentes en informática. Aquí hay algunos:
- Crecen exponencialmente rápido. Una estructura de datos interesante en la que surge la serie Fibonacci es el árbol AVL, una forma de árbol binario autoequilibrante. La intuición detrás de este árbol es que cada nodo mantiene un factor de equilibrio, de modo que las alturas del subárbol izquierdo y derecho difieren en como máximo uno. Debido a esto, puede pensar en el número mínimo de nodos necesarios para obtener un árbol AVL de altura h definido por una recurrencia que se ve como N (h + 2) ~ = N (h) + N (h + 1), que se parece mucho a la serie de Fibonacci. Si resuelve los cálculos, puede demostrar que la cantidad de nodos necesarios para obtener un árbol AVL de altura h es F (h + 2) - 1. Debido a que la serie Fibonacci crece exponencialmente rápido, esto significa que la altura de un AVL el árbol es como mucho logarítmico en la cantidad de nodos, lo que le da el tiempo de búsqueda O (lg n) que conocemos y apreciamos sobre los árboles binarios equilibrados. De hecho, si puede vincular el tamaño de alguna estructura con un número de Fibonacci, es probable que obtenga un tiempo de ejecución O (lg n) en alguna operación. Esta es la verdadera razón por la que los montones de Fibonacci se llaman montones de Fibonacci, la prueba de que el número de montones después de un minuto de dequeue implica delimitar la cantidad de nodos que puede tener en una cierta profundidad con un número de Fibonacci.
- Cualquier número puede escribirse como la suma de números únicos de Fibonacci. Esta propiedad de los números de Fibonacci es fundamental para que funcione la búsqueda de Fibonacci; si no puede agregar números únicos de Fibonacci en un número posible, esta búsqueda no funcionaría. Compare esto con muchas otras series, como 3 n o los números catalanes. Esto también es parcialmente la razón por la cual muchos algoritmos como potencias de dos, creo.
- Los números de Fibonacci son computables de manera eficiente. El hecho de que la serie se pueda generar de manera extremadamente eficiente (puede obtener los primeros n términos en O (n) o cualquier término arbitrario en O (lg n)), entonces muchos de los algoritmos que los usan no serían prácticos. Generar números catalanes es bastante complejo desde el punto de vista informático, IIRC. Además de esto, los números de Fibonacci tienen una propiedad agradable donde, dados dos números de Fibonacci consecutivos, digamos F (k) y F (k + 1), podemos calcular fácilmente el número de Fibonacci siguiente o anterior agregando los dos valores (F (k) + F (k + 1) = F (k + 2)) o restándolas (F (k + 1) - F (k) = F (k - 1)). Esta propiedad se explota en varios algoritmos, junto con la propiedad (2), para separar los números en la suma de los números de Fibonacci. Por ejemplo, la búsqueda de Fibonacci usa esto para localizar valores en la memoria, mientras que un algoritmo similar puede usarse para calcular logaritmos de manera rápida y eficiente.
- Son pedagógicamente útiles. Enseñar recursividad es complicado, y la serie de Fibonacci es una excelente manera de presentarlo. Puede hablar de recursión directa, de memorización o de programación dinámica al presentar la serie. Además, la asombrosa forma cerrada de los números de Fibonacci a menudo se enseña como un ejercicio de inducción o análisis de series infinitas, y la ecuación matricial relacionada para los números de Fibonacci se introduce comúnmente en el álgebra lineal como una motivación detrás de los vectores propios y los valores propios. Creo que esta es una de las razones por las que tienen un perfil tan alto en las clases introductorias.
Estoy seguro de que hay más razones que solo esto, pero estoy seguro de que algunas de estas razones son los factores principales. ¡Espero que esto ayude!
No creo que haya una respuesta definitiva, pero una posibilidad es que la operación de dividir un conjunto S en dos particiones S1 y S2, una de las cuales se divide en subparticiones S11 y S12, una de las cuales tiene el mismo tamaño que S2: es un enfoque probable para muchos algoritmos y que a veces se puede describir numéricamente como una secuencia de Fibonacci.
Si tiene un algoritmo que se puede explicar con éxito en una forma simple y concisa con ejemplos comprensibles en CS y naturaleza, ¿qué mejor herramienta de enseñanza podría encontrar alguien?
Solo para agregar una trivia sobre esto, los números de Fibonacci describen el empanado de conejos. Empiezas con (1, 1), dos conejos, y luego su población crece exponencialmente.
Su cálculo como matriz de potencia de [[0,1], [1,1]] se puede considerar como el problema más primitivo de la Investigación operativa (algo así como el dilema del prisionero es el problema más primitivo de la teoría de juegos).
El Divisor común más grande es otra magia; mira this por demasiadas magias. Pero los números de Fibonacci son fáciles de calcular; también tiene un nombre específico. Por ejemplo, los números naturales 1,2,3,4,5 tienen demasiada lógica; todos los números primos están dentro de ellos; La suma de 1..n es computable, cada uno puede producir con otros, ... pero nadie se ocupa de ellos :)
Una cosa importante que olvidé es la Proporción Áurea , que tiene un impacto muy importante en la vida real (por ejemplo, te gustan los monitores anchos :)