Fibonacci series

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. This sequence is not just a mathematical curiosity; it has found applications in various fields like computer science, finance, and nature itself. In this context, we'll explore how to generate the Fibonacci series efficiently using dynamic programming.

Problem Statement

Given a size n, the Fibonacci series involves generating the first n numbers of the sequence. For instance, if n is 5, the series would be 0, 1, 1, 2, 3.

Example

For n = 12, the Fibonacci series would be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Idea to Solve

The Fibonacci series can be generated using an iterative approach, commonly known as dynamic programming. Instead of recursively recalculating values, we store previously computed values to avoid redundant calculations.

Pseudocode

function generateFibonacci(size):
    if size <= 1:
        print 0
    else:
        result = new array of size
        result[0] = 0
        result[1] = 1
        for i from 2 to size:
            result[i] = result[i-1] + result[i-2]
        print result

Algorithm Explanation

1. The function generateFibonacci takes the size n as input.
2. If n is less than or equal to 1, we directly print 0 and return.
3. Otherwise, we create an array result to store the Fibonacci series.
4. We initialize the first two values of result as 0 and 1, respectively.
5. Using a loop, we start from index 2 and iteratively compute the Fibonacci numbers based on the previous two values.
6. The calculated series is printed as the final output.

Code Solution

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//C Program
//Fibonacci series
//By dynamic programming
#include<stdio.h>

//Display Fibonacci series of given size
void fib(int size)
{
  if(size<=1)
  {
    printf("%d\n",0 );
  }
  else
  {
    //Store fibonacci series
    int result[size];
    
    //Set initial values
    result[0] = 0 ;
    result[1] = 1 ;

    for (int i = 2; i < size; ++i)
    {
      //Use old transaction value
      result[i] = result[i-1] + result[i-2];
    }
    //Show fibonacci series  
    for (int i = 0; i < size; ++i)
    {
      printf("%3d",result[i]);
    }
    printf("\n");
  }
  
}

int main()
{
  //Test Case
  fib(5);
  fib(12);
  return 0;
}

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

// C++ Program
//Fibonacci series
//By dynamic programming
#include<iostream>

using namespace std;
class DynamicExample {
	public:

    //Display Fibonacci series of given size
    void fibonacci(int size) {
      if (size <= 1) {
        cout << "0\n";
      } else {
        int *result = new int[size];
        //Set initial values
        result[0] = 0;
        result[1] = 1;
        for (int i = 2; i < size; ++i) {
          //Use old transaction value
          result[i] = result[i - 1] + result[i - 2];
        }
        //Show fibonacci series  

        for (int i = 0; i < size; ++i) {
          cout << " " << result[i];
        }
        cout << "\n";
      }
    }
};
int main() {
	DynamicExample obj =  DynamicExample();
	//Test Case
	obj.fibonacci(5);
	obj.fibonacci(12);
	return 0;
}

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

// Java Program
//Fibonacci series
//By dynamic programming

public class DynamicExample
{
  //Display Fibonacci series of given size
  public void fibonacci(int size) 
  {
    if (size <= 1) 
    {
      System.out.print("0\n");
    } 
    else 
    {
      //Store fibonacci series
      int[] result = new int[size];
      
      //Set initial values
      result[0] = 0;
      result[1] = 1;
     
      for (int i = 2; i < size; ++i) 
      {
        //Use old transaction value
        result[i] = result[i - 1] + result[i - 2];
      }
      //Show fibonacci series  

      for (int i = 0; i < size; ++i) 
      {
        System.out.print("  "+ result[i]);
      }
      System.out.print("\n");
    }
  }

  public static void main(String[] args) 
  {
    DynamicExample obj = new DynamicExample();
    //Test Case
    obj.fibonacci(5);
    obj.fibonacci(12);

  }
}

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

// C# Program
// Fibonacci series
// By dynamic programming
using System;
public class DynamicExample {
	//Display Fibonacci series of given size
	public void fibonacci(int size) {
		if (size <= 1) {
			Console.Write("0\n");
		} else {
			int[]
			//Store fibonacci series
			result = new int[size];
			//Set initial values
			result[0] = 0;
			result[1] = 1;
			for (int i = 2; i < size; ++i) {
				//Use old transaction value
				result[i] = result[i - 1] + result[i - 2];
			}
			//Show fibonacci series  

			for (int i = 0; i < size; ++i) {
				Console.Write(" " + result[i]);
			}
			Console.Write("\n");
		}
	}
	public static void Main(String[] args) {
		DynamicExample obj = new DynamicExample();
		obj.fibonacci(5);
		obj.fibonacci(12);
	}
}

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

<?php
// Php Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
	//Display Fibonacci series of given size

	public 	function fibonacci($size) {
		if ($size <= 1) {
			echo("0\n");
		} else {
			//Store fibonacci series
			$result = array_fill(0, $size, 0);
			//Set initial values
			$result[0] = 0;
			$result[1] = 1;
			for ($i = 2; $i < $size; ++$i) {
				//Use old transaction value
				$result[$i] = $result[$i - 1] + $result[$i - 2];
			}
			//Show fibonacci series  

			for ($i = 0; $i < $size; ++$i) {
				echo(" ". $result[$i]);
			}
			echo("\n");
		}
	}
}

function main() {
	$obj = new DynamicExample();
	//Test Case
	$obj->fibonacci(5);
	$obj->fibonacci(12);

}
main();

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

// Node Js Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
	//Display Fibonacci series of given size
	fibonacci(size) {
		if (size <= 1) {
			process.stdout.write("0\n");
		} else {
			//Store fibonacci series
			var result = Array(size).fill(0);
			//Set initial values
			result[0] = 0;
			result[1] = 1;
			for (var i = 2; i < size; ++i) {
				//Use old transaction value
				result[i] = result[i - 1] + result[i - 2];
			}

			//Show fibonacci series  

			for (var i = 0; i < size; ++i) {
				process.stdout.write(" " + result[i]);
			}

			process.stdout.write("\n");
		}
	}
}

function main(args) {
	var obj = new DynamicExample();
	//Test Case
	obj.fibonacci(5);
	obj.fibonacci(12);
}

main();

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

#  Python 3 Program
# Fibonacci series
# By dynamic programming

class DynamicExample :
	# Display Fibonacci series of given size
	def fibonacci(self, size) :
		if (size <= 1) :
			print("0\n", end = "")
		else :
			result = [0] * size
			# Set initial values
			result[0] = 0
			result[1] = 1
			i = 2
			while (i < size) :
				# Use old transaction value
				result[i] = result[i - 1] + result[i - 2]
				i += 1
			
			# Show fibonacci series  
			i = 0
			while (i < size) :
				print(" ", result[i], end = "")
				i += 1
			
			print("\n", end = "")
		
	

def main() :
	obj = DynamicExample()
	obj.fibonacci(5)
	obj.fibonacci(12)


if __name__ == "__main__":
	main()

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

# Ruby Program
# Fibonacci series
# By dynamic programming
class DynamicExample 
	# Display Fibonacci series of given size
	def fibonacci(size) 
		if (size <= 1) 
			print("0\n")
		else 
			result = Array.new(size) {0}
			# Set initial values
			result[0] = 0
			result[1] = 1
			i = 2
			while (i < size) 
				# Use old transaction value
				result[i] = result[i - 1] + result[i - 2]
				i += 1
			end
			# Show fibonacci series  
			i = 0
			while (i < size) 
				print(" ", result[i])
				i += 1
			end
			print("\n")
		end
	end
end
def main() 
	obj = DynamicExample.new()
	obj.fibonacci(5)
	obj.fibonacci(12)
end
main()

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

// Scala Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
	//Display Fibonacci series of given size
	def fibonacci(size: Int): Unit = {
		if (size <= 1) {
			print("0\n");
		} else {
			var result: Array[Int] = Array.fill[Int](size)(0);

			//Set initial values
			result(0) = 0;
			result(1) = 1;
			var i: Int = 2;
			while (i < size) {
				//Use old transaction value
				result(i) = result(i - 1) + result(i - 2);
				i += 1;
			}
			//Show fibonacci series  
			i = 0;
			while (i < size) {
				print(" " + result(i));
				i += 1;
			}
			print("\n");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		var obj: DynamicExample = new DynamicExample();
		obj.fibonacci(5);
		obj.fibonacci(12);
	}
}

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

// Swift Program
//Fibonacci series
//By dynamic programming
class DynamicExample {
	//Display Fibonacci series of given size
	func fibonacci(_ size: Int) {
		if (size <= 1) {
			print("0\n", terminator: "");
		} else {
			var result: [Int] = Array(repeating: 0, count: size);
			//Set initial values
			result[0] = 0;
			result[1] = 1;
			var i: Int = 2;
			while (i < size) {
				//Use old transaction value
				result[i] = result[i - 1] + result[i - 2];
				i += 1;
			}
			//Show fibonacci series  
			i = 0;
			while (i < size) {
				print(" ", result[i], terminator: "");
				i += 1;
			}
			print("\n", terminator: "");
		}
	}
}
func main() {
	let obj: DynamicExample = DynamicExample();
	obj.fibonacci(5);
	obj.fibonacci(12);
}
main();

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

Time Complexity

The time complexity of this algorithm is O(n) because we iteratively calculate each Fibonacci number once using the dynamic programming approach.