Archive

Posts Tagged ‘logic’

Divide and Conquer method Illustrated


Divide and Conquer is one of the famous algorithmic techniques. It works with the philosophy that divide the whole problem into smaller managable chunks of subproblems and work out these small subproblems there by combining the intermediate partial solutions.

There are many famous examples which use the Divide and Conqure strategy, for example Binary search, Merge sort, Insertion sort, Quick sort etc.,

Let us take a small example of finding minimum and maximum elements in a given array. If we adapt a normal methodology it takes atleast 2*(n-1) comparisions. We can decrease the number of comparisions using this technique which results in [ Ceil(3*n/2)-2 ] comparisions.

The below is the code for finding MIN and MAX of the given array which was compiled and tested using GNU g++compiler.

//Author: Vasanth Raja Chittampally
#include <iostream>

using namespace std;

void findMin(int [],int, int,int &amp;, int &amp;);

int main()

{

int n,min,max;

cout<<"Enter n:";

cin>>n;

int a[n];

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

{

cout<<"Enter a["<<i<<"]:";

cin>>a[i];

}

findMin(a,0,n-1,min,max);

cout<<"Minimun of the given array is: "<<min<<;endl;

cout<<"Maximum of the gvien arrays is: "<<max<<endl;

return 0;

}

void findMin(int a[], int left, int right, int &amp;min, int &amp;max)

{

if(left==right)

{

min=a[left];

max=a[right];

}

else

{

int mid=(left+right)/2;

findMin(a,left,mid,min,max);

int left_min=min;

int left_max=max;

findMin(a,mid+1,right,min,max);

int right_min=min;

int right_max=max;

if(left_min&lt;right_min)

min=left_min;

else

min=right_min;

if(left_max&gt;right_max)

max=left_max;

else

max=right_max;

}

}

In this example it divides whole array into two equal parts recursively and tries to compare partial solutions to find the minimum and maximum elements.

T(n)=2T(n/2) + 2 —–>(2 comparisions are needed one for minimum and the other of maximum)

.

.

.

.

number of comparisions = [ Ceil(3*n/2)-2 ]

The above number of comparisions can be verified by substituting in T(n)

T(n)=2*[3*n/(2*2) – 2]+2

T(n)=3n/2-2 (hence verfied)

Advertisements

Program to extract source code from comment lines


#include<stdio.h>
#include<conio.h>
void main()
{
FILE *p;
char ch=’a’,ch1;
int count=1;
clrscr();
p=fopen(“cfile.c”,”r”);//this is the demonstration of comment line
if(p==NULL)
{
printf(“File not found”);
exit(1);
}
while(ch!=EOF)
{
ch=fgetc(p);
if(ch==’\n’)
count++;
else if(ch=='”‘) {
while((ch=fgetc(p))!=’\n’);
count++;
}
else if(ch==’/’)
{
if((ch1=fgetc(p))==’/’)
{
printf(“\nComment no %d:”,count);
while((ch=fgetc(p))!=’\n’&&ch!=EOF)
printf(“%c”,ch);
count++;
printf(“\n”);
continue;
}
else if(ch1==’*’)
{
printf(“\nComment %d :”,count);
while(ch!=EOF)
{
if((ch=fgetc(p))==’*’)
{
ch1=fgetc(p);
if(ch1==’/’)
break;
else
{
printf(“%c%c”,ch,ch1);
continue;
}
}
else if(ch==’\n’)
count++;
printf(“%c”,ch);
}
printf(“\n”);
}
}
}
getch();
}

Compiled on: Turbo C, gcc

Description : Extracts the program source code with out the comment lines in the given source file

program to swap two numbers with out using temporary variable with in one line


#include <stdio.h>
#include <conio.h>
int main(void)
{
int a , b;
printf(“Enter two integers: “);
scanf(“%d%d”,&a,&b);
printf(“Before swapping: a=%d,b=%d\n”,a,b);
a=(a+b)-(b=a); //This is just one line
printf(“After swapping: a=%d,b=%d”,a,b);
getch();
return 0;
}
compiled on :gcc logic :simple and tricky
If you have any doubts please add a comment

program to swap two numbers with out using temporary variable


#include < stdio.h >
#include < conio.h >
int main(void)
{
int a,b,i,j;
clrscr();
printf(“Enter two integers: “);
scanf(“%d%d”,&a,&b);
printf(“a=%d,b=%d\n”,a,b);
for(i=0;i<sizeof(int)*8;i++)
{
if((a&(1<<i))^(b&(1<<i)))
{
a=a^(1<<i);
b=b^(1<<i);
}
}
printf(“a=%d,b=%d”,a,b);
getch();
return 0;
}