facebook like button

12 December, 2011

Reversing order of words in a sentence using stack

The need:
     This is another way ( a layman's approach) to write previous program about this topic. I have written the approach there too.
The code:
----------------------------------------------------------
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct linked_list
{
    char *chr;
    struct linked_list *next;
};
typedef struct linked_list node;
void push(node **p,char *x);
char *pop(node **p);

int main()
{
    char a[50],*temp,*dup;
    strcpy(a,"I dont know why useless programs are asked");
    node * head=NULL;
    temp=strtok(a," ");
    while(temp != NULL)
    {
        dup=strdup(temp);
        temp=strtok(NULL," ");
        push(&head,dup);
    }
    strcpy(a,"");
    while((temp=pop(&head))!=NULL)
    {
        strcat(a,temp);
        strcat(a," ");
    }
    a[strlen(a)-1]='\0';
    printf("%s\n",a);
    return 0;
}

void push(node **p,char *x)
{
    node *new_node;
    new_node=(node *)malloc(sizeof(node));
    new_node->chr=x;
    new_node->next=*p;
    *p=new_node;
}

char *pop(node **p)
{
    char *temp=NULL;
    node *tmp;
    if(*p==NULL)
        return (NULL);
    else
    {
        temp=(*p)->chr;
        tmp=*p;
        (*p)=(*p)->next;
        free(tmp);
        return (temp);
    }
}
----------------------------------------------------------
Approach:
    In that case I have made use of my stack concepts and using almost no brain I have got it done. Have a look how simple is this. Steps are:
1. read word by word (strtok has been used to read words delimiter is space)
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print. :-)
Remarks:
1. This is not the most efficient method to do this. For more efficient method have a look at previous program about this topic.
2. This program can also be used to reverse the order of words in a file. In that case steps are:
  1. read word by word (using fscanf(FilePointer,"%s",&TempString)).
  2. keep on pushing all words on a stack till last word.
  3. Now pop each word and print to another file. :-)

11 December, 2011

Finding k'th root of a number

The need:
    The need is nothing but to find k'th root of a number.
The code:
----------------------------------------------------------------
#include<stdio.h>
#include<math.h>
main()
{
    printf ("*********a program to find k'th root of x ....\n\n");
    char c;
    float i,j,k,m;
    do
    {
    printf ("To get k'th root of x ....\n");
    printf ("type the values .....\n\n");
    printf ("x= "); 
    scanf("%f",&i);
    printf ("k=  ");
    scanf("%f",&k);
    j=pow(i,(1/k));
    printf("\n %dth root of%f = %f\n\n\n",(int)k,i,j);
    printf("do you want to try more? y/n \t");
    fflush(stdin);
    c=getchar();
    }while(c=='y');
}
---------------------------------------------------------------- 
The Approach:
     The approach is very simple. Lets apply simple math
If y^k = x
then y =  x^(1/k)
and the problem is solved because we have built-in pow() function for a power.

10 December, 2011

Variable number of arguments to a function

Variable number of arguments:
     Till now we have seen various types of functions in C. Some them were built-in and some user defined. There are a lot of noticeable point about them. Intuitively We can say that all the functions should possess same characteristics  whether it is user defined or built-in. We have also seen function returning some value, not returning any value, taking no argument and taking certain fixed number of arguments with certain data-types.
    Some-times a question can come in your mind if it is possible for a function to accept any number of arguments in C language. Off course it is possible !!! In fact we have used such function many times. Don't remember??? Recall our most commonly used functions printf() and scanf(). How many arguments does printf() function take??
     Let me remind you when we pass arguments to a function while calling it, the arguments are separated by a comma(,). So printf() function takes variable number of arguments. First argument to printf() is a character string and after that some other arguments of various types may or may not come. This fact encourages us to create our own user defined function which would take variable number of arguments.
Problem and solution:
    There may be some problems while implementing variable arguments. One such problem is to determine how many arguments have been passed during a particular call. To overcome that problem there is a rule that at least one argument must be specified in the declaration of function. For more ease I will be giving that argument as a number equal to the count of following arguments so that I can easily know that how many arguments are being passed.
Sample program:
     This program is one of the simplest programs for illustrating the use of variable number of arguments. There is a function sum which can take may arguments and print the sum of those.
Have a look.
------------------------------------------------------------
#include <stdio.h>
#include <stdarg.h>
int sum(int num, ... );
int main( void )
{
    printf("This is program to show the use of variable numbers of arguments to a function\n");
    printf( "Sum of 1,2,3,4 is %d\n", sum(4,1,2,3,4) );
    printf( "Sum of 4,5,3 is %d\n", sum(3,4,5,3) );
    printf( "Sum of 7,3,4,9,1,5 is %d\n", sum(6,7,3,4,9,1,5) );
    return( 0 );
 }
