sandeep said:
Hello Friends ~
How would you find the maximum of
(a) two numbers
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."
How would you do it in idiomatic Perl?
Ah! A much easier question! Answer: I would not do it
in any kind of Perl, idiotmatic or otherwise.
Use this as a basis
for a discussion of the differences in expressive power of the two
languages.
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.