Like Tree11Likes

problem in divide and conquer approach to find max-min

This is a discussion on problem in divide and conquer approach to find max-min within the C Programming forums, part of the General Programming Boards category; Can anyone help me fix the problem with the code for finding max-min in an array? Code: #include<stdio.h> #include<conio.h> maxmin(int,int,int,int); ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    18

    problem in divide and conquer approach to find max-min

    Can anyone help me fix the problem with the code for finding max-min in an array?
    Code:
    #include<stdio.h>
    #include<conio.h>
    maxmin(int,int,int,int);
    int num[20],max,min,max1,min1;
    main()
    { int n,i;
    printf("enter number of elements in the array\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    printf("enter the number\n");
    scanf("%d",&num[i]);
    }
    maxmin(0,n-1,max,min);
    printf("the maximum element is- %d\n",max);
    printf("the minimum element is- %d\n",min);
    getch();
    }
    maxmin(int i,int j,int max,int min)
    {
    if(i=j) max=min=num[i];
    else if(j=i+1) { if(num[i]<num[j]) { max=num[j]; min=num[i];}
    else if(num[i]>num[j]){max=num[i]; min=num[j];}
    else max=min=num[i];
    }
    else
    {
    int mid=(i+j)/2;
    maxmin(i,mid,max,min);
    maxmin(mid+1,j,max1,min1);
    }
    Code:
    if(max<max1) max=max1;
    if(min>min1) min=min1;
    }
    


  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Can you please solve your exercises one by one?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    2,506
    Learn the difference between "==" and "=".

    Learn to indent your code when posting it.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  4. #4
    Registered User
    Join Date
    Nov 2012
    Posts
    1,053
    The problem is here

    Code:
    maxmin(0,n-1,max,min);
    printf("the maximum element is- %d\n",max);
    printf("the minimum element is- %d\n",min);
    No matter what your function maxmin does, the calling function retains the original values of max and min. If you want your function to be able to modify the values of max and min, you must call your function like this

    Code:
    maxmin(0,n-1,&max,&min);
    printf("the maximum element is- %d\n",max);
    printf("the minimum element is- %d\n",min);
    And then define the arguments to maxmin with appropriate pointer types.

    Also, I notice you defined max and min as global but you are not using them as global. Better to define them inside your function scope rather than global. Same with your array.

  5. #5
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    As the variables- max and min have already been made global and the function-'maxmin' being called before the maximum and minimum values are printed, am I supposed to pass the references- &max,&min?

  6. #6
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    Thanks for pointing the mistake.

  7. #7
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    At c99tutorial,
    Can you please write the modified code using both "global" and "local" scopes to better help me get the concept.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Sorry, but "do it for me" requests are largely going to be ignored here. We're here to help you learn, not to do it for you.

    I suggest that you post your updated code where you have applied the advice given so far.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    The modified code is below, which still prints the incorrect max- min.
    Code:
     
    Code:
    #include<stdio.h>
    #include<conio.h>
    int maxmin(int,int,int *,int *);
     int num[20];
     main()
    {
    int max,min;  int n,i;
    printf("enter number of elements in the array\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("enter the number\n");
        scanf("%d",&num[i]);
    }
     maxmin(0,n-1,&max,&min);
     printf("the maximum element is- %d\n",max);
     printf("the minimum element is- %d\n",min);
     getch();
    }
    maxmin(int i,int j,int *max,int *min)
    {    int max1,min1;
        if(i==j) *max=*min=num[i];
        else if(j==(i+1)) {  if(num[i]<num[j]) { *max=num[j]; *min=num[i];}
                             else if(num[i]>num[j]){*max=num[i]; *min=num[j];}
                             else *max=*min=num[i];
                           }
        else
            {
                int mid=(i+j)/2;
                maxmin(i,mid,max,min);
                maxmin(mid+1,j,&max1,&min1);
            }
    
    
         if(*max<max1) *max=max1;
         if(*min>min1) *min=min1;
    }

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,401
    Compile at a high warning level: your compiler should be warning you about something that you need to fix.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    But how to increase the warning level of the compiler, presently it shows zero errors and zero warnings.

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    There's a great line in a movie "The Lost Boys", where the younger brother's new friend, reveals he's a dedicated teen-age Vampire killer (wanna be), on the hunt to kill a Vampire.

    First time he hears this, the older brother turns to his younger brother and asks "Where did you say you met this guy?".

    That's my question for this logic here - "Where did you say you thought of this?"

    There are two simple ways to get max and min from an array:

    1) If the array is being checked AFTER all the values are entered, then:
    *assign max and min BOTH to array[0].

    *and use two if statements, as you traverse the array in a loop:
    Code:
    for(each item in the array) {
       if(array[i] > max) max=array[i];
       if(array[i] < min) min = array[i];
    }
    2) If the array is being checked AS the values are being entered, then:
    *assign max and min to the first entered number:
    Code:
    if(i==0) {
       max=array[0]; 
       min=array[0];
    }
    //and then continue testing each number, with two if statements, //immediately AFTER the number has been entered into the array:
    if(array[i] > max) max=array[i];
    if(array[i] < min) min=array[i];
    Note that both examples are simple, concise, and require no else or else if statements. Get used to using local variables, unless required to do otherwise.

    The younger brother replied, "in the Comic Book store".

    And I'm giving out some pseudo code, because this, has been declared a sin against C followers, everywhere:
    Code:
        if(i==j) *max=*min=num[i];
        else if(j==(i+1)) {  if(num[i]<num[j]) { *max=num[j]; *min=num[i];}
                             else if(num[i]>num[j]){*max=num[i]; *min=num[j];}
                             else *max=*min=num[i];
                           }
        else
            {
                int mid=(i+j)/2;
                maxmin(i,mid,max,min);
                maxmin(mid+1,j,&max1,&min1);
            }
    
    
         if(*max<max1) *max=max1;
         if(*min>min1) *min=min1;
    }
    Encyclical and Fatwa, to follow.
    Last edited by Adak; 12-22-2012 at 06:39 AM.
    Crossfire likes this.

  13. #13
    Registered User
    Join Date
    May 2009
    Posts
    2,506
    The values of max1 and min1 are in my opinion undefined/uninitialized most of the time in your code. Therefore I expect a high chance of unpredictable results on some compilers.

    Tim S.

    Code:
         if(*max<max1) *max=max1;
         if(*min>min1) *min=min1;
    comocomocomo likes this.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  14. #14
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    Adak, the two algos to find the max-min that you talked about are straightforward and I know this. What I want to do is to implement the "divide and conquer approach" to it. But your such a long post ends up prematurely without pointing the bug in it or suggesting a way out.

  15. #15
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    But how to increase the warning level of the compiler, presently it shows zero errors and zero warnings.
    One would have to know the name of the compiler to know this. Either tell us or do a google search such as

    "[Compiler Name] adjust warning level"

    I would suggest this as laserlight usually spots these things pretty well, but his answers can be rather cryptic.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 10-25-2012, 09:50 PM
  2. Divide and Conquer Merge_sort
    By nimitzhunter in forum C++ Programming
    Replies: 4
    Last Post: 12-10-2010, 05:39 PM
  3. Divide and Conquer: array in the reverse order
    By Steamer in forum C Programming
    Replies: 11
    Last Post: 03-08-2004, 06:31 PM
  4. divide and conquer
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-13-2002, 09:52 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21