Encontramos el número de Fibonacci de N de tres maneras para un tiempo aceptable: lo básico de la programación dinámica. Números de Fibonacci: Ciclo de Fibonacci y recursión de recursión

Muy a menudo en una variedad de olimpiadas, las tareas parecen ser así, que, como se consideran a primera vista, se pueden resolver con un simple reventador. Pero si calculamos el número. opciones posiblesInmediatamente aseguraré de la ineficacia de este enfoque: por ejemplo, una función recursiva simple a continuación consumirá recursos sustanciales en el 30 de Fibonacci, mientras que en los Juegos Olímpicos, el tiempo de decisión a menudo se limita a 1-5 segundos.

INT FIBO (INT N) (IF (N \u003d\u003d 1 || N \u003d\u003d 2) (devuelva 1;) otra cosa (devuelva FIBO (N - 1) + FIBO (N - 2);))

Pensemos en por qué sucede. Por ejemplo, para calcular FIBO (30), primero calculamos FIBO (29) y FIBO (28). Pero al mismo tiempo, nuestro programa "se olvida" que FIBO (28) ya calculado Cuando busque FIBO (29).

El error principal de este enfoque "en la frente" es que los mismos valores de los argumentos de la función se calculan repetidamente, y esto son operaciones suficientes intensivas en recursos. Deshacerse de los cálculos repetitivos nos ayudará programación dinámica - Esta es una recepción, al usar la cual la tarea se divide en subtareas comunes y repetidas, cada una de las cuales se resuelve solo 1 vez, esto mejora significativamente la eficiencia del programa. Este método se describe en detalle en, también hay ejemplos de resolución de otras tareas.

La opción más fácil de mejorar nuestra función es memorizar qué valores ya hemos calculado. Para hacer esto, debe ingresar una matriz adicional que servirá como "caché" para nuestros cálculos: antes de calcular el nuevo valor, verificaremos si se ha calculado antes. Si se calculan, tomaremos un valor listo para la matriz y, si no se calcula, deberá considerarlo sobre la base de los anteriores y memorizar para el futuro:

En caché int; INT FIBO (INT N) (Si (caché [N] \u003d\u003d 0) (si (n \u003d\u003d 1 || n \u003d\u003d 2) (caché [n] \u003d 1;) de la otra manera (caché [n] \u003d FIBO (N - 1) + FIBO (N - 2);)) DEVOLUCIÓN CACHE [N];)

Dado que en esta tarea para calcular el valor N-Mind, se le garantizará que se le garantice (N-1) -E, no será difícil volver a escribir la fórmula en una forma iterativa: simplemente completaremos nuestra matriz en un Fila hasta que llegue a la celda deseada:

<= n; i++) { cache[i] = cache + cache; } cout << cache;

Ahora podemos notar que cuando calculamos el valor F (N), el valor F (N-3) ya está garantizado nunca no necesitará. Es decir, es suficiente para nosotros almacenar solo dos valores en la memoria: F (N - 1) y F (N-2). Además, tan pronto como calculamos F (N), el almacenamiento F (N-2) pierde cualquier significado. Intentemos escribir estos reflejos en la forma de código:

// Dos valores anteriores: int Cache1 \u003d 1; int cache2 \u003d 1; // nuevo valor int cache3; para (int i \u003d 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 => A través de la iteración perderá la relevancia del cache2, es decir, Debe ser cache1 // en otras palabras, cache1 - f (n-2), cache2 - f (n - 1), cache3 - f (n). // Sea n \u003d n + 1 (el número que calculamos en la siguiente iteración). Luego N-2 \u003d N-3, N-1 \u003d N - 2, N \u003d N-1. // De acuerdo con las nuevas realidades, reescribimos los valores de nuestras variables: cache1 \u003d cache2; cache2 \u003d cache3; ) Cout<< cache3;

El programador experimentado está claro que el código es mayor, en general, sin sentido, ya que el cache3 nunca se usa (se registra inmediatamente en cache2), y puede reescribir toda la iteración usando solo una expresión:

