Wednesday, March 9, 2016

Print all the Fibonacci numbers from 0 to n

Code:

Method - 1:

using System;

public class Test
{
    public static void Main()
    {
        int n = 5;

        Console.WriteLine("Input: " + n);

        Console.WriteLine("Output: ");

        new Test().Fibonacci(n);
    }

    public void Fibonacci(int n)
    {
        int prevprev = 0;
        int prev = 1;

    Console.WriteLine(prevprev);

        for(int i=1; i <= n ; i++)
        {
        Console.WriteLine(prev);
        
        prev = prev + prevprev;
            prevprev = prev - prevprev;
        }
    }

}


Run Time: O(N)

Method - 2:

using System;

public class Test
{
    public static void Main()
    {
        int n = 5;

        Console.WriteLine("Input: " + n);
        Console.WriteLine("Output: ");
        new Test().AllFibonacci(n);
    }

public void AllFibonacci(int n)
{
for(int i = 0; i <= n; i++)
{
Console.WriteLine(Fibonacci(i));
}
}
    
    public int Fibonacci(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return 1;
        }
        else
        {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

}

Run Time: O(2^N)

Method - 3:

using System;

public class Test
{
    public static void Main()
    {
        int n = 5;

        Console.WriteLine("Input: " + n);
        Console.WriteLine("Output: ");
        new Test().AllFibonacci(n);
    }

 public void AllFibonacci(int n)
 {
  int[] cache = new int[n+1];
  for(int i = 0; i <= n; i++)
  {
   Console.WriteLine(Fibonacci(i,cache));
  }
 }
    
    public int Fibonacci(int n, int[] cache)
    {
        if (n == 0)
        {
            return 0;
        }
        else if (n == 1)
        {
            return 1;
        }
        else if(cache[n] > 0)
        {
         return cache[n];
        }
        else
        {
         cache[n] = Fibonacci(n - 1, cache) + Fibonacci(n - 2, cache); 
            return cache[n];
        }
    }
}

Run Time: O(n)

Output:

Input: 5
Output: 
0
1
1
2
3
5


No comments:

Post a Comment