Saturday 16 March 2013

LEXICOGRAPHIC SORTING IN C++

Lexicographic sorting in C++

Sorting a list lexicographically, means sorting the contents of list so that the resultant list have its contents in dictionary order. Although, such a lexicographic sorting can be performed using a number of algorithms, I will be discussing here, the most common and the simplest technique called Bubble sort. 
Bubble sort is a very simple sorting technique and I assume that the readers have it's prior knowledge. So without taking the pain of explaining the bubble sort, I directly jump over to the explanation of the function used for comparing two stings in C/C++.

strcmp() and strcmpi()

I have used the function called strcmpi(), and for accessing this function you should include the header file string.h. The general declaration for this function is as follows:
int strcmpi(const char*s1,const char*s2);
Here you should note that this function performs comparison of s1 and s2 without case sensitivity. On the other hand, if we talk about the strcmp() function, it performs the comparison of s1 and s2 without ignoring the case sensitivity.
This function starts comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ or until a terminating null-character is reached. 
Both of these functions have a return type integer, means both of these functions returns an integral value, depending upon the relationship between s1 and s2.
A zero value indicates that both strings are equal.
A value greater than zero indicates that the first character that does not match has a greater value in s1 than in s2; and a value less than zero indicates the reverse condition.
The good thing about my code is that it is totally user defined and initially asks the user to input the total number of words that are to be sorted. For this I have also used the concept of allocating the memory dynamically.
Here is my cpp source code:

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

int main()
{
    clrscr();
    char **arr;
    int n;
    cout<<"ENTER THE NUMBER OF WORDS \n";
    cin>>n;

    //dynamic memory allocation
    arr=new char*[n];
    for(int i=0;i<n;i++)
        arr[i]=new char[20];

    //prompting user to input words
     cout<<"ENTER THE WORDS\ n";
    for(i=0;i<n;i++)
        cin>>arr[i];

    //applying the bubble sort
    for(i=1;i<n;i++)
    {
        for(int j=0;j<n-i;j++)
        {
            if(strcmpi(arr[j],arr[j+1])>0)
            {
                char*tmp;
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }

    //printing lexicographically sorted list
    cout<<"\n LEXICOGRAPHICALLY SORTED WORDS ARE : \n"<<endl;
    for(i=0;i<n;i++)
        cout<<arr[i]<<endl;


    getch();
    return 1;
}


Output:-



 










Sunday 10 March 2013

HEAP SORT

 
In this post, I will be explaining Heap Sort.
Sorting, as we all know, is a technique of arranging the elements of a list in a certain order. Sorting can be done either on numerical data or on alphabetical data (lexicographic sorting).
Here I'm concerned with the heap sort applied on the numerical data.

Some prior knowledge that you may require:-

Tree representation of array:-

One important thing to note here is that we have started the indexing of the array from '1' rather than from '0'. This may be a weird thing for some of you but in C the arrays may be indexed as per the wish of programmer. We are totally free to choose the starting index number for any array.
 
A heap is a specialized tree-based data structure that satisfies the heap property, i.e. any parent node in the tree is always greater than each of it's child node.

ALGORITHM:
Heap sort basically includes two steps:-
1) First of all a heap is constructed using the data.
2) In the second step, a sorted array is created by repeatedly swapping the largest element (the first element of array or the root node of the tree) with the last element of the array. The heap is reconstructed after each swap taking appropriate upper limits. Once all objects have been swapped within the heap, we have a sorted array.

For executing the first step of our algorithm, we start building the heap from the last parent node of our tree.
The second step is more explicitly explained as follows:-
Once a heap is constructed, it is sure that the maximum of all the data elements will be at the root node of the tree. Now, we interchange the first and the last element of the array and then the heap is reconstructed by excluding the last element of array. Repeating this process for each node, we get a sorted array.
Some of you may have this question in your mind-
Why the second step is needed, after constructing the heap, is the array not sorted?
The answer to this question is very simple one. After the heap is constructed it is sure that each parent node will be greater than both of it's child node, in fact this is the definition of a heap, but here we are not sure that both the child nodes are in sorted order, i.e. there could exist a pair of sibling that is not in sorted order. 
The following example explains the sorting of 15,19,10,7,17 and 16: 

Source Code in C:-
/******************************************************************************/
#include<stdio.h>
#include<conio.h>

void heapsort(int *,int);
void buildheap(int*,int,int,int);

int main()
{
    int i,n,*arr;

    clrscr();

    printf("enter the maximum number of elements");
    scanf("%d",&n);

    printf("enter the data of array:\n");
    for(i=1;i<=n;i++)
        scanf("%d",&arr[i]);

    heapsort(arr,n);

    printf("\nthe sorted array is as follows:\n");
    for(i=1;i<=n;i++)
        printf("%d\t",arr[i]);


    getch();
    return 1;
}

