Fibonacci Series Using Dynamic Programming in C++

Fibonacci Series Using Dynamic Programming

#include<iostream>
#include<vector>
using namespace std;
int fibo(int n)
{

    vector<int> f(n,0) ;
    //int f[n];
    if(n<=1)
    {
        return n;
    }
    else{
        f[0]=0;
        f[1]=1;
        cout<<f[1];
        for(int i=2;i<=n;i++)
        {
            f[i]=f[i-2]+f[i-1];
        }
        return f[n];
    }
}
int main()
{
    int n;
    cout<<"Enter the rangehhhh:=";
    cin>>n;
    int result=fibo(n);
    cout<<"\n\tThe fibonacci series upto "<<n<<" ="<<result;
    return 0;
}

 

Source code : download source code from here

Output :

Job sequencing with deadlines -Greedy Method Using C

Job Sequencing

#include<stdio.h>

#include<conio.h>

int profit[50],deadline[50],select[50];

void job(int n,int max)

{

int i,j,temp,total=0;

for(i=1;i<n;i++)

{

for(j=0;j<n-i;j++)

{

if(profit[j]<=profit[j+1])

{

temp=profit[j];

profit[j]=profit[j+1];

profit[j+1]=temp;

temp=deadline[j];

deadline[j]=deadline[j+1];

deadline[j+1]=temp;

}

}

}//sorting end

for(i=0;i<n;i++)

{

if(deadline[i]<=max)

{

for(j=deadline[i];j>=1;j--)

{

if(select[j]!=1)

{

select[j]=1;

total+=profit[i];

break;

}

}

}

}

printf("\nTotal profit :=%d",total);

}

void main()

{

int i,n,max=0;

clrscr();

printf("\tEnter no of jobs :=");

scanf("%d",&n);

printf("\nEnter profit and deadline :=");

for(i=0;i<n;i++)

{

printf("\np[%d]:=",i);

scanf("%d",&profit[i]);

printf("d[%d]:=",i);

scanf("%d",&deadline[i]);

select[i]=0;

if(deadline[i]>=max)

max=deadline[i];

}

job(n,max);

getch();

}

Source code: https://github.com/shouvik126/Job-sequencing--Greedy-method

Output:

Knapsack Problem - Greedy Method Using C

Knapsack Problem - Greedy Method Using C

#include<stdio.h>

#include<conio.h>

int profit[50],weight[50],max_weight;

void knapsack(int profit[],int weight[],int n)

{

int i,j;

float max_profit=0.0,temp,p_w[50],select[50];

for(i=0;i<n;i++)//calculating per weight profit

{

p_w[i]=(profit[i]*1.0)/weight[i];

select[i]=0;

}

for(i=1;i<n;i++)//sorting according to per weight profit

{

for(j=0;j<n-i;j++)

{

if(p_w[j]<=p_w[j+1])

{

temp=p_w[j];

p_w[j]=p_w[j+1];

p_w[j+1]=temp;

temp=weight[j];

weight[j]=weight[j+1];

weight[j+1]=temp;

temp=profit[j];

profit[j]=profit[j+1];

profit[j+1]=temp;

}

}

}

for(i=0;i<n;i++)

{

printf("%d,",weight[i]);

}

printf("\n\n");

for(i=0;i<n;i++)

{

if(weight[i]<=max_weight)

{

select[i]=1.0;

max_weight-=weight[i];

}

else

{

select[i]=(max_weight*1.0)/weight[i];

break;

}

}

for(i=0;i<n;i++)

{

max_profit+=(select[i]*profit[i]);

}

printf("\nMaximum profit:=%f",max_profit);

}

void main()

{

int n,i;

clrscr();

printf("\tEnter no of object:=");

scanf("%d",&n);

printf("Enter profit and weight of all the objects:=");

for(i=0;i<n;i++)

{

printf("\nProfit[%d] :",i+1);

scanf("%d",&profit[i]);

printf("\nWeight[%d] :",i+1);

scanf("%d",&weight[i]);

}

printf("\nEnter max weight of knapsack:=");

scanf("%d",&max_weight);

knapsack(profit,weight,n);

getch();

}

Source code: https://github.com/shouvik126/Knapsack-Problem---Greedy-method

Output:

Matrix Multiplication using C

Matrix Multiplication

#include<stdio.h>

#include<conio.h>

int a[20][20],b[20][20],c[20][20];

void main()

{

int i,j,k,n;

clrscr();

printf("\nEnter the order of Matrix(order of 2):=");

scanf("%d",&n);

printf("\nEnter first matrix:=\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("A[%d][%d]:=",i,j);

scanf("%d",&a[i][j]);

}

}

printf("\nEnter second matrix:=\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("B[%d][%d]:=",i,j);

scanf("%d",&b[i][j]);

}

}

clrscr();

printf("\nMatrix A :=\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("%d ",a[i][j]);

}

printf("\n");

}

printf("\nMatrix B :=\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("%d ",b[i][j]);

}

printf("\n");

}

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

c[i][j]=0;

for(k=0;k<n;k++)

{

c[i][j]+=a[i][k]+b[k][j];

}

}

}

printf("\nMultiplication of two matrix A*B=C :=\n");

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("%d ",c[i][j]);

}

printf("\n");

}

getch();

}

Source code: =https://github.com/shouvik126/matrix-multiplication

Output: =

Quick Sort using C

Quick Sort

#include<stdio.h>

#include<conio.h>

int ar[20];

int partition(int low ,int high)

