Fibonacci numbers- this is a series of numbers in which each next number is equal to the sum of the two previous ones: 1, 1, 2, 3, 5, 8, 13, .... Sometimes the series starts from zero: 0, 1, 1, 2, 3, 5, .... In this case, we will stick to the first option.
Formula:
F1=1
F2 = 1
F n \u003d F n-1 + F n-2
Calculation example:
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
...
Calculating the nth number of a Fibonacci series with a while loop
- Assign to variables fib1 and fib2 the values of the first two elements of the series, that is, assign units to the variables.
- Ask the user for the number of the element whose value he wants to get. Assign a number to the variable n .
- Do the following n - 2 times, since the first two elements have already been taken into account:
- Add fib1 and fib2 , assigning the result to a temporary storage variable, such as fib_sum .
- Set fib1 to fib2 .
- Set fib2 to fib_sum .
- Display the value of fib2 .
Note. If the user enters 1 or 2, the body of the loop is never executed, and the original value of fib2 is displayed.
fib1=1 fib2=1 n=input() n=int(n) i=0 while i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)
Compact version of the code:
fib1 = fib2 = 1 n = int(input( "Element number of the Fibonacci series: ") ) - 2 while n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 print (fib2)
Outputting Fibonacci numbers with a for loop
In this case, not only the value of the desired element of the Fibonacci series is displayed, but also all numbers up to and including it. To do this, the output of the fib2 value is placed in a loop.
fib1 = fib2 = 1 n = int (input () ) if n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()
Execution example:
10 1 1 2 3 5 8 13 21 34 55
Recursive calculation of the nth number of the Fibonacci series
- If n = 1 or n = 2, return one to the calling branch, since the first and second elements of the Fibonacci series are equal to one.
- In all other cases, call the same function with arguments n - 1 and n - 2. Add the result of two calls and return it to the calling branch of the program.
def fibonacci(n) : if n in (1 , 2 ) : return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )
Let's say n = 4. Then fibonacci(3) and fibonacci(2) will be called recursively. The second will return one, and the first will result in two more function calls: fibonacci(2) and fibonacci(1). Both calls will return one, for a total of two. Thus, the call to fibonacci(3) returns the number 2, which is added to the number 1 from the call to fibonacci(2). The result 3 is returned to the main branch of the program. The fourth element of the Fibonacci series is three: 1 1 2 3.
Programmers of Fibonacci numbers should already be fed up. Examples of their calculation are used everywhere. Everything from what these numbers provide the simplest example recursion. And also they are good example dynamic programming. But is it necessary to calculate them like this in a real project? No need. Neither recursion nor dynamic programming are ideal options. And not a closed formula using floating point numbers. Now I will tell you the right way. But first, let's go through all the known solutions.The code is for Python 3, although it should work for Python 2 as well.
First, let me remind you the definition:
F n \u003d F n-1 + F n-2
And F 1 \u003d F 2 \u003d 1.
closed formula
We will skip the details, but those who wish can familiarize themselves with the derivation of the formula. The idea is to assume that there is some x for which F n = x n , and then find x.What does
We reduce x n-2
We solve the quadratic equation:
From where the "golden section" ϕ=(1+√5)/2 grows. Substituting the original values and doing some more calculations, we get:
Which is what we use to calculate F n .
From __future__ import division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)
Good:
Fast and easy for small n
Bad:
Floating point operations are required. Larger n will require more precision.
Evil:
Using complex numbers to calculate F n is beautiful from a mathematical point of view, but ugly from a computer one.
recursion
The most obvious solution, which you have already seen many times - most likely as an example of what recursion is. I'll repeat it again for completeness. In Python, it can be written in one line:fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1
Good:
A very simple implementation that repeats the mathematical definition
Bad:
Exponential runtime. For large n very slowly
Evil:
Stack Overflow
memorization
The recursive solution has a big problem: overlapping calculations. When fib(n) is called, fib(n-1) and fib(n-2) are counted. But when fib(n-1) is counted, it will independently count fib(n-2) again - that is, fib(n-2) will be counted twice. If we continue the reasoning, it will be seen that fib(n-3) will be counted three times, and so on. Too many intersections.Therefore, you just need to remember the results so as not to count them again. This solution consumes time and memory in a linear fashion. I'm using a dictionary in the solution, but a simple array could also be used.
M = (0: 0, 1: 1) def fib(n): if n in M: return M[n] M[n] = fib(n - 1) + fib(n - 2) return M[n]
(In Python, this can also be done with a decorator, functools.lru_cache.)
Good:
Just turn the recursion into a remember solution. Turns exponential execution time into linear execution time, which consumes more memory.
Bad:
Wastes a lot of memory
Evil:
Possible stack overflow, like recursion
Dynamic programming
After solving with memorization, it becomes clear that we do not need all the previous results, but only the last two. Also, instead of starting at fib(n) and going backwards, you can start at fib(0) and go forward. The following code has linear execution time and fixed memory usage. In practice, the solution speed will be even faster, since there are no recursive function calls and related work. And the code looks simpler.This solution is often cited as an example of dynamic programming.
Def fib(n): a = 0 b = 1 for __ in range(n): a, b = b, a + b return a
Good:
Fast for small n, simple code
Bad:
Still linear runtime
Evil:
Yes, nothing special.
Matrix Algebra
And, finally, the least covered, but the most correct solution that intelligently uses both time and memory. It can also be extended to any homogeneous linear sequence. The idea is to use matrices. It is enough just to see that
And the generalization of this is that
The two values for x we obtained earlier, of which one was the golden ratio, are the eigenvalues of the matrix. Therefore, another way to derive a closed formula is to use a matrix equation and linear algebra.
So why is this phrase useful? The fact that exponentiation can be done in logarithmic time. This is done through squaring. The bottom line is that
Where the first expression is used for even A, the second for odd. It remains only to organize the multiplication of matrices, and everything is ready. It turns out the following code. I organized a recursive implementation of pow because it's easier to understand. See iterative version here.
Def pow(x, n, I, mult): """ Returns x to the power of n. Assumes I is the identity matrix that multiplies with mult and n is a positive integer """ if n == 0: return I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix(n): """Returns an n by n identity matrix""" r = list(range(n)) return [ for j in r] def matrix_multiply(A, B): BT = list(zip(*B) ) return [ for row_a in A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F
Good:
Fixed memory size, logarithmic time
Bad:
The code is more complicated
Evil:
You have to work with matrices, although they are not so bad
Performance Comparison
It is worth comparing only the variant of dynamic programming and the matrix. If we compare them by the number of characters in the number n, then it turns out that matrix solution linearly, while the dynamic programming solution is exponential. A practical example is the calculation of fib(10 ** 6), a number that will have more than two hundred thousand characters.N=10**6
Compute fib_matrix: fib(n) has 208988 digits in total, calculation took 0.24993 seconds.
Calculate fib_dynamic: fib(n) has 208988 digits in total, calculation took 11.83377 seconds.
Theoretical remarks
Not directly related to the above code, this remark is still of some interest. Consider the following graph:
Let's count the number of paths of length n from A to B. For example, for n = 1 we have one path, 1. For n = 2, we again have one path, 01. For n = 3, we have two paths, 001 and 101 It can be shown quite simply that the number of paths of length n from A to B is exactly F n . Having written the adjacency matrix for the graph, we will get the same matrix that was described above. It is a well-known result from graph theory that for a given adjacency matrix A, occurrences in A n is the number of paths of length n in the graph (one of the problems mentioned in the movie Good Will Hunting).
Why are there such designations on the edges? It turns out that when you consider an infinite sequence of symbols on an infinite in both directions sequence of paths on a graph, you get something called "subshifts of finite type", which is a type of system of symbolic dynamics. This particular shift final type known as the “golden ratio shift”, and is given by a set of “forbidden words” (11). In other words, we will get binary sequences that are infinite in both directions and no pairs of them will be adjacent. The topological entropy of this dynamical system is equal to the golden ratio ϕ. It is interesting how this number appears periodically in different areas of mathematics.
Very often at various Olympiads there are problems like this, which, at first glance, it seems, can be solved with a simple enumeration. But if we count the number options, then we will immediately see the inefficiency of this approach: for example, a simple recursive function below will consume significant resources already at the 30th Fibonacci number, while at Olympiads the solution time is often limited to 1-5 seconds.
int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )
Let's think about why this happens. For example, to calculate fibo(30) we first calculate fibo(29) and fibo(28). But at the same time, our program "forgets" that fibo(28) we already calculated when looking for fibo(29).
The main mistake of this head-on approach is that the same values of the function arguments are calculated many times - and these are rather resource-intensive operations. The method of dynamic programming will help us get rid of repetitive calculations - this is a technique when using which the task is divided into general and repetitive subtasks, each of which is solved only 1 time - this significantly increases the efficiency of the program. This method is described in detail in, there are also examples of solving other problems.
The easiest way to improve our function is to remember which values we have already calculated. To do this, we need to introduce an additional array, which will serve as a kind of "cache" for our calculations: before calculating a new value, we will check if it has been calculated before. If we calculated, then we will take the ready value from the array, and if we didn’t calculate it, we will have to calculate it based on the previous ones and remember it for the future:
Int cache; int fibo(int n) ( if (cache[n] == 0) ( if (n == 1 || n == 2) ( cache[n] = 1; ) else ( cache[n] = fibo(n - 1) + fibo(n - 2); ) ) return cache[n]; )
Since in this task we are guaranteed to need (N-1)th value to calculate the Nth value, it will not be difficult to rewrite the formula in an iterative form - we will simply fill in our array in a row until we reach the desired cell:
<= n; i++) { cache[i] = cache + cache; } cout << cache;
Now we can notice that when we calculate the value of F(N) , then the value of F(N-3) is already guaranteed to us never will not need. That is, it is enough for us to store only two values in memory - F(N-1) and F(N-2) . Moreover, as soon as we have calculated F(N) , storing F(N-2) loses all meaning. Let's try to write these thoughts in the form of code:
//Two previous values: int cache1 = 1; int cache2 = 1; //New value int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>through iteration, cache2 will lose its relevance, i.e. it should become cache1 //In other words, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //Let N=n+1 (the number we calculate in the next iteration). Then n-2=N-3, n-1=N-2, n=N-1. //In accordance with the new realities, we rewrite the values of our variables: cache1 = cache2; cache2 = cache3; ) cut<< cache3;
An experienced programmer understands that the code above is, in general, nonsense, since cache3 is never used (it is immediately written to cache2), and the entire iteration can be rewritten using just one expression:
cache=1; cache=1; for (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;
For those who can't figure out how the modulo magic works, or just want to see a more non-obvious formula, there is another solution:
int x = 1; int y = 1; for (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;
Try to follow the execution of this program: you will be convinced of the correctness of the algorithm.
P.S. In general, there is a single formula for calculating any Fibonacci number that does not require any iteration or recursion:
Const double SQRT5 = sqrt(5); const double PHI = (SQRT5 + 1) / 2; int fibo(int n)( return int(pow(PHI, n) / SQRT5 + 0.5); )
But, as you can guess, the catch is that the cost of calculating the powers of non-integer numbers is quite large, as is their error.