void heapsort(int*arr,int n)
{
    int tmp,i;
    for(i=n/2;i>0;i--)
        buildheap(arr,arr[i],i,n);

    for(i=n;;i--)
    {
        tmp=arr[i];
        arr[i]=arr[1];
        arr[1]=tmp;
        if(i<=2)
            break;
        buildheap(arr,tmp,1,i-1);
    }
}

//function for building the heap
void buildheap(int*arr,int val,int pos, int limit)
{
    int child;
    child=pos*2;
    if((arr[child]<arr[child+1])&&(child+1)<=limit)
        child++;
    while(child<=limit)
    {
        if(val>arr[child])
            break;
        arr[pos]=arr[child];
        pos=child;
        child=pos*2;
        if((arr[child]<arr[child+1])&&(child+1)<=limit)
            child++;
    }
    arr[pos]=val;
}

/*****************************************************************************/

Friday 8 March 2013

PROJECT EULER - SOLUTION TO PROBLEM NO. 45

Here I have for all of you the solution to problem number 45, which I solved recently.
As some of my friends asked me to include comments in my code for a better understanding, I have done the same in this following program.

I am sorry for the audience that don't have the knowledge of working on the java platform as I have the following source code in java. Initially I was all prepared for working in tcpp, but tcpp being an 16-bit compiler can't satisfy my range demands, and that's why I jumped onto java platform which provides me a 32-bit environment.
Actually this is not a big issue, as I have not used any of the exclusive key features of java, and all the concepts used can be easily understood by a c or cpp programmer.

For readers' convenience I'm mentioning the 45th problem in the following lines:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulas:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.

/*************************************************************************/
class pr45
{
    public static void main(String args[])
    {
        long t,p,h;
        long max=100000;
        for(long i=1;i<max;i++)
        {
            t=i*(i+1)/2;//triangle number
            for(long j=1;j<max;j++)
            {
                p=j*(3*j-1)/2;//pentagonal number
                if(t==p)
                    for(long k=1;k<max;k++)
                    {   
                        h=k*(2*k-1);//hexagonal number
                        if(t==h)
                            System.out.println(t);   
                    }
            }
        }
    }
}                    

/**********************************************************************************/

Here is the output of this program....


I don't think that you will have any problem in understanding the logic of the code. Its very easy and obvious. Then also if any of the reader have any suggestion or queries then please feel free to comment...

Tuesday 5 March 2013

DETERMINATION OF THE DAY OF THE WEEK THROUGH A SIMPLE C PROGRAM


 

Have you ever wondered what if you were given any future or past date and you were asked to calculate the day of week...how would you proceed to solve this crazy problem.
Here is a solution for this problem. I have made a program in C that enables you to enter a date, and calculates the day of the week.
Here are a few screen-shots, have a look at them.


 Now to confirm that my programs runs well and calculates the day of the week perfectly, here is a link that i would recommend you to visit.
Some of the screenshots form this website are adder here to confirm that my program runs perfectly well.
 

You can even run my C program for a future date as shown below.
Although it seems crazy stuff...no doubt, it clearly depicts the power of programming....
BEWARE:
If you go for a google search for this topic you will get a large number of such calculators that ensures you for a perfect answer, but this is not the scenario all the time.
Some of the websites that gives a wrong prediction are:
and surely you can find many more....

Just put these anomalies aside and have a look at my program...
Note that my code runs perfectly well in turbo cpp...just after small amendments you can have a code for any other compiler. 


/*****************************************************************************/

//program to find day of week for a given date....

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

void main()
{
    long int d,m,y,d1,m1,y1,d2,m2,y2,tot,lavish,i;
    clrscr();
    printf("Program to find the day of week for a given date\n\n");
    d1=1;
    m1=1;
    y1=0;
    printf("Enter the date in dd mm yyyy format: \n");
    scanf("%ld%ld%ld",&d2,&m2,&y2);

    y=y2-y1;
    m=m2-m1;
    d=d2-d1;

    tot=y*365+m*30+d;

    if(m2>2)
    {
        for(i=y1;i<=y2;i++)
        {
            if(i%4==0)
                tot++;

            if(i%100==0)
                if(i%400!=0)
                    tot--;
        }
    }
    else
    {
        for(i=y1;i<y2;i++)
        {
            if(i%4==0)
                tot++;

            if(i%100==0)
                if(i%400!=0)
                    tot--;
        }

    }


    if(m2>m1)
    {
        for(i=m1;i<m2;i++)
        {
            if(i==1||i==3||i==5||i==7||i==8||i==10||i==12)
                tot++;

            if(i==2)
                tot=tot-2;
        }

    }

    lavish=tot%7;

    printf("\n\n");

    switch(lavish)
    {
        case 0:
            printf("SATURDAY");
            break;
        case 1:
            printf("SUNDAY");
            break;
        case 2 :
            printf("MONDAY");
            break;
        case 3  :
            printf("TUESDAY");
            break;
        case 4   :
            printf("WEDNESDAY");
            break;
        case 5    :
            printf("THRUSDAY");
            break;
        case 6     :
            printf("FRIDAY");
            break;
    }
    getch();
}
/**********************************************************************************/