{

int temp,pivot=ar[low],i=low,j=high;

while(i<j)

{

do

{

i++;

}while(ar[i]<=pivot);

do

{

j--;

}while(ar[j]>pivot);

if(i<j)

{

temp=ar[i];

ar[i]=ar[j];

ar[j]=temp;

}

}

temp=ar[low];

ar[low]=ar[j];

ar[j]=temp;

return j;

}

void quick_sort(int low,int high)

{       if(low<high)

{       int i,pivot;

pivot=partition(low,high);

quick_sort(low,pivot);

quick_sort(pivot+1,high);

}

}

void main()

{

int n,i;

clrscr();

printf("Enter how mauny no u want to enter:=");

scanf("%d",&n);

for(i=0;i<n;i++)

{

printf("A[%d]",i+1);

scanf("%d",&ar[i]);

}

ar[n]=9999;//assume as a infinity

printf("\nBefore sorting:=\n");

for(i=0;i<n;i++)

{

printf("%d,",ar[i]);

}

quick_sort(0,n);

printf("\nAfter sorting:=\n");

for(i=0;i<n;i++)

{

printf("%d,",ar[i]);

}

getch();

}

Souce code :=https://github.com/shouvik126/quick-sort

Output: =

Merge Sort using C

Merge Sort

       #include<stdio.h>
#include<conio.h>
int ar[20];
void merge(int low ,int mid,int high)
{
int i=low,j=mid+1,k=0,b[20];
while(i<=mid &&j<=high)
{
if(ar[i]<ar[j])
{
b[k++]=ar[i++];
}
else
{
b[k++]=ar[j++] ;
}
}
for(;i<=mid;i++)
b[k++]=ar[i];
for(;j<=high;j++)
b[k++]=ar[j];
for(i=low,k=0;i<=high;i++,k++)
{
ar[i]=b[k] ;
}
}
void mergesort(int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
void main()
{
int n,i,j;
clrscr();
printf("\nEnter how many no you want to enter:=");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("A[%d]:=",i+1);
scanf("%d",&ar[i]);
}
clrscr();
printf("\nBefore sorting:=\n");
for(j=0;j<n;j++)
{
printf("%d,",ar[j]);
}
mergesort(0,n-1);
printf("\nAfter sorting:=\n");
for(j=0;j<n;j++)
{
printf("%d,",ar[j]);
}
getch();
}

Source Code  :=https://github.com/shouvik126/merge-sort                 

Output :=

                             

Binary Search using C

Binary Search

Binary search is a searching technique in a given sorted(ascending or descending) collection of the elements. We all know that there are two types of searching Linear Search, Binary Search, where Linear Search time complexity depends on the no of the element present in the collections I's Time complexity is O(n), whereas Binary Search depends on the height of the tree that is why Time complexity is O(log n). Binary search can be implemented by divide and conquer approach

Divide and Conquer: =It is an approach to solve the bigger problem. If a problem P(big) is given of size=n, which can not be solved at a time then it can be broken into Pk subproblem and obtain a solution for each of them then after combining  all those solutions we can get solutions of the main problem

Binary Search using Iteration
//binary search using iteration
#include<stdio.h>
#include<conio.h>
int ar[20];
int bsearch(int ,int);//prototype declaration
void main()
{
int flag,n,i,key;
clrscr();
printf("Enter no of element :=");
scanf("%d",&n);
//taking input from user
//input must be in sorted order
printf("\nEnter elements in sorted order\n");
for(i=0;i<n;i++)
{
printf("\nEnter Ar[%d]:=",i);
scanf("%d",&ar[i]);
}
printf("\nEnter the key u want to search:=");
scanf("%d",&key);
flag=bsearch(n,key);
if(flag==0)
{
printf("\nKey not found!!");
}
else
{
printf("\nKey %d found at [%d] position",key,flag+1);
}
getch();
}

//function defination start

int bsearch(int n,int key)
{
int mid,low=0,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(ar[mid]==key)
{
return mid;//if element found at mid position return mid
}
else if(key<ar[mid])
{
high=mid-1;//if element is less then mid then upper is shifted to (mid-1)
}
else
{
low=mid+1;//if element is less then mid then upper is shifted to (mid-1)
}
}
return 0;

}

Source code : https://github.com/shouvik126/binary_search-iteration-

Output :

Binary Search using recursion : 

//Binary search using recursion

#include<stdio.h>

#include<conio.h>

int ar[30];

int bsearch(int ,int ,int);//prototype declaration

void main()

{

int low,high,n,i,key,flag;

clrscr();

printf("\nEnter no of element:=");

scanf("%d",&n);

printf("\nEnter elements in sorted order\n");

for(i=0;i<n;i++)

{

printf("\nEnter Ar[%d] :=",i);

scanf("%d",&ar[i]);

}

printf("\nEnter the key u want to search:=");

scanf("%d",&key);

low=0;

high=n-1;

flag=bsearch(low,high,key);//function called

if(flag==0)

{

printf("\nKey not found!!!");

}

else

{

printf("\nKey %d found at [%d] position@@",key,flag+1);

}

getch();

}

//function defination start

int bsearch(int low,int high,int key)

{

int mid;

if(low==high)

{

if(ar[low]==key)

{

return low;//one element exist with in range

}

else

return 0;

}

else

{

mid=(low+high)/2;

if(key==ar[mid])

return mid; //if element found at middle of the array

else if(key<ar[mid])

return bsearch(low,mid-1,key);//if searching key is less then ar[mid]

else

return bsearch(mid+1,high,key);//if searching key is greater then ar[mid]

}

}

Source Code : https://github.com/shouvik126/binary_search_recursion

Output :