C - Program to Solve Knapsack Problem

#include<stdio.h>
#include<conio.h>

int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0};

int max(int i,int j)
{
 return ((i>j)?i:j);
}

int knap(int i,int j)
{
 int value;
 if(v[i][j]<0)
 {
  if(j<w[i])
   value=knap(i-1,j);
  else
   value=max(knap(i-1,j),p[i]+knap(i-1,j-w[i]));
  v[i][j]=value;
 }
 return(v[i][j]);
}

void main()
{
 int profit,count=0;
 clrscr();
 printf("\nEnter the number of elements\n");
 scanf("%d",&n);
 printf("Enter the profit and weights of the elements\n");
 for(i=1;i<=n;i++)
 {
  printf("For item no %d\n",i);
  scanf("%d%d",&p[i],&w[i]);
 }
 printf("\nEnter the capacity \n");
 scanf("%d",&cap);
 for(i=0;i<=n;i++)
  for(j=0;j<=cap;j++)
   if((i==0)||(j==0))
    v[i][j]=0;
   else
    v[i][j]=-1;
 profit=knap(n,cap);
 i=n;
 j=cap;
 while(j!=0&&i!=0)
 {
  if(v[i][j]!=v[i-1][j])
  {
   x[i]=1;
   j=j-w[i];
   i--;
  }
  else
   i--;
 }
 printf("Items included are\n");
 printf("Sl.no\tweight\tprofit\n");
 for(i=1;i<=n;i++)
  if(x[i])
   printf("%d\t%d\t%d\n",++count,w[i],p[i]);
 printf("Total profit = %d\n",profit);
 getch();
}

C - Program to Cyclically Permute the Elements of an Array 

 

C - Program to Print Fibonacci Numbers using Recursion

 

C - Program To Find The Largest Of 3 Numbers

#include<stdio.h>

int main() {

 int a, b, c;
 printf("Enter the value for a:\n");
 scanf("%d", &a);
 printf("Enter the value for b:\n");
 scanf("%d", &b);
 printf("Enter the value for c:\n");
 scanf("%d", &c);
 if ((a > b) && (a > c)) {
  printf("\n The big one is a= %d", a);
 } else if (b > c) {
  printf("\n The big one is b= %d", b);
 } else {
  printf("\n The big one is c= %d", c);
 }
 return 0;
}

C - Program to Find Type of  Triangle (equilateral, isosceles and scalene)

C - Program To Find The Roots Of Quadratic Equation

#include<stdio.h>
#include<math.h>
#include<conio.h>

void main()
{
 int a,b,c;
 float disc,r1,r2;
 for(;;)
 {
  printf("\nEnter the non Zero co-efficients a, b,c\n");
  scanf("%d%d%d",&a,&b,&c);
  if((a==0) || (b==0) || (c==0))
  {
   printf("\nPlease enter non zero co-efficients \n");
  }else{
   disc=((b*b)-(4*a*c));
   if(disc>0)
   {
    printf("Roots are Real:\n");
    r1=(-b-(sqrt(disc)))/(2.0*a);
    r2=(-b+(sqrt(disc)))/(2.0*a);
    printf("Roots are:%f and %f  \n", r1,r2);

   }
   else if(disc<0)
   {
    printf("Roots are Imaginary:\n");
    r1=-b/(2.0*a);

    printf("First root: %lf +%fi \n", r1,sqrt(-disc)/(2.0*a));
    printf("Second root:%lf -%lfi\n", r1,sqrt(-disc)/(2.0*a));

   }
   else
   {
    printf("Roots are Equal\n");
    r1= -b/(2.0*a);
    printf("Equal; roots are:%f and %f  \n", r1,r1);
   }
getch();
  }
 }
}

C - Program to Implement Interpolation Search

#include <stdio.h>
#include <stdlib.h>

#define MAX 200

int interpolation_search(int a[], int bottom, int top, int item) {

 int mid;
 while (bottom <= top) {
  mid = bottom + (top - bottom)
    * ((item - a[bottom]) / (a[top] - a[bottom]));
  if (item == a[mid])
   return mid + 1;
  if (item < a[mid])
   top = mid - 1;
  else
   bottom = mid + 1;
 }
 return -1;
}

int main() {
 int arr[MAX];
 int i, num;
 int item, pos;

 printf("\nEnter total elements (num< %d) : ", MAX);
 scanf("%d", &num);

 printf("Enter %d Elements : ", num);
 for (i = 0; i < num; i++)
  scanf("%d", &arr[i]);

 printf("\nELEMENTS ARE\n: ");
 for (i = 0; i < num; i++)
  printf("%d\t", arr[i]);

 printf("\nSearch For : ");
 scanf("%d", &item);
 pos = interpolation_search(&arr[0], 0, num, item);
 if (pos == -1)
  printf("\nElement %d not found\n", item);
 else
  printf("\nElement %d found at position %d\n", item, pos);

 return 0;
}

C - Program to Implement Shell Sort

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void shell_sort(char *chars, int c) 
{
 register int i, j, space, k;
 char x, a[5];

 a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

 for(k=0; k < 5; k++) {
  space = a[k];
  for(i=space; i < c; ++i) {
   x = chars[i];
   for(j=i-space; (x < chars[j]) && (j >= 0); j=j-space)
    chars[j+space] = chars[j];
   chars[j+space] = x;
  }
 }
}

int main() {
 char string[300];
 printf("Enter a string:");
 gets(string);
 shell_sort(string, strlen(string));
 printf("The sorted string is: %s.\n", string);
 return 0;
}

