Array of Fibonacci Numbers
A sequence of numbers named after the Italian mathematician Leonardo of Pisa, better known as Fibonacci. These numbers form a sequence where, starting from the first two valuesf₀ = 0 and f₁ = 1,
each subsequent number is obtained using the formula:
fₙ = fₙ₋₁ + fₙ₋₂, for n ≥ 2.
Each new member of the string is obtained as a sum of the previous 2.
Array of Fibonacci:
0,1,1,2,3,5,8,13,21,34,55,89,144,....
An example illustrating this sequence of numbers can be seen in Figure 1:
| These numbers have a great application in nature. The number of petals on the flower, the number of spirals on the sunflower, the hive, the hive, the leaves on the branch, the shell of the snail Nautilus is a typical Fibonacci series. Behind the bees can be seen the Fibonacci series, because there are always few bees in the hive than bees. And when I divide the number of males with the number of males, I would get a number that represents the relationship between the two adjacent members of the Fibonacci series, which is also the number of fi. |
Figure 1: Array of Fibonnaci and nature
|
Determination of the nth Fibonacci number-recursion
One of the possible solutions is through recursion. We make a function for determining the number from the Fibonacci array at a position that is sent as a function parameter. Because it's for calculationF(N)= F(N-1) + F(N-2)
it is necessary to re-call the function, but now with the sent positions of N-1 or N-2, this means that the function must call itself repeatedly recursively. This method is not particularly effective for large data due to too many calls made to the function.
Figure 2: Square squares whose lengthwise pages are successive Fibonacci numbers
|
Figure 3: Fibonacci series - Spiral
|
using namespace std;
int fib(int n)
{
if(n<=1)return n;
int f1=fib(n-1);
int f2=fib(n-2);
return f1+f2;
}
int main()
{
int N,x;
cin >> N;
x=fib(N);
cout << x << endl;
return 0;
}
Figure 4: Determination of this element of the Fibonacci sequence by recursion - function calls
Determination of the nth Fibonacci number - dynamic programming
In this case, in order to shorten the execution time, we remember the set of values that were previously calculated. There is no recursion here, but the function calls only once, and then, using the loop, calculates each current element by adding its two predecessors stored in the series f;using namespace std;
int fib(int n)
{
int f[n+2];f[0]=0;
f[1]=1;
for(int i=2; i<=n; i++){
f[i]=f[i-1]+f[i-2];}
return f[n];
}
int main(){
int N,x;
cin >> N;
x=fib(N);
cout << x << endl;
return 0;
}Determination of the nth Fibonacci number - dynamic programming-optimized method
The preceding code can be further accelerated if, instead of remembering the whole sequence, we only remember the last two elements:using namespace std;
int fib(int n)
{
long long f[n+2];long long a,b,f;
a=0;
b=1;
for(long long i=2; i<=n; i++)
{
f=a+b;a=b;
b=f;
}
return f;}
int main(){
long long N,x;
cin >> N;
x=fib(N);
cout << x << endl;
return 0;
}b=f
while the first predecessor of the new cycle, in fact, the one who in the current cycle was the second predecessor:
a=b.
| Previous |< Mathematical algorithms |
Next A prime numbers and factoring>| |