//Fibonacci Series using Dynamic Programming and recursion call
//@author : Swarnava Chakraborty#include<stdio.h>
int arr[20];
int f(int n)
{
if (n==0)
return arr[0];
else if (n==1)
return arr[1];
else{
arr[n]=f(n-1)+f(n-2);
return arr[n];
}
}
int main ()
{
int i, n;
arr[0]=0, arr[1]=1;
printf("Enter the value of n [f(n)] : ");
scanf("%d",&n);
f(n);
for(i=0;i<=n;i++)
printf("%d\t",arr[i]);
return 0;
}
Output:
//Coin Changes Problem using BackTracking (&Greedy)
//@author : Swarnava Chakraborty
#include<stdio.h>
#include<stdlib.h>
void coin_changes(int coin_value[],int n,int amount){
int i,j=0,sol[n],sol_index[n],amount2=amount,ci=0;
again:
for(i=ci;i<n;i++)
if(amount2>=coin_value[i]){
amount2=amount2-coin_value[i];
sol[j]=coin_value[i];
sol_index[j++]=i;
}
if(amount2!=0){
amount2=amount2+sol[--j];
ci=sol_index[j]+1;
if (ci==sol_index[0]+1)
printf("\nnot possible\n");
else
goto again;
}
for(i=0;i<j;i++)
printf("\n%d",sol[i]);
}
int desc(const void *a,const void *b){
return (*(int *)b - *(int *)a);
}
int main(){
int n, amount=106, coin_value[]={100,3,3,50,5};
n = sizeof(coin_value) / sizeof(coin_value[0]);
qsort(coin_value,n,sizeof(int),desc);
coin_changes(coin_value, n, amount);
return 0;
}
Time Complexity of coin_changes() :
Worst Case: [if it apply backtracking method]
= O(n) * O(n-1)
= O(n) * O(n)
= O(n^2)
Best Case:
= O(1)
Average Case:
= O(n)
Worst Case: [if it apply greedy]
= O(mn)
Disclaimer :
If any problem not solve by greedy approach then it apply backtracking method.
//Binary Search using Divide & Conquer Algorithm
#include<stdio.h>int e;
int bin( int a[],int low, int high) {
if (low < high) {
int mid=(low+(high-1))/2;
if (a[mid]==e)
printf("elements found in position : %d\n",mid);
else if(a[mid]>e)
bin( a, low, mid-1);
else if(a[mid]<e)
bin( a, mid+1, high);
}
}
int main() {
int n=7, a[20]={1,5,6,8,9,20,25};
e = 6;//element
bin( a, 0, n-1 );
}
Output:
Time Complexity of bin() is :
Best Case = O(1)
Worst Case = O(log n)
C++ program to convert mixed fraction to improper fraction
Input: 5 3/4
Output: 23/4
Program :
#include <bits/stdc++.h>
using namespace std;
int main(){
int i1, i2, i3, o1;
cin >>i1 >>i2 >>i3;
o1 = (i3*i1)+i2;
if(i3==0 || o1==0 || o1<i3)
cout<<"Invalid input";
else
cout<<o1<<"\n"<<i3;
return 0;
}
