The code is intended for Python 3, although it should also work with Python 2.
To begin with, let me remind you of the definition:
F n = F n-1 + F n-2
And F 1 = F 2 =1.
Closed formula
We will skip the details, but those interested 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 it mean
Reduce x n-2
Solving the quadratic equation:
This is where the “golden ratio” ϕ=(1+√5)/2 grows. Substituting the original values and doing some more calculations, we get:
Which is what we use to calculate Fn.
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
The bad:
Floating point operations are required. Large n will require greater precision.
Evil:
Using complex numbers to calculate F n is beautiful from a mathematical point of view, but ugly from a computer point of view.
Recursion
The most obvious solution is one that you've seen many times before, most likely as an example of what recursion is. I will 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 follows the mathematical definition
The bad:
Exponential execution time. For large n it is very slow
Evil:
Stack Overflow
Memorization
The recursion 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 count fib(n-2) again independently - that is, fib(n-2) is counted twice. If we continue the argument, we will see that fib(n-3) will be counted three times, etc. 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 manner. I'm using a dictionary in my 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 using the decorator, functools.lru_cache.)
Good:
Just turn recursion into a memory solution. Converts exponential execution time into linear execution, which consumes more memory.
The bad:
Wastes a lot of memory
Evil:
Possible stack overflow, just 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 from fib(n) and going backwards, you can start from fib(0) and going forward. The following code has linear execution time and fixed memory usage. In practice, the solution speed will be even higher, since there are no recursive function calls and associated 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:
Works fast for small n, simple code
The bad:
Still linear execution time
Evil:
Nothing special.
Matrix algebra
And finally, the least illuminated, but most correct solution, wisely using 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 a generalization of this says that
The two values for x that we obtained earlier, one of which 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 formulation useful? Because exponentiation can be done in logarithmic time. This is done through squaring. The point is that
Where the first expression is used for even A, the second for odd. All that remains is to organize the matrix multiplications, and everything is ready. This results in the following code. I created a recursive implementation of pow because it is easier to understand. See the iterative version here.
Def pow(x, n, I, mult): """ Returns x to the power of n. Assumes I is the identity matrix being multiplied 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
The bad:
The code is more complicated
Evil:
You have to work with matrices, although they are not that 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, it turns out that the matrix solution is linear, and the solution with dynamic programming is exponential. Case Study– calculation of fib(10 ** 6), a number that will have more than two hundred thousand digits.N=10**6
Calculating fib_matrix: fib(n) has only 208988 digits, the calculation took 0.24993 seconds.
Calculating fib_dynamic: fib(n) has only 208988 digits, the calculation took 11.83377 seconds.
Theoretical Notes
While not directly related to the code above, this remark still has 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 equal to Fn. Having written down the adjacency matrix for the graph, we get the same matrix that was described above. It is a well-known result from graph theory that, given an adjacency matrix A, occurrences in A n are 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 markings on the ribs? It turns out that when you consider an infinite sequence of symbols on a round-trip infinite sequence of paths on a graph, you get something called "finite type subshifts", which is a type of symbolic dynamics system. This particular subshift of a finite type is known as the “golden ratio shift,” and is specified 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's interesting how this number appears periodically in different areas of mathematics.
Very often, at various Olympiads, you come across problems like this, which, at first glance, you think can be solved using simple brute force. But if we count the number possible options, then we will immediately be convinced of the ineffectiveness of this approach: for example, the simple recursive function given below will consume significant resources already at the 30th Fibonacci number, whereas in 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 compute fibo(30), we first compute fibo(29) and fibo(28). But at the same time, our program “forgets” that fibo(28) we already calculated when searching for fibo(29).
The main mistake of this head-on approach is that identical values of function arguments are calculated many times - and these are quite resource-intensive operations. The dynamic programming method will help us get rid of repetitive calculations - this is a technique in which the problem is divided into general and repeatable subtasks, each of which is solved only once - 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 what values we have already calculated. To do this, we need to introduce an additional array, which will serve as a “cache” for our calculations: before calculating a new value, we will check whether it has not been calculated before. If we calculated it, then we will take the finished value from the array, and if we did not 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 problem we are guaranteed to need the (N-1)th value to calculate the Nth value, it will not be difficult to rewrite the formula in iterative form - we will simply fill 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, we only need to store 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 down 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 =>After 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 that we calculate at 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; ) cout<< cache3;
An experienced programmer will understand 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 understand how the magic with remainders 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 monitor 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, which 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 powers of non-integer numbers is quite high, as is their error.
Fibonacci numbers 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 scratch: 0, 1, 1, 2, 3, 5, ... . In this case, we will stick to the first option.
Formula:
F 1 = 1
F 2 = 1
F n = F n-1 + F n-2
Calculation example:
F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...
Calculating the nth number of the Fibonacci series using a while loop
- Assign the variables fib1 and fib2 the values of the first two elements of the series, that is, assign the variables ones.
- Request the user for the number of the element whose value he wants to obtain. Assign a number to the variable n.
- Perform the following steps n - 2 times, since the first two elements are already taken into account:
- Add fib1 and fib2 , assigning the result to a temporary storage variable, for example fib_sum .
- Set variable fib1 to fib2 .
- Set variable 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 printed to the screen.
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 ( "Fibonacci series element number: ") ) - 2 while n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 print (fib2)
Printing Fibonacci numbers using 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 it, inclusive. 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
Recursively calculating 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 the two calls and return it to the calling program branch.
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 there will be a recursive call to fibonacci(3) and fibonacci(2). 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. So the call to fibonacci(3) returns the number 2, which adds up to the number 1 from the call to fibonacci(2). Result 3 is returned to the main branch of the program. The fourth element of the Fibonacci series is equal to three: 1 1 2 3.
Loading...