C - Program to Sort Names

#include <stdio.h>
#include <conio.h>
#include <string.h>

void main()
{
 char name[10][8], Tname[10][8], temp[8];
 int i, j, N;

 clrscr();

 printf("Enter the value of N\n");
 scanf("%d", &N);

 printf("Enter %d names\n", N);
 for(i=0; i< N ; i++)
 {
  scanf("%s",name[i]);
  strcpy (Tname[i], name[i]);
 }

 for(i=0; i < N-1 ; i++)
 {
  for(j=i+1; j< N; j++)
  {
   if(strcmpi(name[i],name[j]) > 0)
   {
    strcpy(temp,name[i]);
    strcpy(name[i],name[j]);
    strcpy(name[j],temp);
   }
  }
 }

 printf("\n----------------------------------------\n");
 printf("Input Names\tSorted names\n");
 printf("------------------------------------------\n");
 for(i=0; i< N ; i++)
 {
  printf("%s\t\t%s\n",Tname[i], name[i]);
 }
 printf("------------------------------------------\n");

}  

C - Program to Implement Bucket Sort

#include<stdio.h>

void Bucket_Sort(int array[], int n)
{  
 int i, j;  
 int count[n]; 
 for(i=0; i < n; i++)
 {  
  count[i] = 0;  
 }    
 for(i=0; i < n; i++)
 {   
  (count[array[i]])++;
 }    
 for(i=0,j=0; i < n; i++)
 {  
  for(; count[i]>0;(count[i])--)
  {      
   array[j++] = i;
  } 
 }  
}   

int main()
{
 int array[100];  
 int num;  
 int i; 
 printf("Enter How many Numbers : ");   
 scanf("%d",&num);   
 printf("Enter the %d elements to be sorted:\n",num); 
 for(i = 0; i < num; i++ )
 {  
  scanf("%d",&array[i]); 
 }  
 printf("\nThe array of elements before sorting : \n");
 for (i = 0;i < num;i++)
 {   
  printf("%d ", array[i]);  
 }   
 printf("\nThe array of elements after sorting : \n"); 
 Bucket_Sort(array, num); 
 for (i = 0;i < n;i++)
 {    
  printf("%d ", array[i]); 
 }  
 printf("\n");     
 return 0;
}

C - Program to Implement Topological Sort

#include<stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main()
{
 int i,j = 0,k;
 int topsort[MAX],indeg[MAX];
 create_graph();
 printf(“The adjacency matrix is:\n”);
 display();
 for(i=1;i<+n;i++)
 {
  indeg[i]=indegree(i);
  if(indeg[i]==0)
   insert_queue(i);
 }
 while(front<=rear)
 {
  k=delete_queue();
  topsort[j++]=k;
  for(i=1;i<=n;i++)
  {
   if(adj[k][i]==1)
   {
    adj[k][i]=0;
    indeg[i]=indeg[i]-1;
    if(indeg[i]==0)
     insert_queue(i);
   }
  }
 }
 printf("Nodes after topological sorting are:\n");
 for(i=0;i<=n;i++)
  printf("%d",topsort[i]);
 printf("\n");
}
create_graph()
{
 int i,max_edges,origin,destin;
 printf("\n Enter number of vertices:");
 scamf("%d",&n);
 max_edges = n * (n - 1);
 for(i = 1;i <= max_edges;i++)
 {
  printf("\n Enter edge %d (00 to quit):",i);
  scanf("%d%d",&origin,&destin);
  if((origin == 0) && (destin == 0))
  {
   printf("Invalid edge!!\n");
   i–;
  }
  else
   adj[origin][destin] = 1;
 }return;
}
display()
{
 int i,j;
 for(i = 0;i <= n;i++)
 {
  for(j = 1;jrear)
  {
   printf(“Queue Underflow”);
   return;
  }
  else
  {
   del_item = queue[front];
   front = front + 1;
   return del_item;
  }
 }
 int indegree(int node)
 {
  int i,in_deg = 0;
  for(i = 1;i <= n;i++)
   if(adj[i][node] == 1)
    in_deg++;
  returnin_deg;
 }

C - Program for Radix Sort

#include <stdio.h>

#define MAX 100
#define SHOWPASS

void print(int *a, int n)
{
 int i;
 for (i = 0; i < n; i++)
  printf("%d\t", a[i]);
}

void radix_sort(int *a, int n)
{
 int i, b[MAX], m = 0, exp = 1;
 for (i = 0; i < n; i++) {
  if (a[i] > m)
   m = a[i];
 }

 while (m / exp > 0)
{
  int box[10] = { 0 };
  for (i = 0; i < n; i++)
   box[a[i] / exp % 10]++;
  for (i = 1; i < 10; i++)
   box[i] += box[i - 1];
  for (i = n - 1; i >= 0; i--)
   b[--box[a[i] / exp % 10]] = a[i];
  for (i = 0; i < n; i++)
   a[i] = b[i];
  exp *= 10;

#ifdef SHOWPASS
  printf("\n\nPASS   : ");
  print(a, n);
#endif
 }
}

int main()
{
 int arr[MAX];
 int i, num;

 printf("\nEnter total elements (num < %d) : ", MAX);
 scanf("%d", &num);

 printf("\nEnter %d Elements : ", num);
 for (i = 0; i < num; i++)
  scanf("%d", &arr[i]);

 printf("\nARRAY  : ");
 print(&arr[0], num);

 radix_sort(&arr[0], num);

 printf("\n\nSORTED  : ");
 print(&arr[0], num);

 return 0;
}