Expert: Zlatko - 5/12/2010

Question
QUESTION: ANSI C library functions to export these five set functions.
1) Take a set as inputs from the key board and output it.
2) Print a set to screen.
3) computes the set median value.
4) computes the set maximum value.
5) computes the set minimum value.
  These are to be computed using recursive function only.

ANSWER: Hello Raphael.

For ethical reasons, I don't do people's homework. I help. In order to help, You have to tell me what you are having trouble with. You have to tell me what you have tried. You have to tell me what you don't understand.

To start, I suggest you take your input from an array, so you don't have to keep typing numbers as you test your program.

Later store your input from the keyboard into the array, so your min, max, and median functions will not change just because your input source changes.

Using recursive functions means you are to divide the array into 2 and work on each individual half, then combine the results. This is the general recursive divide and conquer idea. To do this, your function will need to take the array, the start index of the array, and the end index of the array. Your recursive function will need an exit condition as well so that you don't get infinite recursion.

For example, here is C-pseudo-code for the min function

int findMinimum(int list*, int indexLow, int indexHigh)
{
    /* Step 1. Check the exit condition */
    if list size is 1, return the only element of the list
  
    /* Step 2. Divide the array into left and right sides and recurse */
    minLeft = findMinimum(list, indexLow, indexHighLeft);
    minRight = findMinimum(list, indexHighLeft+1, indexHigh);

    /* Step 3. Combine the results */
    if (minLeft < minRight) minimum = minLeft;
    else minimum = minRight;

    return minimum;
}

I leave it up to you to finish the above function. The findMaximum is the same idea.

Finding the median is trickier. It depends on if you are allowed to sort the array first or not. Ask your instructor. If you are allowed to sort the array, then the median is just the middle element of the sorted array. If you are not allowed to sort the array, then there is a recursive algorithm. Show me your effort and I'll help you more.

Best regards
Zlatko


---------- FOLLOW-UP ----------

QUESTION: #include <stdio.h>
#include "set.c"

int main()
{
  int set[10000];
  int choice;
  int count;
  
  do {
     printf("---------------------------------\n");
     printf("1. Input a set\n");
     printf("2. Print the current set\n");
     printf("3. Get the median\n");
     printf("4. Get the minimum\n");
     printf("5. Get the maximum\n");
     printf("6. Quit\n");
     
     printf("\nEnter your choice: ");
     scanf("%d", &choice);
     
     if (choice == 1)
     {
        read_set(set, &count);
     }
     else if (choice == 2)
     {
        printf("Current set: ");
        print_set(set, count);
     }
     else if (choice == 3)
     {
        printf("Median: %lf\n", get_median(set, count));
     }
     else if (choice == 4)
     {
        printf("Minimum: %d\n", get_minimum(set, count));
     }
     else if (choice == 5)
     {
        printf("Maxmimum %d\n", get_maximum(set, count));
     }          
  } while (choice != 6);
  
  return 0;
}
**************************************************************************
   

    set.c
#include <stdio.h>

void read_set(int* set, int* count)
{
  int i;
  printf("Number of integers to input: ");
  scanf("%d", count);

  printf("Enter %d integers: ", *count);
  for(i=0; i<(*count); i++)
  {
     scanf("%d", &set[i]);
  }
}

void print_set(int* set, int count)
{
  int i;
  
  for(i=0; i<count; i++)
  {
     printf("%d ", set[i]);      
  }
  
  printf("\n");
}

double get_median(int* set, int count)
{
  int i, j;
  int smaller_count;
  double median;
  
  median = 0;
  if (count % 2 == 1)
  {
     for(i=0; i<count; i++)
     {
        smaller_count = 0;
        for(j=0; j<count; j++)
        {
         if (i != j && set[i] >= set[j])
         {
         smaller_count = smaller_count + 1;      
         }
        }
        
        if (smaller_count == (count-1) / 2) median = set[i];   
     }
  }
  else
  {
     for(i=0; i<count; i++)
     {
        smaller_count = 0;
        for(j=0; j<count; j++)
        {
         if (i != j && set[i] >= set[j])
         {
         smaller_count = smaller_count + 1;      
         }
        }
     

        if ((smaller_count == (count/2-1)) || (smaller_count == count/2))
        {
         median = median  + set[i];
        }
     }
     median = median / 2;
  }
     
  return median;
}

