C# Program - Fibonacci Sequence


Advertisements

Fibonacci terms are generally represented as $$F_n$$. A Fibonacci term is the sum of two previous terms and starts with $$0$$ and $$1$$. Mathematically, it can be represented as:

$$F_n$$ = $$F_{n-1}$$ + $$F_{n-2}$$

With boundary conditions: $$F_0$$ = 0 and $$F_1$$ = 1

The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Example: Using Recursive method

In the below example, a recursive method called fib() is created to find out the nth term of Fibonacci sequence.

using System;

namespace MyApplication { 
  class MyProgram {
    static int fib(int n) {
      if (n == 0)
        {return 0;}
      else if (n == 1)
        {return 1;}
      else
        {return fib(n-1) + fib(n-2);}  
    }  

    static void Main(string[] args) {
      Console.WriteLine("Fibonacci 5th term: " + fib(5));
      Console.WriteLine("Fibonacci 6th term: " + fib(6));
      Console.WriteLine("Fibonacci 7th term: " + fib(7));
    }
  }
}

Output

Fibonacci 5th term: 5
Fibonacci 6th term: 8
Fibonacci 7th term: 13

Example: Using Dynamic Programming

The Fibonacci term can also be estimated using dynamic programming. As compared to the recursive method, it calculates a specific term of the sequence only once.

using System;

namespace MyApplication { 
  class MyProgram {
    static int fib(int n) {
      //creating array which contains Fibonacci terms
      int[] f = new int[n+1];
      f[0] = 0;
      f[1] = 1;
      for(int i = 2; i <= n ; i++)
      {
        f[i] = f[i-1] + f[i-2];
      }
      return f[n];  
    }  

    static void Main(string[] args) {
      Console.WriteLine("Fibonacci 6th term: " + fib(6));
      Console.WriteLine("Fibonacci 7th term: " + fib(7));
      Console.WriteLine("Fibonacci 8th term: " + fib(8));
    }
  }
}

Output

Fibonacci 6th term: 8
Fibonacci 7th term: 13
Fibonacci 8th term: 21

Example: Using Ternary Operator

This can also be achieved using ternary operator.

using System;

namespace MyApplication { 
  class MyProgram {
    static int fib(int n) {
      int y = (n == 0)? 0 : (n == 1) ? 1 : fib(n-1) + fib(n-2);
      return y;  
    }  

    static void Main(string[] args) {
      Console.WriteLine("Fibonacci 8th term: " + fib(8));
      Console.WriteLine("Fibonacci 9th term: " + fib(9));
      Console.WriteLine("Fibonacci 10th term: " + fib(10)); 
    }
  }
}

Output

Fibonacci 8th term: 21
Fibonacci 9th term: 34
Fibonacci 10th term: 55

Example: Space optimized method

In this method, only three variables are used which changes in each iteration and finally nth term of Fibonacci Sequence is calculated.

using System;

namespace MyApplication { 
  class MyProgram {
    static int fib(int n) {
      int a = 0, b = 1, c = 0;
      if (n == 0)
        {return a;}
      for(int i = 2; i <= n; i++) 
      {
        c = a + b;
        a = b;
        b = c;    
      }
      return b;  
    }  

    static void Main(string[] args) {
      Console.WriteLine("Fibonacci 9th term: " + fib(9));
      Console.WriteLine("Fibonacci 10th term: " + fib(10));    
      Console.WriteLine("Fibonacci 11th term: " + fib(11));
    }
  }
}

Output

Fibonacci 9th term: 34
Fibonacci 10th term: 55
Fibonacci 11th term: 89

Example: Using power of matrix

A Fibonacci sequence term can also be calculated as power of matrix. A Fibonacci sequence holds below mentioned property:

$$\begin{pmatrix}1 & 1\\\ 1 & 0\end{pmatrix}^n$$ = $$\begin{pmatrix}F_{n+1} & F_n\\\ F_n & F_{n-1}\end{pmatrix}$$

To calculate $$F_n$$, $$A = \begin{pmatrix}1 & 1\\\ 1 & 0\end{pmatrix}^n$$ is calculated and $$A_{01}$$ will be the $$F_n$$.

using System;

namespace MyApplication { 
  class MyProgram {
    static int fib(int n) {
      int[,] initial = new int[2,2]{{1,1},{1,0}};
      int[,] Final = new int[2,2]{{1,1},{1,0}};
      int a, b, c, d;
      if (n == 0)
        {return 0;}
      else
        {      
          for(int i = 1; i < n ; i++)
          {
            a = Final[0,0]*initial[0,0] + Final[0,1]*initial[1,0];
            b = Final[1,0]*initial[0,0] + Final[1,1]*initial[1,0];
            c = Final[0,0]*initial[0,1] + Final[0,1]*initial[1,1];
            d = Final[1,0]*initial[0,1] + Final[1,1]*initial[1,1];
            Final[0,0] = a;
            Final[1,0] = b;
            Final[0,1] = c;
            Final[1,1] = d;           
          }

        }
      return Final[0,1];  
    }  

    static void Main(string[] args) {
      Console.WriteLine("Fibonacci 10th term: " + fib(10));    
      Console.WriteLine("Fibonacci 11th term: " + fib(11));
      Console.WriteLine("Fibonacci 12th term: " + fib(12));
    }
  }
}

Output

Fibonacci 10th term: 55
Fibonacci 11th term: 89
Fibonacci 12th term: 144




Advertisements