Caché \u003d 1; caché \u003d 1; para (int i \u003d 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Para aquellos que no pueden entender cómo funciona la magia con el residuo de la división, o simplemente quiere ver una fórmula más no obvia, hay otra solución:

Int x \u003d 1; int y \u003d 1; para (int i \u003d 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

Trate de seguir la ejecución de este programa: se asegurará de corregir el algoritmo.

PD En general, hay una fórmula única para calcular cualquier número de FIBONACCI, que no requiere iteraciones o recursiones:

Const Doble SQRT5 \u003d SQRT (5); Const doble phi \u003d (sqrt5 + 1) / 2; INT FIBO (INT N) (DEVOLUCIÓN INT (POW (PHI, N) / SQRT5 + 0.5);)

Pero, como puede adivinar, la captura es que el precio de calcular los grados de los números neuropales es bastante grande, al igual que su error.

Números de Fibonacci - Esta es una serie de números en los que cada número siguiente es igual a la suma de los dos anteriores: 1, 1, 2, 3, 5, 8, 13, .... A veces una fila comienza desde cero: 0, 1, 1, 2, 3, 5, .... En este caso, nos adheriremos a la primera opción.

Fórmula:

F 1 \u003d 1
F 2 \u003d 1
F n \u003d F n-1 + f n-2

Ejemplo de cálculo:

F 3 \u003d F 2 + F 1 \u003d 1 + 1 \u003d 2
F 4 \u003d F 3 + F 2 \u003d 2 + 1 \u003d 3
F 5 \u003d F 4 + F 3 \u003d 3 + 2 \u003d 5
F 6 \u003d F 5 + F 4 \u003d 5 + 3 \u003d 8
...

Cálculo del número N-TH de la fila Fibonacci usando el ciclo MIENTO

Asigne los primeros primeros elementos de la serie a las variables FIB1 y FIB2, es decir, asigne una unidad a una variable.
Solicite el número de usuario del elemento cuyo valor quiere obtener. Asignar el número de variable n.
Realice las siguientes acciones n - 2 veces, ya que ya se tienen en cuenta los dos primeros elementos:
1. Fije FIB1 y FIB2 asignando el resultado de una variable para el almacenamiento temporal de datos, por ejemplo, FIB_SUM.
2. Variable FIB1 Asigne el valor FIB2.
3. FIB variable Asigne el valor FIB_SUM.
Mostrar el FIB2.

Nota. Si el usuario ingresa a 1 o 2, el cuerpo del ciclo nunca se realiza, se muestra el valor FIB2 original.

fIB1 \u003d 1 FIB2 \u003d 1 N \u003d entrada () n \u003d int (n) i \u003d 0 Mientras yo< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

Opción de código compacto:

fIB1 \u003d FIB2 \u003d 1 N \u003d int (entrada ( "Número de elemento de una fila de Fibonacci:")) - 2 Mientras N\u003e 0: FIB1, FIB2 \u003d FIB2, FIB1 + FIB2 N - \u003d 1 Impresión (FIB2)

Salida de los números de Fibonacci con un ciclo para

En este caso, no solo se muestra el valor del elemento de la base de una serie de Fibonacci, sino también todos los números, inclusive. Para hacer esto, la salida del valor FIB2 se coloca en el ciclo.

fIB1 \u003d FIB2 \u003d 1 N \u003d int (entrada ()) si n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

Ejemplo de ejecución:

10 1 1 2 3 5 8 13 21 34 55

Cálculo recursivo del número N-TH de la fila Fibonacci

Si n \u003d 1 o N \u003d 2, vuelva a la unidad de sucursal de llamadas, ya que los elementos primero y segundo de la gama Fibonacci son iguales a uno.
En todos los demás casos, causa la misma función con los argumentos N - 1 y N - 2. El resultado de dos llamadas para plegar y volver a la rama de llamadas del programa.

dEF FIBONACCI (N): si n IN (1, 2): devuelva 1 devolución Fibonacci (N - 1) + Fibonacci (N - 2) Impresión (Fibonacci (10))

Supongamos n \u003d 4. Luego habrá una llamada recursiva Fibonacci (3) y Fibonacci (2). El segundo devolverá una unidad, y la primera conducirá a dos desafíos más de la función: Fibonacci (2) y Fibonacci (1). Ambas llamadas serán devueltas por una, en la cantidad que habrá dos. Por lo tanto, la llamada Fibonacci (3) devuelve el número 2, que se resume con un número 1 desde la llamada FIBONACCI (2). Resultado 3 Devoluciones a la rama principal del programa. El cuarto elemento de la gama Fibonacci es de tres: 1 1 2 3.

Los programadores del número de Fibonacci ya deberían aficionarse. Ejemplos de sus cálculos se utilizan en todas partes. Todo, desde el hecho de que estos números proporcionan el ejemplo más simple de la recursión. Y son un buen ejemplo de programación dinámica. ¿Pero es necesario calcularlos así en el proyecto real? No hacer. Ni la recursión ni la programación dinámica son opciones ideales. Y fórmula no cerrada que utiliza números de punto flotante. Ahora te diré cuán correctamente. Pero primero pasa por todas las soluciones conocidas.

El código está diseñado para Python 3, aunque debe ir en Python 2.

Para empezar, recuerdo la definición:

F n \u003d F n-1 + f n-2

Y f 1 \u003d f 2 \u003d 1.

Fórmula cerrada

Extrañemos los detalles, pero aquellos que quieren familiarizarse con la conclusión de la fórmula. La idea es asumir que hay una cierta X para la cual F N \u003d X N, y luego encuentra x.

Que significa

Reduciendo X N-2

Resolvemos la ecuación cuadrada:

Desde donde la "sección de oro" está creciendo φ \u003d (1 + √5) / 2. Sustituyendo los valores iniciales y habiendo hecho más computación, obtenemos:

Como usamos para calcular F N.

Desde __future__ Import Division Import Math Def FIB (N): sqrt5 \u003d math.sqrt (5) phi \u003d (sqrt5 + 1) / 2 retorno int (phi ** n / sqrt5 + 0.5)

Bien:
Rápido y solo por pequeño n
Pobre:
Operaciones de coma flotantes deseadas. Para gran n, se requerirá una gran precisión.
Maldad:
El uso de números integrados para calcular F N es hermoso desde un punto de vista matemático, pero feo, con una computadora.

Recursión

La decisión más obvia que ya ha visto muchas veces, lo más probable, como un ejemplo de lo que es la recursión. Repito una vez más por completo. En Python, se puede escribir en una línea:

FIB \u003d Lambda N: FIB (N - 1) + FIB (N - 2) Si n\u003e 2 else 1

Bien:
Implementación muy simple Repetición de definición matemática
Pobre:
Tiempo de ejecución exponencial. Para n grande n muy lentamente
Maldad:
Desbordamiento de pila

Memoria

La solución con recursión tiene un gran problema: los cálculos de intersección. Cuando se llama FIB (N), se calculan FIB (N-1) y FIB (N-2). Pero cuando se considera la FIB (N-1), calculará independientemente FIB (N-2), es decir, FIB (N-2) se calculará dos veces. Si continúa los argumentos, se verá que la FIB (N-3) se calculará tres veces, etc. Demasiadas intersecciones.

Por lo tanto, solo necesita memorizar los resultados para no contarlos nuevamente. El tiempo y la memoria de esta solución se gastan linealmente. En la resolución, uso un diccionario, pero podrías usar una simple matriz.

M \u003d (0: 0, 1: 1) DEF FIB (N): Si n IN M: RETURSE M [N] M [N] \u003d FIB (N - 1) + FIB (N - 2) Retorno M [n]

(En Python, también se puede hacer usando un decorador, FuntOols.Lru_Cache.)

Bien:
Simplemente gire la recursión a una solución de memorización. Convierte el tiempo exponencial para ejecutar en lineal, para lo que gasta más memoria.
Pobre:
Pasa mucha memoria
Maldad:
Es posible desbordar la pila, como en la recursión.

Programación dinámica

Después de la decisión con la memorización, queda claro que no necesitamos todos los resultados anteriores, sino solo los dos últimos. Además, en lugar de comenzar con FIB (N) y volver, puede comenzar con FIB (0) y seguir adelante. El siguiente código tiene una ejecución de tiempo lineal, y el uso de la memoria es fijo. En la práctica, la velocidad de la solución será aún mayor, ya que no hay desafíos recursivos de las funciones y la operación asociada. Y el código se ve más fácil.

Esta solución a menudo se trae como ejemplo de programación dinámica.

Def (n): a \u003d 0 b \u003d 1 para __ en rango (n): a, b \u003d b, a + b devuelve un

Bien:
Funciona rápidamente para N, código simple.
Pobre:
Tiempo de ejecución aún lineal
Maldad:
Sí, nada no es nada.

Algebra de matriz

Y, finalmente, lo menos iluminado, pero la solución más correcta, usando el tiempo y la memoria. También se puede ampliar en cualquier secuencia lineal homogénea. Idea en el uso de matrices. Es bastante fácil ver eso

Y la generalización dice que

Dos valores para X, obtenidos por nosotros anteriormente, de los cuales uno representó una sección transversal de oro, son valores propios de la matriz. Por lo tanto, otra forma de generar una fórmula cerrada es el uso de una ecuación de matriz y un álgebra lineal.

Entonces, ¿qué es útil tal redacción? Por el hecho de que la exposición se puede realizar para el tiempo logarítmico. Esto se hace a través de la construcción de la plaza. La conclusión es que

Donde se usa la primera expresión incluso para un, el segundo para impar. Sólo permanece organizar multiplicaciones de matrices, y todo está listo. Se obtiene el siguiente código. Organicé una implementación recursiva de POW, porque es más fácil de entender. La versión iterativa mira aquí.

DEF POW (X, N, I, MULT): "" "Devuelve x al grado n. Se asume que i es una matriz única que varía con MULT, y N es un completo" "" si n \u003d\u003d 0: regresa I ELIF N \u003d\u003d 1: RETORNO X ELSE: Y \u003d POW (X, N // 2, I, MULTO) Y \u003d MULT (Y, Y) SI N% 2: Y \u003d MULT (X, Y) Devuelve Y DeF IDENTITY_MATRIX (N): "" "Devuelve una sola MATRIX N en N" "" R \u003d Lista (rango (n)) Retorno [para J en R] DEF MATRIX_MULTIPLY (A, B): BT \u003d LISTA (ZIP (* B )) RETURSE [para ROW_A en A] DEF FIB (N): F \u003d POW ([,], N, identity_matrix (2), matrix_multiply) devuelve f

Bien:
Memoria fija, tiempo logarítmico
Pobre:
El código es más complicado.
Maldad:
Hay que trabajar con matrices, aunque no son tan malos.

Comparación de la velocidad

Es solo una variante de programación dinámica y matriz. Si los comparan el número de caracteres, entre N, resulta que la solución Matrix es linealmente, y la solución con programación dinámica es exponencialmente. Ejemplo práctico: cálculo de FIB (10 ** 6), el número que tendrá más de doscientos mil caracteres.

N \u003d 10 ** 6
Calcule FIB_MATRIX: FIB (N) tiene solo 208988 dígitos, el cálculo tomó 0.24993 segundos.
Calcule FIB_DYNAMIC: FIB (N) es solo 208988 dígitos, el cálculo tomó 11.83377 segundos.

Comentarios teóricos

No tocando directamente el código dado anteriormente, este comentario sigue siendo cierto interés. Considere el siguiente gráfico:

Calcule el número de rutas N de A a B. Por ejemplo, para N \u003d 1 Tenemos una forma, 1. Para n \u003d 2, nuevamente tenemos una forma, 01. Para n \u003d 3 tenemos dos maneras, 001 y 101 . Es bastante sencillo demostrar que la cantidad de rutas N de A a B es igual a la precisión F N. Después de escribir la matriz de arreglos para el gráfico, obtenemos la misma matriz que se describió anteriormente. Este es un resultado bien conocido de la teoría de los gráficos, que para una matriz determinada de la adyacencia A, la aparición de C N es el número de rutas N en la columna (una de las tareas mencionadas en la película "Umnitsa se cazará" ).

¿Por qué hay tales designaciones en los vagabundos? Resulta que al considerar una secuencia infinita de caracteres en sin fin en ambos lados de la secuencia de rutas en la columna, obtendrá algo llamado "TIPOS DE TIPO FINAL", que es un tipo de sistema de altavoces simbólico. Específicamente, este tipo de subfimen final se conoce como el "cambio de la sección de oro" y se establece como un conjunto de "palabras prohibidas" (11). En otras palabras, obtendremos secuencias binarias infinitas en ambas direcciones y no serán adyacentes a los pares de ellos. La entropía topológica de este sistema dinámico es igual a la sección de oro φ. Me pregunto cómo este número está apareciendo periódicamente en diferentes campos de las matemáticas.