int get_minimum(int* set, int count)
{
  int i;
  int min;
  
  min = set[0];
  for(i=1; i<count; i++)
  {
     if (set[i] < min) min = set[i];
  }
  
  return min;
}

int get_maximum(int* set, int count)
{
  int i;
  int max;
  
  max = set[0];
  for(i=1; i<count; i++)
  {
     if (set[i] > max) max = set[i];
  }
  
  return max;
}

THANKS, this is what i have but the gcc compiler keep giving error for no  1) storage typedef.Maybe store input with malloc
   2) For input validation  i needed too.
   3) In function to read set, <the gcc compiler gives errors>
   4) I like to change the word (count) in the code.
   ***ABOVE i need your help to add quality to the project so as to pass
   the gcc compiler.main.c and set.c are be co-compiled.
THanks,for yours anticipated respond.

Answer
May 13, 2010
----------------
Hello Raphael.
As I promised, I have looked more at the questions you have asked. I hope you have no more compiler errors.

You wanted to do dynamic allocation of the set with malloc? That is not difficult to do. First you declare set to be a pointer to integer, instead of an array of integer. Then pass the address of set to the read_set function. The read_set function will allocate the memory. The main function now looks like this.


int main()
{
   /*int set[10000];*/
   int* set = NULL; /* THIS LINE IS CHANGED for malloc */

   int choice;
   int count;

   do {
       printf("---------------------------------\n");
       printf("1. Input a set\n");
       printf("2. Print the current set\n");
       printf("3. Get the median\n");
       printf("4. Get the minimum\n");
       printf("5. Get the maximum\n");
       printf("6. Quit\n");

       printf("\nEnter your choice: ");
       scanf("%d", &choice);

       if (choice == 1)
       {
         if (set != NULL) free(set); /* Free the set before allocating a new one */
         read_set(&set, &count); /* THIS LINE IS CHANGED to pass &set instead of set */
       }





Next you have to change your read_set function to accept an int** instead of an int*. I have also made changes to read_set to check user input. You said you wanted to add quality to the project. Checking user input is one place to add quality. Here is my version.

#include <malloc.h>
void read_set(int** pp_set, int* count) /* Takes a pointer to a pointer to integer */
{
   int i;
   int* set;

   printf("Number of integers to input: ");
   while (scanf("%d", count) != 1 || *count < 0 || *count > 1000)
   {
       flushKeyboardBuffer();
       printf("Bad input\n");
       printf("Number of integers to input: ");
   }
   flushKeyboardBuffer();

   set = (int*)malloc(sizeof(int)* *count);
   printf("Enter %d integers: ", *count);
   for(i=0; i<(*count); i++)
   {
       while (scanf("%d", &set[i]) != 1)
       {
         flushKeyboardBuffer();
         printf("Bad input, please repeat\n");
       }
   }
   flushKeyboardBuffer();

   *pp_set = set; /* assign allocated memory to the passed in pointer address */
}

The flushKeyboardBuffer is a simple function to clear the keyboard buffer of extra characters the user may have entered so they don't interfere with the next input. It looks like this.


void flushKeyboardBuffer(void)
{
   char c;
   do
   {
       c = getc(stdin);
   } while (c != '\n' && c != EOF);
}


Please let me know if this has helped you. Are you going to try to make your min, max, and median functions recursive ? If you have more questions, please open a new question or post a follow-up.

Best regards
Zlatko

May 12, 2010
----------------
Hello Raphael.

I will give you a quick response now, then I will look more closely at the code.

First, do not include set.c into the main file.

You have set.c as a separate file.
Make a set.h that looks like this.

#ifndef _SET_H
#define _SET_H

void read_set(int* set, int* count);
void print_set(int* set, int count);
double get_median(int* set, int count);
int get_minimum(int* set, int count);
int get_maximum(int* set, int count);

#endif


Include set.h at the top of set.c and into the file with the main function. I will assume it is called main.c




So the top of the main file looks like this:

#include <stdio.h>
#include "set.h"

int main()
{
   int set[10000];
   int choice;
   int count;

   do {
       printf("---------------------






And the top of set.c looks like this




#include <stdio.h>
#include "set.h"

void read_set(int* set, int* count)
{
   int i;
   printf("Number of integers



Compile something like this
gcc -g -Wall -o outexe main.c set.c
When I do this, I get no errors or warnings.


You should understand that your get_minimum and get_maximum are not using a recursive algorithm. If your instructor asked for a recursive algorithm, you will not get full points.