Print first n Fibonacci numbers using direct formula

In this article, we will solve the problem of printing the first n Fibonacci numbers using direct formula.

In mathematics, Fibonacci numbers are usually represented by Fn (for the nth Fibonacci number), forming a sequence in which each number is equal to the sum of the previous two numbers. The nth Fibonacci number can be expressed as follows -

$$\mathrm{Fn\:=\:F_{n-1}\: \:F_{n-2}}$$

The series starts with 0 and 1. The first few values ​​in the Fibonacci sequence starting from 0 and 1 are -

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

So, in this problem, we will be given a number N and we need to print the first N Fibonacci numbers using the direct formula.

Example

Enter : 4

Output: 0 1 1 2

Input: 8

Output: 0 1 1 2 3 5 8 13

For this problem, we need to understand the concept of Binet's formula, which gives a direct formula for obtaining the nth Fibonacci number, which will be discussed in detail in the algorithm section.

algorithm

According to the formula $\mathrm{Fn\:=\:F_{n-1}\: \:F_{n-2}}$ we need the (n-1)th item and the (n- 2)th item Add them to get the nth term. Because in this problem we should print the first n Fibonacci numbers using direct formula to get the nth Fibonacci number.

To obtain the nth Fibonacci number in the Fibonacci sequence, you can apply an explicit formula called Binet's formula. It was created by mathematician Jacques Philippe Marie Binet.

formula

If $\mathrm{Fn}$ represents the nth Fibonacci number in the Fibonacci sequence, it can be expressed as

$$\mathrm{F_n\:=\:\frac{1}{\sqrt5}((\frac{1 {\sqrt5}}{2})^n\:-\:(\frac{ 1 -{\sqrt5}}{2})^n)}$$

NOTE - This formula gives the Fibonacci sequence starting from 1 and 1. To get the Fibonacci sequence starting at 0 and 1, use n-1 to get the nth Fibonacci number.

We can derive this formula using the concept of quadratic equations. We will use this formula to print each Fibonacci number up to the nth Fibonacci number to print the first n Fibonacci numbers.

method

• We will use a for loop to print all N Fibonacci numbers from 0 to n iterations since we are considering the Fibonacci sequence starting from 0 and 1.

• Initialize the variable to a Fibonacci number and store the i-th Fibonacci number using the above formula on each iteration until i

• Continue printing Fibonacci numbers on each iteration, which will give us the first N Fibonacci numbers.

Example

The following is the implementation of the above method in C -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void fibonacci(long long int N){ //function to print first N fibonacci numbers
   long long int fibonacci; //to store ith fibonacci number
   
   for(int i=0;i<N;i++) { //using for loop to print all N fibonacci numbers
      //using direct formula to print every fibonacci number until n
      fibonacci = 1/sqrt(5)*(pow((1+sqrt(5))/2,i) - (pow((1-sqrt(5))/2,i)));
      cout<<fibonacci<<" ";
   }
   cout<<endl;
}

//Driver Code
int main(){
   long long int N=10;
   fibonacci(N);
   N=6;
   fibonacci(N);
   return 0;
}

Output

0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5

Time complexity: O(n), Because the for loop runs until i is less than n.

Space complexity: O(1), because it does not use extra space.

in conclusion

In this article, we learned to print the first N Fibonacci numbers using a direct formula instead of using recursion. We also learned Binet's formula, which can directly obtain the nth Fibonacci number in the Fibonacci sequence.

I hope this article helped you to clear up all the concepts about this topic.

The above is the detailed content of Print first n Fibonacci numbers using direct formula. For more information, please follow other related articles on the PHP Chinese website!