Thread: i didn't understand part of this algorithm to calculate highest value

If you are unsure, it always helps to add some printfs, and then run the code.

i.e.

Code:

for (; begin!=end; begin++)
{

  //printf("%d\n", *begin);    // until here i understood. 

  printf("*largest=%d, *begin=%d\n\r", *begin, *largest);

  if(*largest < *begin)    //from here i didnt understand.
  {
    printf("*largest was smaller than *begin - *largest now has the value of *begin");
    largest = begin;          // also...
  }
}

If it is the pointer notation that you are unformiliar with, Pointers in C - Tutorial - Cprogramming.com

If it is what the program is doing that is confusing you, the clue for what it is doing is in the naming of the variable "largest"

Code:

return 0; // Bad style code, because we must return pointer, not number.
return NULL; // Good code style.


// By the way, I would totally rewrite so:


int* find_max(int* begin, int* end)
{
    int* max = NULL;
    while( begin < end ) {
       if( !max || *begin > *max ) {
           max = begin;
       }
       ++begin;
    }
    return max;
}

Originally Posted by zub

Code:

// By the way, I would totally rewrite so:
 
 
int* find_max(int* begin, int* end)
{
    int* max = NULL;
    while( begin < end ) {
       if( !max || *begin > *max ) {
           max = begin;
       }
       ++begin;
    }
    return max;
}

Why test for max on each iteration? It is not wrong, but it does not seem to be an improvement over checking the range before the loop.

Originally Posted by laserlight

Why test for max on each iteration? It is not wrong, but it does not seem to be an improvement over checking the range before the loop.

In many other cases, I would agree with you. However, it seemed to me simpler and more logical to do so. Think of it as an example of a different approach for solving the problem.

By the way, the original version can also be a bit optimized. On the first iteration occurs completely meaningless comparison of two identical numbers.

Code:

int* find_max(const int* begin, const int* const end)
{
    if( begin >= end ) { return NULL; } // attention to comparison!
    int* max = begin++; // attention to increment!
    for( ++begin; begin != end; ++begin ) { // other place for same increment.
        if( *max > *begin ) {
            max = begin;
        }
    }
    return max;
}

Originally Posted by zub

By the way, the original version can also be a bit optimized. On the first iteration occurs completely meaningless comparison of two identical numbers.

Yeah. However, you incremented begin twice in your revised example, which is wrong. I would suggest:

Code:

int *find_max(int *begin, int *end)
{
    int *max = NULL;
    if (begin < end)
    {
        max = begin;
        for (++begin; begin < end; ++begin)
        {
           if (*begin > *max)
           {
               max = begin;
           }
        }
    }
    return max;
}

Comparing for begin != end rather than begin < end should be fine too, upon which the implied pre-condition is that begin <= end.

Originally Posted by laserlight

Yeah. However, you incremented begin twice in your revised example, which is wrong.

No, I have two options of the same increment. Read the comments carefully.

I really made ​​a mistake in the code, but in a different line (*max > *begin). It's just a typo. I was distracted and did not have time to fix it in 60 minutes.

Originally Posted by zub

No, I have two options of the same increment. Read the comments carefully.

I read your code, not just your comments. Compile and run this program:

Code:

#include <stdio.h>
#include <stdlib.h>

const int* find_max(const int* begin, const int* const end)
{
    if( begin >= end ) { return NULL; } // attention to comparison!
    const int* max = begin++; // attention to increment!
    for( ++begin; begin != end; ++begin ) { // other place for same increment.
        if( *begin > *max ) {
            max = begin;
        }
    }
    return max;
}

int main(void)
{
    int numbers[] = {0, 2, 1};
    const int *max = find_max(numbers, numbers + sizeof(numbers) / sizeof(numbers[0]));
    if (max)
    {
        printf("%d\n", *max);
    }
    return 0;
}

You will find that the output is 1 even though the maximum is obviously 2. The reason is that you increment begin once, to point to the element at index 1, then you increment begin again, to point to the element at index 2. Since the element at index 2 is greater than the element at index 0, it is set to be the maximum, skipping the element at index 1, which is the true maximum.

Originally Posted by zub

I really made ​​a mistake in the code, but in a different line (*max > *begin). It's just a typo. I was distracted and did not have time to fix it in 60 minutes.

Heh, I did not spot that either, though my example code fixed the bug.

Apparently, I can not articulate my thoughts in English. I did increment in two lines, just to show that it can be made in any of them. I showed one possible place to increment and another possible place for the same increment. That is what is written in the comments.

Ah, now I understand. It might have been clearer to explain outside of the code since "other place for same increment" does not convey the intended meaning of "the increment from the previous line could have been placed on this line instead", especially since the increment does appear in the for loop's third expression.