finding maximum

Discussion in 'C Programming' started by sandeep, Mar 31, 2009.

  1. sandeep

    sandeep Guest

    Hello Friends ~

    How would you find the maximum of
    (a) two numbers
    (b) a set of numbers
    in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
    for a discussion of the differences in expressive power of the two
    languages.

    Thx!

    Sandeep
     
    sandeep, Mar 31, 2009
    #1
    1. Advertisements

  2. sandeep

    jacob navia Guest

    OK. To make it easier for you, can you tell us
    the name of your teacher?

    We will send him the answer directly.

    thanks
     
    jacob navia, Mar 31, 2009
    #2
    1. Advertisements

  3. sandeep

    Phil Carmody Guest

    Can you let us have your teacher's email address, so that we
    can get your homework answers to him directly, to save you the
    effort.

    Phil
     
    Phil Carmody, Mar 31, 2009
    #3
  4. sandeep

    Default User Guest

    A better idea would be for you to do the homework that you've been
    assigned. The assignment was for a reason, that is to teach you some
    programming concepts and techniques.



    Brian
     
    Default User, Mar 31, 2009
    #4
  5. sandeep

    sln Guest

    What is "idiomatic" is that a washing machine gone bad?

    -sln
     
    sln, Apr 1, 2009
    #5
  6. Or perhaps it's flamebait disguised as homework.
     
    Spiros Bousbouras, Apr 1, 2009
    #6
  7. ["Followup-To:" header set to comp.lang.perl.misc.]



    The poster's address should have been a big clue.

    I have that one killfiled.
     
    Tad J McClellan, Apr 1, 2009
    #7
  8. sandeep

    Eric Sosman Guest

    Negate both, find the minimum, and negate that minimum.
    Be careful of corner cases: On many systems negating the most
    negative integer fails to produce a positive integer (which
    could lead to an incorrect answer), and on some systems there
    are numbers X,Y such that X<=Y and Y<=X are *both* false.
    A subtle problem; I wish you luck with it.
    Much harder, because in a set of N numbers there are
    (N choose 2) = N * (N-1) / 2 pairs to consider. Even for a
    fairly modest set size like N = 1000000 it can easily happen
    that (N choose 2) exceeds the maximum value of the system's
    integer.

    So, I suggest a heuristic approach. Choose a pair of the
    numbers at random, and determine their maximum by applying the
    solution to (a). Then choose another pair at random and find
    *their* maximum the same way. Now (and here's the crux) you
    have formed the leftmost two pieces of a tree in which all the
    numbers appear:

    . .
    . . .
    / \ .
    max(A,B) max(C,D) .
    / \ / \ /
    A B C D E ...

    Using a stack (or possibly a priority queue) you can recursively
    compute max(A,B,C,D) = max(max(A,B), max(C,D)), and then
    max(A,B,C,D,E,F,G,H) = max(max(A,B,C,D), max(E,F,G,H))
    = max(max(max(A,B), max(C,D)), max(max(E,F), max(G,H))) and
    so on, populating the tree in a bottom-up left-to-right
    fashion. Eventually, the root of the tree will be equal to the
    maximum of the entire set, with a probability close to unity.
    There's a strong analogy to the Mergesort algorithm: If you
    consider the tree as a representation of a merge sort, then
    the desired maximum of N elements is the unique element that
    is not among the first N-1 emitted.
    There is no such thing as "idiomatic C." There are only
    "High C" (as practiced during the High C Era), and "Trade C"
    (the patois that has taken hold among those who'd rather get
    things done than argue about the proprieties). There are also
    some debased C-ish dialects, notably "Rapper's C" or "CRap."
    Ah! A much easier question! Answer: I would not do it
    in any kind of Perl, idiotmatic or otherwise.
    Both languages are Turing-complete, that is, capable of
    expressing methods that solve all computable functions (subject
    to the finiteness limits of the computers they execute on.) Also,
    both languages are Virgil-complete, that is, capable of expressing
    figurative and poetic thought, as in

    C2shining(C)

    and

    Perl + Perl <- Swine
    D'rn.
     
    Eric Sosman, Apr 1, 2009
    #8
  9. ["Followup-To:" header set to comp.lang.perl.misc.]



    Leaving out "Tenne C" is inexcusable.

    http://www.netfunny.com/rhf/jokes/88q3/0tenny.html
     
    Tad J McClellan, Apr 1, 2009
    #9
  10. sandeep

    Andrey Vul Guest


    You have made my day. Thank you so much.
     
    Andrey Vul, Apr 1, 2009
    #10
  11. sandeep

    sln Guest

    Pretty lose language. Can you give examples of that?

    -sln
     
    sln, Apr 1, 2009
    #11
  12. sandeep

    sln Guest

    Why don't you 'C' a doctor for examples.

    -sln
     
    sln, Apr 1, 2009
    #12
  13. The simple answer is: "Post the problem to the usenet and wait for
    others to solve it for you".
     
    Josef Moellers, Apr 1, 2009
    #13
  14. sandeep

    Bart Lateur Guest

    Well, that doesn't seem to work too well.
     
    Bart Lateur, Apr 1, 2009
    #14
  15. sandeep

    Ted Zlatanov Guest

    s> How would you find the maximum of
    s> (a) two numbers
    s> (b) a set of numbers
    s> in idiomatic C? How would you do it in idiomatic Perl?

    In any language, you put the numbers in an array, sort the array, and
    return the element at the top. Similarly, to get the average, you sort
    the array and then return the middle number (AKA the "median average").

    In Perl sorting is even built into the language; in C unfortunately you
    have to embed the Perl interpreter to get that kind of simplicity.

    s> Use this as a basis for a discussion of the differences in expressive
    s> power of the two languages.

    We are programmers, sir. Discussion does not become us. We are always
    right, even when we're wrong.

    Ted
     
    Ted Zlatanov, Apr 1, 2009
    #15
  16. sandeep

    sandeep Guest

    Friends ~

    Thanks for the answers. Actually this is not a homework, I am just curious.

    Anyways, here is my solution:

    (a) in C:

    int max(int a, int b)
    {
    if(a>b)
    return a;
    return b;
    }

    in Perl:

    sub max
    {
    my $max = shift;
    for(@_) {
    $max=$_ if($_>$max)
    }
    $max;
    }


    (b) in C:

    #define NUMMAX (10)
    int max(int a[NUMMAX])
    {
    int max = -1;
    for(int i=0; i < NUMMAX;)
    if(a[i++]>max)
    max = a[i-1];
    return max;
    }


    In Perl: the solution for (a) still works.

    Conclusion: Perl is more expressive as a simple function for two arguments
    often generalizes to any list.

    Best greetings
    Sandeep
     
    sandeep, Apr 1, 2009
    #16
  17. sandeep

    user923005 Guest

    If performance matters, C will probably be a little faster.
    If your programmers who maintain the code are Perl programmers, then
    Perl is the logical choice, and vice-versa.
    In either case, unless you are processing a billion items, the
    language choice does not matter much.
    If a language is Turing complete (and most of them are) then something
    simple like finding the max from a list can be done without much fuss.

    Which language to choose to solve some programming problem usually
    turns into a pissing match, especially when cross-posted to multiple
    language groups.

    For my opinion, I don't think either one is a better choice.

    IMO-YMMV
     
    user923005, Apr 1, 2009
    #17
  18. all of which are verbose compared to (max list):
    (max 3)
    3
    ;; maximum of two integers
    (max 483 6932487534)
    6932487534
    ;; maximum of two floats and an integer
    (max 4.72 49.1 -3)
    49.100000000000001
    ;; maximum of a list, including several types
    (max -3 49/3 5.37s-1 -34.3l-2 5.1)
    49/3
    ;; minimum of the same list
    (min -3 49/3 5.37s-1 -34.3l-2 5.1)
    -3
    (-3 49/3 0.537S0 -0.34299999999999997 5.0999999999999996)
    Conclusion: lisp is more expressive, period.
     
    Martin Ambuhl, Apr 1, 2009
    #18
  19. sandeep

    jameskuyper Guest

    That's at best an O(N log N) solution. There's an O(N) solution which
    is even simpler; sandeep presented the basic idea for that solution
    (badly) in his second message on this thread.
    In C, sorting is built into the standard library: qsort(). It may be
    clumsier to use, perhaps, than Perl's sort, but it's still an easier
    solution for a C program than embedding the perl interpreter.
     
    jameskuyper, Apr 1, 2009
    #19
  20. ["Followup-To:" header set to comp.lang.perl.misc.]



    Unless the array might be "large".

    Your algorithm is likely O(n log n) when finding the maximum can
    be done in only O(n).


    Sure we do. We discuss stuff all the time.

    But we discuss what interests us.

    That is, we do not take direction from random usenauts.
     
    Tad J McClellan, Apr 1, 2009
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.