FIBONACCI SERIES USING Dynamic programming using C/C++/Java/JavaScript
Hi everyone,
Hi family
1.
What
is Dynamic programming?
Dynamic
programming is an algorithmic technique in Data structure and algorithm(DSA)
for solving an optimization problem by breaking it down into simpler subproblems
and utilizing the fact that the optimal solution to overall problem depends
upon optimal solution to its subproblems. It is mainly optimization over plan
recursion in DSA.
Recursion:
When function calls itself it is called recursion;
Dynamic
programming vs Recursion
·
In dynamic programming we genreally use
for loop where in recursion function calls itself.
FIBONACCI SERIES
Example: 0,1,1,2,3,5,8,13,21,34,55
,….
Algorithm:
Fibonacci series at any index number is sum of
previous two index just like at position 3 the number is 1 which is sum of
position 2 and position 1 which is 0+1 =1
SO alogorithm is
Number At index = number at index-1+number at index-2
In terms of function:
series(index)
= series(index-1)+series(index-2)
C program to solve
FIBONACCI SERIES using recursion:
#include<stdio.h>
int fibo(int num)
{
if(num<2)
return num;
else
return
(fibo(num-1)+fibo(num-2));
}
void main()
{
int num;
printf("Enter Number to find series ");
scanf("%d",&num);
printf("Fibonacci series is : \n");
for(int
i=1;i<=num;i++)
{
printf("%d\t",fibo(i));
}
//made by riser
great lord shri krishna
}
Output:
How it is working:
First the function calls fibo(1) as per if condition it return 1
Now for fibo(2) as per else fibo(1)+fibo(0) = 1+0 = 1
Now for fibo(3) as per else fibo(2)+fibo(1) = 1+1 = 2
Now for fibo(4) as per else fibo(3)+fibo(2) = 2+1 = 3
Now for fibo(5) as per else fibo(4)+fibo(3) = 3+2 = 5
Using Dynamic programming:
Alogorithm is
Number At index = number at index-1+number at index-2
In terms of Array:
array[index]=array[index-1]+array[index-2];
Code:
#include<stdio.h>
void main()
{
int num;
printf("Enter Number to
find series ");
scanf("%d",&num);
int arr[num];
arr[0] = 0;
arr[1] = 1;
printf("Fibonacci series
is : \n");
printf("%d\t
%d\t",arr[0],arr[1]);
for(int i=2;i<=num;i++)
{
arr[i] = arr[i-1]+arr[i-2];
printf("%d\t",arr[i]);
}
//made by riser great lord
shri krishna
}
How it is working:
First the array at index 0 arr[0]= 0 and at index 1 arr[1] = 1;
Now for arr[2] as per else arr[1]+arr[0] = 1+0 = 1
Now for arr[3] as per else arr[2]+arr[1] = 1+1 = 2
Now for arr[4] as per else arr[3]+arr[2] = 2+1 = 3
Now for arr[5] as per else arr[4]+arr[3] = 3+2 = 5
C++ program to solve
FIBONACCI SERIES using recursion:
#include<iostream>
using namespace std;
int fibo(int num)
{
if(num<2)
{
return num;
}
else
{
return
fibo(num-1)+fibo(num-2);
}
}
int main()
{
int num;
cout<<"Enter Number
to find series ";
cin >>num;
cout <<"Fibonacci
series is : \n";
for(int i=0;i<num;i++)
{
cout
<<fibo(i)<<"\t";
}
//made by riser great lord shri krishna
return 0;
}
OUTPUT
Using Dynamic Programming in C++:
#include<iostream>
using namespace std;
int main()
{
int num;
cout<<”Enter Number to
find series “;
cin >>num;
int arr[num];
arr[0] = 0;
arr[1] = 1;
cout <<”Fibonacci series
is : \n”;
cout<<arr[0]<<”\t”<<arr[1]<<”\t”;
for(int i=2;i<=num;i++)
{
arr[i] =
arr[i-1]+arr[i-2];
cout
<<arr[i]<<”\t”;
}
//made by riser great lord shri krishna
return 0;
}
OUTPUT:
Java program to solve
FIBONACCI SERIES using recursion:
import java.util.*;
public class Fibonacci {
static int fibonacci(int num)
{
if (num < 2)
return num;
else
return fibonacci(num - 1) + fibonacci(num - 2);
}
public static void main(String[] args) {
int num;
Long time1,time2;
System.out.print("Enter Number \n");
Scanner kb = new Scanner(System.in);
num = kb.nextInt();
time1 = System.currentTimeMillis();
System.out.print("Fibonacci Series is :\n"+"Time is "+time1+"\n");
for(int i=0;i<=num;i++)
{
System.out.print(fibonacci(i) + "\t");
}
time2 = System.currentTimeMillis();
System.out.println("\nTime is " + time2 + "\n");
// made by riser great lord shri krishna
System.out.println("Total Time taken to calculate is " + (time2 - time1) + " Sec");
kb.close();
}
}
OUTPUT:
Using dynamic
programming in java:
import java.util.*;
public class Fibonacci {
public static void main(String[] args) {
int num;
Long time1, time2;
System.out.print("Enter Number \n");
Scanner kb = new Scanner(System.in);
num = kb.nextInt();
int[] arr = new int[num+1];
arr[0] = 0;
arr[1] = 1;
time1 = System.currentTimeMillis();
System.out.print(arr[0] + "\t" + arr[1] + "\t");
System.out.print("Fibonacci Series is :\n" + "Time is " + time1 + "\n");
for(int i=2;i<=num;i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
System.out.print(arr[i] + "\t");
}
time2 = System.currentTimeMillis();
System.out.println("\nTime is " + time2 + "\n");
// made by riser great lord shri krishna
System.out.println("Total Time taken to calculate is " + (time2 - time1) + " Sec");
kb.close();
}
}
OUTPUT:
Javascript program to
solve FIBONACCI SERIES using recursion And Dynamic programming:
Code:
function fun(params) {
if(params<2)
return params;
else
return fun(params-1)+fun(params-2);
}
function fibo(params) {
let a = function () {
this.values = [];
this.get = (po)=>{return parseInt(this.values[po])};
this.set = (po,index)=>
{this.values[index] = parseInt(po);}
}
let b = new a();
b.set(0,0);
b.set(1,1);
let par = 4;
for(let i=2;i<=params;i++)
{
b.set(b.get(i-1)+b.get(i-2),i);
}
for(let j=0;j<=params;j++)
{
console.log("Val is "+b.get(j));
series.style = "display:block";
let h2 = document.createElement("h2");
h2.innerText = b.get(j);
series.appendChild(h2);
}
console.log("In re "+b.get(params));
return parseInt(b.get(params));
}
let num = document.getElementById('num');
const btn = document.getElementById('btn');
const series = document.getElementById('series');
const h1 = document.getElementById('start');
btn.addEventListener('click',()=>{
if(num.value==null || isNaN(num.value))
{
alert("Please enter number");
}
else
{
console.log(fibo(num.value));
}
})
OUTPUT:
Comments
Post a Comment