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
- The function
generateFibonacci
takes the sizen
as input. - If
n
is less than or equal to 1, we directly print 0 and return. - Otherwise, we create an array
result
to store the Fibonacci series. - We initialize the first two values of
result
as 0 and 1, respectively. - Using a loop, we start from index 2 and iteratively compute the Fibonacci numbers based on the previous two values.
- The calculated series is printed as the final output.
Code Solution
//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;
}
Output
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;
}
Output
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);
}
}
Output
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);
}
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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);
}
}
Output
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();
Output
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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment