Array of Fibonacci
A series of numbers that was named after the Italian mathematician Leonardo of Pisces, better known as the Fibonacci. These are numbers that, if we know the first two numbers
f0=0 i
f1=1,
are obtained by the formula:
fn=fn-1 + fn-2, 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:
f0=0 i
f1=1,
are obtained by the formula:
fn=fn-1 + fn-2, 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 calculation
F(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.
F(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 shows the function calls for determining the 4th element of the Fibonacci sequence. It can be concluded that there are too many recursive function calls for larger positions, so execution is slow.
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;
}Initially, the predecessors a and b are initialized to 0 and 1. When a new Fibonacci number is defined as the predecessor a and b, then the predecessors are prepared for a new iteration: the second in the next is equal to the calculated Fibonacci number in the current cycle
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.
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.
|
Next
A prime numbers and factoring >| |