Monday 4 March 2013

CALCULATE FACTORIAL OF VERY BIG NUMBERS THROUGH A SIMPLE C PROGRAM

Here is one more interesting program that enables you to calculate the factorial of very massive numbers such as 500. And even you can calculate the sum of all the digits of this massive number.
Have a look at this program and enjoy.
This program runs perfectly well in turbo cpp.

Enjoy programming:)


/*******************************************************************************/




#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<time.h>
#define max 5000
void multiply(long int *,long int);
void factorial(long int *,long int);


int main()
{
    clrscr();
    cout<<"PROGRAM TO CALCULATE FACTORIAL OF A NUMBER";
    cout<<"\nENTER THE NUMBER\n";
    long int num;
    cin>>num;

    long int a[max];
    for(long int i=0;i<max;i++)
        a[i]=0;

    factorial(a,num);

    clrscr();

    //PRINTING THE FINAL ARRAY...:):):)
    cout<<"THE FACTORIAL OF "<<num<<" is "<<endl<<endl;
    long int flag=0;

    int ans=0;
    for(i=0;i<max;i++)
    {
        if(flag||a[i]!=0)
        {
            flag=1;
            cout<<a[i];
            ans=ans+a[i];
        }
    }

    cout<<endl<<endl<<"the sum of all digits is: "<<ans;


    getch();
    return 1;
}

void factorial(long int *a,long int n)
{
    long int lavish;
    long int num=n;
    lavish=n;
    for(long int i=max-1;i>=0&&n;i--)
    {
        a[i]=n%10;
        n=n/10;
    }

    for(i=2;i<(lavish);i++)
    {
        multiply(a,num-1);
        num=num-1;

    }
}


void multiply(long int *a,long int n)
{

    for(long int i=0;i<max;i++)
        a[i]=a[i]*n;

    for(i=max-1;i>0;i--)
    {
        a[i-1]=a[i-1]+(a[i]/10);
        a[i]=a[i]%10;
    }
}


/*****************************************************************************/

For some simple factorial calculating functions refer the following links :-

Sunday 3 March 2013

CALCULATE MASSIVE NUMBER 2^3000

Hey friends,
Here is a  very interesting program in C that enables you to calculate a massive number like 2^1000 or even 2^3000. This program runs perfectly in turbo cpp.
Many a times we encounter a problem like through programming we have to calculate the sum of all digits of 2^1000. Initially this could seem to you a bit messed up, but once you have understood this program, it becomes very easy.
You might be thinking that this silly job can be done by calculator, but its not that true...just have a look at the output...you will be stunned as this program gives the full required number without truncating the answer...its simply amazing.
Just copy and paste this code on your tcpp and try it out just now.
Actually I encountered this problem on www.projecteuler.net an awesome site that always encouraged and tangled me, my favorite pass-time.
Hope you all like it.



Amazing Output:-

Have a look at it and enjoy...;)



 /****************************************************************************/

//PROGRAM TO CALCULATE POWER OF 2

#include<stdio.h>
#include<conio.h>
#define max 5000


void main()
{
    int arr[max],aarr[max],i,j,flag,lavish,tag,sum=0;
    clrscr();

    printf("program to calculate power of 2\n");
    printf("x^(number)\n");
    printf("enter the number\n");
    scanf("%d",&lavish);

    for(i=0;i<max;i++)
    {
        arr[i]=0;
        aarr[i]=0;
    }

    printf("\n\n");

    arr[max-1]=2;

    flag=1;

    while(1)
    {
        flag++;
        for(i=max-1;i>=0;i--)
        {
            aarr[i]=aarr[i]+((2*arr[i])%10);
            if(arr[i]>=5&&arr[i]<10)
                aarr[i-1]=1;
        }


        for(i=0;i<=max-1;i++)
        {
            arr[i]=aarr[i];
            aarr[i]=0;
        }

        tag=0;

        if(flag==lavish)
        {
            for(i=0;i<max;i++)
            {
                if(arr[i]!=0)
                    tag=1;
                if(tag==1)
                {
                    printf("%d",arr[i]);
                    sum=sum+arr[i];
                }
            }
            break;
        }
    }

    printf("\n\nsum of all digits is:-%d",sum);
    getch();
}



/***************************************************************************/

Friday 1 March 2013

My motivation for starting this blog is to provide coders a good platform for digging deep in search of solutions for programming problems...

The audience include the students for whom the academic curriculum is not full-filling their hunger to code. Its a right place for you if you are very curious to have a mind-boggling coding experience.

I will be basically concerned with c programming, but discussions on any other language are also welcomed.
I will be providing you with codes that you may find very interesting and useful not only for your academics but also to satisfy your coding hunger...that will grow day by day after visiting this blog.

Looking ahead for your valuable suggestion and queries for improvement...:)
Happy programming ;)