int sum(int num, ... )
{
    int answer = 0;
    va_list argptr;
    va_start( argptr, num );
    while(num-- > 0)
    answer += va_arg( argptr, int );
    va_end( argptr );
    return( answer );
} 
------------------------------------------------------------
Explanation:
    Declaration of the function is clear as shown. Here argptr is a variable of type va_list. After va_start function is executed here, argptr will contain list of rest of the variables. After that each value of each argument can be accessed with the help of va_arg() function. When all the arguments are finished va_end() function should be put at the end. This va_end() is analogous to fclose() in file handling.
 
Remarks: 
1. variable number of arguments means the function can take some random(but finite) number of arguments. This does not mean that the function can take infinite number of arguments. Maximum number of arguments to a function are limited and depend on the compiler.

Insertion sort in C

The need:
     This is a program to sort a given array of numbers using insertion sort. This program sorts numbers in increasing order. To read more about insert sort read wikipedia.
The code:
----------------------------------------------------------
#include<stdio.h>
void insert_sort(int a[],int size);
int main()
{
    int i,size;
    printf("program for sorting using insert sort\nHow many numbers do you want to sort\n");
    scanf("%d",&size);
    int arr[size];
    printf("enter numbers\n");
    for(i=0;i<size;i++)
    scanf("%d",&arr[i]);
    
    printf("the array before sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    insert_sort(arr,size);
    printf("the array after sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

void insert_sort(int a[],int size)
{
    int i,j,k,temp;
    for(i=1;i<size;i++)
    {
        j=0;
        temp=a[i];
        while(temp>a[j]&&j<i)
        j++;
        for(k=i;k>j;k--)
            a[k]=a[k-1];
        a[k]=temp;
    }
}
----------------------------------------------------------
Approach:
   The approach is to follow the existing algorithm. Read algorithm on wikipedia. The basic idea is traverse the array form start, temporarily store value of current element and search for the place to the left of that element where the value fits. When you find the place, shift the elements after that position by one to make the void to place temporarily stored element.

09 December, 2011

finding kth largest number out of n numbers

The need:
     This program gives the kth largest number from the given unsorted list of n numbers. I don't know what could be the application of that but some sites tell that it is asked as interview question sometimes.
The code:
----------------------------------------------------------
/*find kth largest number from a list of n numbers*/
#include<stdio.h>
#include<stdlib.h>
void getMaxToFront(int *p,int front, int end);
void swap(int *, int *);
int main()
{
    int i,*num,n,k;
    printf("This is a program to find kth largest number from a list of numbers\n");
    printf("how many are total numbers\n n = \t");
    scanf("%d",&n);
    if(1>n)
        exit(printf("n cannot be less than 1\n"));
    printf("for kth largest give value of k\n k = \t");
    scanf("%d",&k);
    if(k<1)
        exit(printf("k cannot be less than 1\n"));
    if(k>n)
        exit(printf("k must be less then n\n"));
    num=(int *)malloc(n*sizeof(int));
    printf("now enter %d integers\n",n);
    for(i=0;i<n;i++)
    scanf("%d",num+i);
    for(i=0;i<k;i++)
        getMaxToFront(num,i,n-1);
    printf("\n%d is %dth largest\n",*(num+k-1),k);
    getchar();
    return 0;
}

void getMaxToFront(int *p,int front, int end)
{              
    int i;
    for(i=front+1;i<=end;i++)
        if( *(p+front) < *(p+i) )
        swap(p+front,p+i);
}

void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

----------------------------------------------------------
Approach:
   first approach is simple. Pick the largest bring it to 1st position, then pick largest from the rest of list and bring on 2nd position and so on upto kth :-).

Remarks:
Analyze the case:
n=100, k=5;
The above program is fine with that. Just find out biggest 5 numbers and done.
Now have a look at this case:
n=100, k=95;
In this case you will not want to go from front to end because you will have to iterate the loop in main 95 time. Instead we'll find out 6th smallest and go end to front... :-)
so better modify the above program a little bit which is like below:
-------------------------------------------------------------
/*find kth largest number from a list of n numbers*/
#include<stdio.h>
#include<stdlib.h>
void getMaxToFront(int *p,int front, int end);
void getMinToEnd(int *p,int front, int end);
void swap(int *, int *);
int main()
{
    int i,*num,n,k;
    printf("This is a program to find kth largest number from a list of numbers\n");
    printf("how many are total numbers\n n = \t");
    scanf("%d",&n);
    if(1>n)
        exit(printf("n cannot be less than 1\n"));
    printf("for kth largest give value of k\n k = \t");
    scanf("%d",&k);
    if(k<1)
        exit(printf("k cannot be less than 1\n"));
    if(k>n)
        exit(printf("k must be less then n\n"));
    num=(int *)malloc(n*sizeof(int));
    printf("now enter %d integers\n",n);
    for(i=0;i<n;i++)
    scanf("%d",num+i);
    if(k<=n/2){
    printf("\nusing getMaxToFront\n");
    for(i=0;i<k;i++)
        getMaxToFront(num,i,n-1);
    }
    else{
    printf("\nusing getMinToEnd\n");
    for(i=n;i>=k;i--)
        getMinToEnd(num,0,i-1);
    }
    printf("\n%d is %dth largest\n",*(num+k-1),k);
    getchar();
    return 0;
}

void getMaxToFront(int *p,int front, int end)
{                //end is needed as an argument here because we need to use the length of list
    int i;
    for(i=front+1;i<=end;i++)
        if( *(p+front) < *(p+i) )
        swap(p+front,p+i);
}

void getMinToEnd(int *p,int front, int end)
{                //actually we could have skipped front as an argument here observe each time I am passing 0 as front
    int i;
    for(i=end;i>=front;i--)
        if( *(p+end) > *(p+i) )
        swap(p+end,p+i);
}

void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
-------------------------------------------------------------
This program uses the method/function which gives less number of loop runs.

Finding whether a number is armstrong number of not

The need:
     This one is trivial program at this point of time. Still putting on demand of Rahul Devra.For those who dont know what is Armstrong number (Narcissistic number) first have a look at Narcissistic number on wikipedia.
The code:
----------------------------------------------------------
/*Find whether entered number is armstrong number or not*/
#include<stdio.h>
#include<math.h>
int digit_count(int x);
int isArmstrong(int x);

int main()
{
    int flg=0,num;
    printf("This is a program to find whether a number is armstrong number\n");
    printf("enter a natural number\n");
    scanf("%d",&num);
    if(isArmstrong(num))
    printf("%d is an armstrong number\n",num);
    else
    printf("%d is not an armstrong number\n",num);
    getchar();
    return 0;
}

int digit_count(int x)
{
    int count=0;
    if(x==0)
    return 0;
    while(x/=10)
    count++;
    return count+1;
}

int isArmstrong(int x)
{
    int i,num_digit,sum=0,current_digit,holder;
    num_digit = digit_count(x);
    holder=x;
    for(i=0;i<num_digit;i++)
    {
        current_digit = x%10;
        sum+=pow(current_digit,num_digit);
        x/=10;
    }
    if(sum==holder)
    return 1;
    else
    return 0;
}
----------------------------------------------------------
Approach:
   The approach is simple. Go by the definition, take digit by digit check for the condition for Armstrong number and that's it.

07 December, 2011

getting nth term of fibonacci series unlimited number of terms

The need:
     The program for fibonacci series is very simple but those programs give you terms upto the limit of integer size. This is a program to print Fibonacci series upto 10000th term. I wrote this program when I noticed people coming on previous fibonacci program in search of 2011th term or so.
The code: 
--------------------------------------------
#define MAX 2100 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
void print(char x[]); 
void add(char x[], char y[], char z[]); 

int main() 
{ 
    int i=0,j,num; 
    char n_minus1[MAX]="1",n_minus2[MAX]="1",nth[MAX]=""; 
    printf("This is a program to print fibonacci sequence upto desired term.(max 10000)\n"); 
    printf("\nenter a natural number upto which do you want fibonacci series\n");
    scanf("%d",&num); 
    if(    num<1||num>10000) 
    { 
        printf("The desired term index was either invalid or greater than 10000\n"); 
        exit(0); 
    }
    printf("\noptions:\n1. print only %dth term\n2. print all terms\n",num);
    scanf("%d",&j);
    switch(j)
    {
        case 1: 
                if(num<2){
                printf("The first term is 1\n");
                break;
                }
                if(num<3){
                printf("The second term is 1\n");
                break;
                }
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                printf("The %dth term is ",num);
                print(nth);
                break;
        case 2:    printf("\nFibonacci series upto %dth term\n\n",num);
                printf("term \tvalue\n",num);
                printf("%4d \t1\n",1);
                if(num<2)
                break;
                printf("%4d \t1\n",2);
                if(num<3)
                break;
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  printf("%4d\t",i+1);
                  print(nth);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                break;
        default: printf("Invalid choice...!!! \tExiting\n");
                exit(0);
    }
    printf("\n\nprgram finished successfully.\t press any key to continue\n");
    getchar(); 
    return 0; 
} 

void print(char x[]) 
{ 
    int i; 
    for(i=strlen(x)-1;i>=0;i--) 
    { 
        putchar(x[i]); 
        if(i%5==0) 
        putchar(' '); 
    } 
    putchar('\n'); 
    return; 
} 

void add(char x[],char y[],char z[]) 
{ 
    int i,ylen,zlen,equal;
    char c = 0,temp;
    ylen = strlen(y);
    zlen = strlen(z);
    equal = (ylen == zlen) ? 1 : 0; 
    for(i=0;i<zlen;i++) 
    { 
        x[i]=c + y[i] + z[i] - '0'; 
        if( x[i]-'0' > 9)
        {
            x[i]-=10;
            c=1;
        }
        else
        c=0; 
    }
    if(equal)
    {
        if(c!=0)
        {
            x[i]=c + '0';
            x[i+1]='\0';
        }
    }
    else
    {
        x[i]=c + y[i];
        x[i+1]='\0';
    } 
    return; 
}
-------------------------------------------- 

The approach: 
This program creates a Fibonacci series upto the terms given by the user. The logic is same. Just go with the definition of Fibonacci that any term is the sum of its two preceding terms. Here nth always hold current term and n_minus1 and n_minus2 hold previous 2 terms(except for first 2 terms case). I have already told that integers are very small to work when we have more than 10digits in the scene so these 3 variables are taken as strings. add() is UDF defined by me which takes 3 arguments x,y,z. add puts sum of y and z into x. This add() is the only twist here to differentiate this program from program38 of this blog.

Remarks:
1. In this program is capable to give you upto 10000th term of fibonacci easily.
2. You can get upto more terms. all you have to do is to increase the value of max in #define statement. This is why I wrote unlimited in the title.

06 December, 2011

program to reverse the spelling of words in a sentence

The need:
     I don't know what could be the need of this program but I found this question on many sites and thats why I wrote this program.
The code:
----------------------------------------------------------
#include<stdio.h>
#include<string.h>

void reverse(char *str,int start, int end)
{
    char temp;
    int i,j;
    i=end-start;
    for(j=0;j<=i/2;j++)
    {       
        temp=*(str+start+j);
        *(str+start+j)=*(str+start+i-j);
        *(str+start+i-j)=temp;
    }
}

rev_word(char *str)
{
    int start=0,end=0,i=0;   
    while(*(str+i)!='\0')
    {
        if(*(str+i)==' ')
        {
            end=i-1;
            reverse(str, start, end);
            i++;
            start=i;
        }
        else
            i++;
    }
    end=i-1;
    reverse(str, start, end);
}

int main()
{
    char a[]="I dont know why useless programs are asked";
    printf("before\n%s\n",a);
    rev_word(a);
    printf("after\n%s\n",a);
    return 0;
}
----------------------------------------------------------
Approach:
   The approach is simple. make a note of start and end points (indices) of each word and reverse with the help of those points. The UDF reverse() does the job here.

program to reverse the order of words in a sentence

The need:
     I don't know what could be the need of this program but I found this question on many sites and thats why I wrote this program.This program is extension of previous program.
The code:
----------------------------------------------------------
#include<stdio.h>
#include<string.h>

void reverse(char *str,int start, int end)
{
    char temp;
    int i,j;
    i=end-start;
    for(j=0;j<=i/2;j++)
    {      
        temp=*(str+start+j);
        *(str+start+j)=*(str+start+i-j);
        *(str+start+i-j)=temp;
    }
}

rev_word(char *str)
{
    int start=0,end=0,i=0;  
    while(*(str+i)!='\0')
    {
        if(*(str+i)==' ')
        {
            end=i-1;
            reverse(str, start, end);
            i++;
            start=i;
        }
        else
            i++;
    }
    end=i-1;
    reverse(str, start, end);
}

int main()
{
    char a[]="I dont know why useless programs are asked";
    printf("before\n%s\n",a);
    rev_word(a);
    reverse(a, 0, strlen(a)-1);
    printf("after\n%s\n",a);
    return 0;
}
----------------------------------------------------------
Approach:
   The approach is simple. make a note of start and end points (indices) of each word and reverse with the help of those points. The UDF reverse() does the job here. After that reverse the whole sentence character by character. I have used my UDF here because its existing and I dont need to write or search for another function though one could also use strrev() built-in function to reverse the whole sentence character by character.
Remarks:
1. You can modify reverse() function here into ordinary string_reverse (same as built-in strrev) function. For that remove arguments start and end from the function definition and use 0 in place of start and (length of string-1) as end.
Other approach:
2. Here for doing the whole thing I have used only one extra character other than the provided string (off course I have also used counters etc. but that is different thing). If I was allowed to use as much space as I wanted, I would have not thought this much like I have thought here --> reversing the spelling of each word and then reversing the whole string. In that case I would have made use of my stack concepts and using almost no brain I could have got it done. Have a look how simple is this. Steps are:
1. read word by word (using scanf with %s)
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print. :-)
For this approach have a look at next program on this topic.